有一个由 $$$N$$$ 个顶点和 $$$N-1$$$ 个边组成的树。第 $$$i$$$ 条边连接顶点 $$$U_i$$$ 和 $$$V_i$$$,长度为 $$$W_i$$$。
Chaneka,树的主人,问你 $$$Q$$$ 次。对于第 $$$j$$$ 题,问题格式如下:
- $$$X_j$$$ $$$K_j$$$ – 如果包含顶点 $$$X_j$$$ 的每条边的长度乘以 $$$K_j$$$,则树的直径是多少?
注意:
- Chaneka 的每个问题都是独立的,这意味着边长的变化不会影响接下来的问题。
- 树的直径是树中两个不同顶点之间的最大可能距离。
输入
第一行包含一个整数 $$$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$$$)。
输出
输出 $$$Q$$$ 行,每行一个整数。第 $$$j$$$ 行中的整数表示第 $$$j$$$ 问题上的树的直径。
示例
输入 #1
7 5 1 2 1 4 2 3 4 1 2 5 3 6 1 6 4 7 2 2 4 3 3 2
输出 #1
18 11
输入 #2
3 1 2 1000000000 2 3 1000000000 1 2 1000000000
输出 #2
2000000000000000000
注意
在第一个示例中,以下是没有任何更改的树。
以下是 $$$1$$$-st 问题的树。
最大距离位于顶点 $$$6$$$ 和 $$$7$$$ 之间,即 $$$6+6+6=18$$$,因此直径为 $$$18$$$。
以下是 $$$2$$$-nd 问题的树。
最大距离是顶点 $$$2$$$ 和 $$$6$$$ 之间的距离,即 $$$3+2+6=11$$$,因此直径为 $$$11$$$。