AT_abc070_d [ABC070D] Transit Tree Path

给定一棵有 $N$ 个顶点的树。 树是一种特殊的图，如果顶点数为 $N$，则边的数量为 $N-1$，且没有环的连通图。 第 $i$ 条边（$1\leq i\leq N-1$）连接顶点 $a_i$ 和顶点 $b_i$，距离为 $c_i$。 另外，给定 $Q$ 个询问和一个整数 $K$。 - 对于第 $j$ 个询问（$1\leq j\leq Q$），请你求出从顶点 $x_j$ 出发，经过顶点 $K$，到达顶点 $y_j$ 的最短路径长度。

输入按以下格式从标准输入读入。 > $N$ > $a_1$ $b_1$ $c_1$ > $a_2$ $b_2$ $c_2$ > $\vdots$ > $a_{N-1}$ $b_{N-1}$ $c_{N-1}$ > $Q$ $K$ > $x_1$ $y_1$ > $x_2$ $y_2$ > $\vdots$ > $x_Q$ $y_Q$

对于每个询问，输出一行答案。 第 $j$ 行输出第 $j$ 个询问的答案。

### 限制条件 - $3\leq N\leq 10^5$ - $1\leq a_i,b_i\leq N\ (1\leq i\leq N-1)$ - $1\leq c_i\leq 10^9\ (1\leq i\leq N-1)$ - 给定的图保证是一棵树。 - $1\leq Q\leq 10^5$ - $1\leq K\leq N$ - $1\leq x_j,y_j\leq N\ (1\leq j\leq Q)$ - $x_j\neq y_j\ (1\leq j\leq Q)$ - $x_j\neq K, y_j\neq K\ (1\leq j\leq Q)$ ### 样例解释 1 对于给定的 $3$ 个询问，最短路径如下： - 第 $1$ 个询问：顶点 $2\to 1\to 2\to 4$，距离 $1+1+1=3$ - 第 $2$ 个询问：顶点 $2\to 1\to 3$，距离 $1+1=2$ - 第 $3$ 个询问：顶点 $4\to 2\to 1\to 3\to 5$，距离 $1+1+1+1=4$ ### 样例解释 2 对于所有询问，最短路径都必须经过顶点 $K=2$。 由 ChatGPT 4.1 翻译