配点 : 500 点
問題文
在帕肯王国 N 个城市, 它的编号为 1,2,3,\ldots,N 。
在王国中 N-1 有一条路, i 真正的道路是城市 A_i 和城市 B_i 是平局, 仅当C_i 。帕肯王国的所有城镇均可通过公路到达。
帕肯王国的国王K已经改变,所以 Q 我告诉你城市的组别,每组都是 (S_i,T_i)(1 \leq i \leq Q) 关于城市 S_i 从城市出发 转至 T_i 的道路上的平均重量。作为仆人,请代表国王询问国王的需要。 如果元素数量为偶数,则
(2023/03/27 15:36追記:) 数列 X 的中位数是元素按升序排列的列。 当 X_1,X_2,...,X_n 时,(X_{n/2} + X_{n/2+1}) / 2 中定义。 如果数字为奇数,则元素按升序排列的列是 X_1,X_2,...,X_n 时,X_{(n+1)/2} 中定义。
制約
- 2 \leq N \leq 10^5
- 1 \leq A_i,B_i \leq N (1 \leq i \leq N-1)
- 2 \leq C_i \leq 2 \times 10^5 (1 \leq i \leq N-1)
- C_i 均为偶数(1 \leq i \leq N-1)
- 1 \leq Q \leq 5 \times 10^4
- 1 \leq S_i,T_i \leq N (1 \leq i \leq Q)
- S_i \neq T_i (1 \leq i \leq Q)
入力
输入是按以下格式从标准输入给出的。
N
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_{N-1} B_{N-1} C_{N-1}
Q
S_1 T_1
S_2 T_2
\vdots
S_Q T_Q
出力
Q 行。 在i 在线 i 请输出要为该集合找到的值。
入力例 1
5 1 2 50 2 3 100 1 4 20 4 5 30 1 3 5
出力例 1
40
入力例 2
3 1 2 100 2 3 50 1 1 3
出力例 2
75