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 $ へのパス上の道路の重みの中央値を求めたいと言いました。召使のあなたは K 国王の代わりに王が求めたい値を求めてあげてください。 (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} $ で定義されます。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 組目についての求めるべき値を出力してください。

### Constraints - $ 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) $