CF1866K.Keen Tree Calculation

There is a tree of $N$ vertices and $N-1$ edges. The $i$-th edge connects vertices $U_i$ and $V_i$ and has a length of $W_i$.

Chaneka, the owner of the tree, asks you $Q$ times. For the $j$-th question, the following is the question format:

• $X_j$ $K_j$ – If each edge that contains vertex $X_j$ has its length multiplied by $K_j$, what is the diameter of the tree?

Notes:

• Each of Chaneka's question is independent, which means the changes in edge length do not influence the next questions.
• The diameter of a tree is the maximum possible distance between two different vertices in the tree.

有一棵包含 $N$ 个顶点和 $N-1$ 条边的树。第 $i$ 条边连接顶点 $U_i$ 和 $V_i$，长度为 $W_i$。

树的所有者 Chaneka 向你提出 $Q$ 个问题。对于第 $j$ 个问题，其格式如下：

• $X_j$ $K_j$ —— 若将所有与顶点 $X_j$ 相连的边的长度均乘以 $K_j$，则该树的直径是多少？

注意事项：

• Chaneka 的每个问题相互独立，即边长的修改不会影响后续问题。
• 树的直径是指树中任意两个不同顶点之间可能的最大距离。

The first line contains a single integer $N$ ($2\leq N\leq10^5$) — the number of vertices in the tree.

The $i$-th of the next $N-1$ lines contains three integers $U_i$, $V_i$, and $W_i$ ($1 \leq U_i,V_i \leq N$; $1\leq W_i\leq10^9$) — an edge that connects vertices $U_i$ and $V_i$ with a length of $W_i$. The edges form a tree.

The $(N+1)$-th line contains a single integer $Q$ ($1\leq Q\leq10^5$) — the number of questions.

The $j$-th of the next $Q$ lines contains two integers $X_j$ and $K_j$ as described ($1 \leq X_j \leq N$; $1 \leq K_j \leq 10^9$).

第一行包含一个整数 $N$（$2\leq N\leq10^5$）——树中顶点的数量。

接下来的 $N-1$ 行中，第 $i$ 行包含三个整数 $U_i$、$V_i$ 和 $W_i$（$1 \leq U_i,V_i \leq N$；$1\leq W_i\leq10^9$）——表示一条连接顶点 $U_i$ 与 $V_i$、长度为 $W_i$ 的边。这些边构成一棵树。

第 $N+1$ 行包含一个整数 $Q$（$1\leq Q\leq10^5$）——询问的数量。

接下来的 $Q$ 行中，第 $j$ 行包含两个整数 $X_j$ 和 $K_j$（如题面所述）（$1 \leq X_j \leq N$；$1 \leq K_j \leq 10^9$）。

Output $Q$ lines with an integer in each line. The integer in the $j$-th line represents the diameter of the tree on the $j$-th question.

输出 $Q$ 行，每行一个整数。第 $j$ 行的整数表示第 $j$ 个询问中树的直径。

In the first example, the following is the tree without any changes.

The following is the tree on the $1$-st question.

The maximum distance is between vertices $6$ and $7$, which is $6+6+6=18$, so the diameter is $18$.

The following is the tree on the $2$-nd question.

The maximum distance is between vertices $2$ and $6$, which is $3+2+6=11$, so the diameter is $11$.

在第一个例子中，以下是未作任何修改的树：

以下是第 $1$ 个询问时的树：

最大距离出现在顶点 $6$ 与 $7$ 之间，其值为 $6+6+6=18$，因此直径为 $18$。

以下是第 $2$ 个询问时的树：

最大距离出现在顶点 $2$ 与 $6$ 之间，其值为 $3+2+6=11$，因此直径为 $11$。