310660: CF1866K. Keen Tree Calculation

K. Keen Tree Calculationtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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.

Input

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$).

Output

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.

ExamplesInput

7
5 1 2
1 4 2
3 4 1
2 5 3
6 1 6
4 7 2
2
4 3
3 2

Output

18
11

Input

3
1 2 1000000000
2 3 1000000000
1
2 1000000000

Output

2000000000000000000

Note

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$.

题目大意：
给定一棵N个顶点和N-1条边的树，每条边连接两个顶点并具有长度W。主人Chaneka会问Q个问题，每个问题格式如下：如果包含顶点X的每条边的长度都乘以K，那么树的直径是多少？每个问题都是独立的，树的直径是树中任意两个不同顶点之间的最大可能距离。

输入数据格式：
第一行包含一个整数N（2≤N≤10^5）——树的顶点数。
接下来的N-1行，每行包含三个整数U、V和W（1≤U,V≤N；1≤W≤10^9）——连接顶点U和V的边，长度为W。这些边构成一棵树。
第N+1行包含一个整数Q（1≤Q≤10^5）——问题数。
接下来的Q行，每行包含两个整数X和K，如题目所述（1≤X≤N；1≤K≤10^9）。

输出数据格式：
输出Q行，每行一个整数。第j行的整数代表第j个问题的树的直径。

示例：
输入：
7
5 1 2
1 4 2
3 4 1
2 5 3
6 1 6
4 7 2
2
4 3
3 2

输出：
18
11

注意：
在第一个示例中，未修改的树的直径是18，因为顶点6和顶点7之间的最大距离是6+6+6=18。在第二个示例中，修改后的树的直径是11，因为顶点2和顶点6之间的最大距离是3+2+6=11。题目大意： 给定一棵N个顶点和N-1条边的树，每条边连接两个顶点并具有长度W。主人Chaneka会问Q个问题，每个问题格式如下：如果包含顶点X的每条边的长度都乘以K，那么树的直径是多少？每个问题都是独立的，树的直径是树中任意两个不同顶点之间的最大可能距离。 输入数据格式： 第一行包含一个整数N（2≤N≤10^5）——树的顶点数。 接下来的N-1行，每行包含三个整数U、V和W（1≤U,V≤N；1≤W≤10^9）——连接顶点U和V的边，长度为W。这些边构成一棵树。 第N+1行包含一个整数Q（1≤Q≤10^5）——问题数。 接下来的Q行，每行包含两个整数X和K，如题目所述（1≤X≤N；1≤K≤10^9）。 输出数据格式： 输出Q行，每行一个整数。第j行的整数代表第j个问题的树的直径。 示例： 输入： 7 5 1 2 1 4 2 3 4 1 2 5 3 6 1 6 4 7 2 2 4 3 3 2 输出： 18 11 注意： 在第一个示例中，未修改的树的直径是18，因为顶点6和顶点7之间的最大距离是6+6+6=18。在第二个示例中，修改后的树的直径是11，因为顶点2和顶点6之间的最大距离是3+2+6=11。