最近 scx 迷上了一个叫做割绳子 3 的隔膜 (game)。
这个游戏的要求是你要扮演蜘蛛去吃掉一个糖果。
那是一个像割绳子游戏一样的界面，共有 V 个节点，和 V - 1 条有长度的边，组成了一个树状结构。第 i 关，糖果在第 xi 个节点上，共有 yi 只蜘蛛。
每只蜘蛛可以用它的网去覆盖任意不同两点 a 和 b 之间的路径，因此，y 只蜘蛛可以覆盖 y 条树上路径的并。当然，不同的蜘蛛选择的路径可以相交。并且，具有如下的要求：
可是蜘蛛们好像都非常智障，所以它们需要你帮忙求出最大值。
第一行包含两个整数 V 和 q，分别代表节点数和关卡数。
接下来的 V - 1 行，每行三个正整数 u, v, l，代表节点 u 和节点 v 之间有一条长度为 l 的边。
接下来的 q 行，每行两个数 xi', yi'，你需要将它们偏移 "上一次的输出答案" 个单位后对 V 取模 (0 看做 V)，记成 xi 和 yi，代表这一关糖果在节点 xi 上，共有 yi 只蜘蛛。
对于每一个关卡，输出一行，包含一个正整数，表示边的长度总和的最大值。
首先，可以比较轻易地看出，每条路径都是从一个叶子走到另一个叶子的。
如果不考虑糖果的存在，我们可以作如下分析：
若 y = 1，则显然是这个树的直径 (边权最大)。
若 y = 2，可以看出是直径加上一个最大的分支。
若 y = 3，可以看出是 y = 2 的答案加上剩下分支中最大的分支。
……
所以，以直径的一个端点为根建立有根树，然后进行树链剖分，每次找最长的链，一共找 2y - 1 条，这样贪心答案就是最优的。
(scx: 如果找出的答案不包括 x 呢？)
这就是这道题作为 codeforces g 题的原因，这个其实是不怎么好分析的。
首先，考察 x 所在的重链，如果它的重链 C 的排名 rank(C)，如果 rank(C) < 2y - 1，则答案就是这个贪心的答案，否则，可以这么处理：
首先，重链 C 是一定要选的，所以，必定要在前 2y - 1 条重链中扔一条，这有两种情况：
Case 1: 丢弃第 2y - 1 条重链，加入重链 C。
Case 2: 点 x 到根 root 的路径 path(x) 上，属于前 2y - 1 条重链的最深的那个节点，记作 δ，那么 δ 节点一定属于一条重链 F，且 rank(F) ≤ 2y - 1，可以将重链 F 中，在 δ 节点以下的部分丢弃，和节点 x 相连。
(scx: 可是 y = 1 的情况可能最优解不包含根呀！)
说得没错。因此，我们要对 y = 1 的情况进行特判，特判过程很简单：
因为只有一条链，所以同样也可以找到这样一个 δ，使得它是 path(x) 上，属于主重链 (直径) F 的最深的那个节点。于是 δ 将 F 分成两段 F0 和 F1 (不妨设 root 节点属于 F0)，那么 F1 的除了 δ 外的另一个端点一定是直径的另一个端点。
因此，可以将 F0 和 F1 的长度取一个 max，然后加上 x 点到 δ 的长度。
(scx: 时空复杂度有多大？)
空间的话用一个邻接表，基本线性不成问题，时间的话，直径 + 重链剖分可以用 2 ~ 3 次 dfs 解决，对于每个询问，由于链数与 同阶，然后可以求一下重链的前缀和，时间的话最坏也就是
的。
(ps: 以下内容为 2019.12.7 更新)
#include <bits/stdc++.h>
using std::cin;
using std::cout;
const int N = 100054, M = N * 2, LN = 18;
struct edge {
int u, v, w;
edge (int u0 = 0, int v0 = 0, int w0 = 0) : u(u0), v(v0), w(w0) {}
} e[M];
int n, q, E = 0, root;
int first[N], next[M];
int p[N], dep[N], f[N], prf[N], top[N];
int Q[LN][N];
int cnt_chain, chain[N], len[N], sum[N], rank[N], grd[N];
inline void addedge(int u, int v, int w) {
e[++E] = edge(u, v, w), next[E] = first[u], first[u] = E;
e[++E] = edge(v, u, w), next[E] = first[v], first[v] = E;
}
inline void up(int &x, const int y) {x < y ? x = y : 0;}
inline void down(int &x, const int y) {x > y ? x = y : 0;}
inline int min(const int x, const int y) {return x < y ? x : y;}
void dfs_diam(int x, int px = 0) {
int i, y;
if (dep[x] > dep[root]) root = x;
for (i = first[x]; i; i = next[i])
if ((y = e[i].v) != px)
dep[y] = dep[x] + e[i].w, dfs_diam(y, x);
}
void dfs_len(int x) {
int i, y, &z = prf[x], best = -1;
for (i = first[x]; i; i = next[i])
if ((y = e[i].v) != p[x])
p[y] = x, dep[y] = dep[x] + e[i].w,
dfs_len(y), up(f[x], f[y] + e[i].w),
f[y] + e[i].w > best && (z = y, best = f[y] + e[i].w);
}
void dfs_lsd(int x, int r) {
int i, y; top[x] = r;
if (x == r)
for (Q[0][x] = top[p[x]], i = 0; Q[i][x]; ++i) Q[i + 1][x] = Q[i][ Q[i][x] ];
grd[x] = (r == root ? x : grd[ p[x] ]);
if (!prf[x]) {len[r] += dep[x] - dep[r]; return;}
dfs_lsd(prf[x], r);
for (i = first[x]; i; i = next[i])
if (!top[y = e[i].v])
len[y] = e[i].w, dfs_lsd(y, y);
}
int jump_until(int x, int r) {
for (int i = LN - 1; i >= 0; --i)
if (Q[i][x] && rank[Q[i][x]] >= r) x = Q[i][x];
return x;
}
int main() {
int i, u, v, w, m, ans = 0;
std::ios::sync_with_stdio(false), cin.tie(NULL);
cin >> n >> q;
for (i = 1; i < n; ++i) cin >> u >> v >> w, addedge(u, v, w);
dfs_diam(1), dep[root] = 0, dfs_len(root), dfs_lsd(root, root);
for (i = 1; i <= n; ++i) if (top[i] == i) chain[cnt_chain++] = i;
std::sort(chain, chain + cnt_chain, [] (const int x, const int y) {return len[x] > len[y];});
for (i = 0; i < cnt_chain; ++i) rank[ chain[i] ] = i, sum[i + 1] = sum[i] + len[ chain[i] ];
for (; q; --q) {
cin >> v >> m, ans %= n;
v = (v + ans - 1) % n + 1, m = (m + ans - 1) % n * 2 + 1;
if (rank[ top[v] ] < m) ans = sum[min(m, cnt_chain)];
else
u = p[ jump_until(top[v], m) ],
up(ans = sum[m - 1], sum[m] - min(f[u], dep[ grd[u] ])),
ans += dep[v] - dep[u] + f[v];
cout << ans << '\n';
}
return 0;
}
结果代码写了 167 行，4 KB，貌似是全 OJ 上最长的。
坑1：这道题的情况比较多，需要特判 y = 1 的情况和扔链的两种 Case，非常考验代码功底。
坑2：在询问前，可以求一下所有链的前缀和，然后运行的时候速度可以快很多，否则很容易 TLE。
坑3：还有，我的邻接表姿势非常奇怪，我也不知道为什么......