← 返回题目列表

Codeforces · 1866/K

K. 敏锐的树计算

中文机器翻译题面 查看原题

有一个由 $$$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$$$。