AT_pakencamp_2022_day1_j An Unusual King in Paken Kingdom

在パ研王国中，有 $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, \ldots, X_n$，中位数定义为 $(X_{n/2} + X_{n/2+1}) / 2$；元素个数为奇数时，仍按升序排列为 $X_1, X_2, \ldots, X_n$，中位数定义为 $X_{(n+1)/2}$。

输入按以下格式从标准输入读入。 > $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$ 组询问的结果。

### 数据范围 - $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)$ 由 ChatGPT 5 翻译