1449 . 聖誕樹 2
TopCoder
Tags
Description
聖誕節到了又過了。PCC 這次準備了 $L$ 棵聖誕樹，第 $i$ 棵聖誕樹有 $n_i$ 個節點與 $n_i - 1$ 條彩帶，這些彩帶形成一棵樹。第 $i$ 棵聖誕樹上的第 $j$ 條彩帶連接節點 $u_{i,j}',v_{i,j}'$，其亮度為 $w_{i,j}'$。
接下來，PCC 把那 $L$ 棵聖誕樹按照順序疊起來，並在第 $i$, $i+1$ 棵聖誕樹之間用一些彩帶綁起來。具體來說，假設第 $i$, $i+1$ 棵聖誕樹之間綁了 $m_i$ 條彩帶，第 $j$ 條彩帶會把第 $i$ 棵樹的第 $u_{i,j}$ 個節點跟第 $i+1$ 棵樹的第 $v_{i,j}$ 個節點用一條亮度為 $w_{i,j}$ 的彩帶綁起來。
PCC 的家裡除了彩帶以外，還有 $Q$ 的小矮人，第 $i$ 個小矮人想要從第 $r_i$ 棵樹的節點 $c_i$ 走到第 $r_i'$ 棵樹的節點 $c_i'$，這裡小矮人只能透過彩帶在節點間移動。此外，因為小矮人長年待在地底，所以他們不太適應地面上的亮度。因此，他們會想要走彩帶亮度總和盡量低的彩帶們到達目的地。請幫助那 $Q$ 位小矮人分別找出他們各自需要經過的最少亮度總和是多少吧！
Input Format
輸入第一行有一個整數 $L$，表示 PCC 的聖誕樹有幾棵。
接下來輸入 $L$ 個區塊，每個區塊第一行為一個整數 $n_i ( 1 \leq i \leq L)$ ，並接著 $n_i -1$ 行，每行有三個整數 $u_{i, j}', v_{i, j}', w_{i, j}' (1 \leq j \leq n_i-1)$ ，表示第 $i$ 棵聖誕樹的節點 $u_{i, j}', v_{i, j}'$ 之間有一條亮度為 $w_{i, j}'$ 的彩帶。保證這些邊會形成一棵樹。
接下來有一行空行，並接著輸入 $L-1$ 個區塊，第 $i$ 個區塊表示相鄰第 $i, i+1$ 棵聖誕樹之間的彩帶。
對於每個區塊先輸入一個正整數 $m_i$，表示第 $i, i+1$ 棵聖誕樹之間有 $m_i$ 條彩帶。接下來輸入 $m_i$ 行，每行有三個正整數 $u_{i, j}, v_{i, j}, w_{i, j}$ ，表示第 $i$ 棵聖誕樹的節點 $u_{i, j}$ 跟第 $i+1$ 棵聖誕樹的節點 $v_{i, j}$ 之間有一條亮度為 $w_{i, j}$ 的彩帶。
接下來，輸入一個正整數 $Q$，表示小矮人的數量。
最後，輸入 $Q$ 行，每行有四個正整數 $r_i, c_i, r_i', c_i'$ 表示每個小矮人的起點跟目的地。第 $i$ 個小矮人會從第 $r_i$ 棵聖誕樹的節點 $c_i$ 出發，並要前往第 $r_i'$ 棵聖誕樹的節點 $c_i'$。
- $2 \leq L \leq 5 \times 10^ 4$
- $1 \leq n_i \leq 5 \times 10^ 4$
- 令 $N = \sum n_i$ ，則 $N \leq 5 \times 10^ 4$
- $1 \leq u_{i, j}', v_{i, j}' \leq n_i$
- $1 \leq m_i \leq 10$
- $1 \leq u_{i, j} \leq n_i$
- $1 \leq v_{i, j} \leq n_{i + 1}$
- $1 \leq Q \leq 5 \times 10^ 5$
- $1 \leq r_i, r_i' \leq L$
- $1 \leq c_i \leq n_{r_i}, 1 \leq c_i' \leq n_{r_i'}$
- $1 \leq w_{i, j}', w_{i, j} \leq 10^ 9$
Output Format
請輸出 $Q$ 行，第 $i$ 行代表第 $i$ 小矮人從自己的起點到自己的目的地所需要經過的最少亮度和。
Sample Input 1
3 5 1 2 1 2 3 2 3 4 4 4 5 8 2 1 2 16 2 1 2 32 2 5 2 64 1 1 128 1 2 2 256 2 1 1 3 2 1 1 1 5
Sample Output 1
335 15
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資。 | 0 |
| 2 | 1~4 | $N \le 2000, Q \le 500$。 | 30 |
| 3 | 5~14 | $L = 3$。 | 20 |
| 4 | 0~24 | 無特別限制。 | 50 |