← 返回题目列表

Codeforces · 526/G

G. 蜘蛛邪恶计划

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

蜘蛛是 Om Nom 的宿敌。他们和他一样喜欢吃糖果,这就是为什么他们一直试图让怪物远离他最喜欢的糖果。他们想出了一个邪恶的计划来陷害 Om Nom。

让我们考虑一个由 n 个节点和连接节点的 n - 1 根绳索组成的绳索结构。该结构是连接的,因此,绳索和节点形成一棵树。所形成结构的每根绳索都与其长度相关。糖果与结构的节点 x 相连。 Om Nom 真的很想吃这个糖果。

y 蜘蛛正试图阻止他这样做。他们决定将糖果和结构的某些部分缠成网,从而将糖果附着在绳索结构的尽可能大的部分上。

每个蜘蛛都可以用自己的网覆盖任意两个节点 a 和 b 之间路径上的所有绳索。因此,y 个蜘蛛可以覆盖一组绳索,该组绳索是给定树中 y 条路径的并集。这些 y 路径可以彼此任意相交。蜘蛛希望满足以下条件:

- 包含糖果的节点与至少一根覆盖有网的绳子相邻
- 被网覆盖的绳索形成一个连接的结构(用网覆盖与糖果没有连接的绳索有什么想法?)
- 被网覆盖的绳索的总长度尽可能大

蜘蛛们还没有决定将糖果绑在结构的哪个节点上,以及有多少只蜘蛛将用网覆盖结构,所以他们要求你帮助他们。帮助他们计算多个 x 和 y 值的最佳计划。

输入

第一行包含数字 n 和 q (1 ≤ n, q ≤ 105) — 结构中的节点数以及蜘蛛想问您的问题数。

接下来的 n - 1 行确定绳索结构。第i行包含三个整数ui、vi、li(1≤ui、vi≤n、ui≠vi、1≤li≤1000),表明节点ui和vi之间有一条长度为li的绳子。

接下来的 q 行描述了蜘蛛的问题。由于他们希望您在线回答他们的问题,因此他们以特殊的方式编码了他们的消息。

接下来的 q 行包含两个数字 xi、yi。在蜘蛛的第一个问题中x = x1,y = y1。

要计算蜘蛛第 i (2 ≤ i ≤ q) 个问题中的 x 和 y 值,您需要使用以下公式:

$$x = ((x_i + Ans_{i-1} - 1) \bmod n) + 1$$

$$y = ((y_i + Ans_{i-1} - 1) \bmod n) + 1$$

其中 Ansi - 1 是第 (i - 1) 个问题答案中网覆盖的绳索的总长度。

以下不等式成立:1 ≤ xi, yi ≤ n。

输出

对于蜘蛛的每个问题,在单独的行上打印一个整数 Ansi — 最佳计划中被网覆盖的绳索的总长度。

示例

输入 #1

6 3
1 2 2
2 3 2
3 4 2
4 6 1
3 5 10
3 1
2 5
1 1

输出 #1

14
13
17