← 返回题目列表

AtCoder · pakencamp_2022_day1_j

J. 帕肯王国的不寻常国王

中文机器翻译题面 查看原题

配点 : 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