CF526G Spiders Evil Plan

题目描述

蜘蛛是 Om Nom 的老对手。它们和他一样喜欢吃糖果，这就是为什么它们总是试图阻止这只怪物靠近他最喜欢的糖果。现在，它们想出了一个邪恶的计划来陷害 Om Nom。

设想有一个由 $n$ 个结点组成的绳索结构，这 $n$ 个结点通过 $n-1$ 根绳索连接起来。该结构是连通的，因此这些绳索和结点一起构成了一棵树。每根绳索都有一个与之相关的长度。现在，有一颗糖果被系在了结构中的结点 $x$ 上，Om Nom 非常想吃到这颗糖果。

这时有 $y$ 只蜘蛛想要阻止他。它们决定用蜘蛛网将糖果和部分结构缠绕起来，从而把糖果系在尽可能大的绳索结构上。

每只蜘蛛都能用蜘蛛网覆盖任意两个结点 $a$ 和 $b$ 之间路径上的所有绳索。因此，$y$ 只蜘蛛一共可以覆盖树上 $y$ 条路径的所有绳索。这 $y$ 条路径之间可以任意相交。蜘蛛们希望满足以下条件：

• 包含糖果的结点至至少一根被网覆盖的绳索相邻。
• 所有被网覆盖的绳索必须构成一个连通结构（毕竟覆盖和糖果无关的绳索毫无意义）。
• 被网覆盖的绳索的总长度要尽可能大。

蜘蛛们还没决定将糖果系在哪个结点，也还没决定将由几只蜘蛛来缠绕结构，于是它们请你帮忙计算多组 $x$ 和 $y$ 的最优方案。

请你帮助蜘蛛们，计算出多组 $x$、$y$ 的最优覆盖方案。

输入格式

第一行包含两个整数 $n$ 和 $q$（$1\leq n, q\leq 10^5$），表示结构中的结点数和问题数。

接下来的 $n-1$ 行描述了绳索结构，第 $i$ 行包含三个整数 $u_i, v_i, l_i$（$1\leq u_i, v_i\leq n$，$u_i\neq v_i$，$1\leq l_i\leq 1000$），表示结点 $u_i$ 与结点 $v_i$ 之间有一根长度为 $l_i$ 的绳索。

接下来 $q$ 行描述了蜘蛛们的问题。由于它们要求你在线回答问题，所以它们用特殊方式对消息进行了编码。

接下来每一行包含两个整数 $x_i, y_i$。蜘蛛们的第一个问题中 $x = x_1, y = y_1$。

对于第 $i$（$2\leq i\leq q$）次提问，$x, y$ 的取值需要使用如下公式计算：

其中 $Ans_{i-1}$ 是你对第 $i-1$ 个问题所求得的最优覆盖方案的被覆盖绳索总长度。

保证有 $1\leq x_i, y_i \leq n$。

输出格式

对于每一个问题，每行输出一个整数 $Ans_i$，表示对应最优方案下被网覆盖的绳索总长度。

输入输出样例 #1

输入 #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

说明/提示

由 ChatGPT 5 翻译