题解 CF526G 【Spiders Evil Plan】
xht
2020-01-08 22:09:54
> [CF526G Spiders Evil Plan](https://codeforces.com/contest/526/problem/G)
## 题意
- 给定一棵 $n$ 个节点的无根树，每条边有边权。
- 有 $q$ 次询问，每次询问给出 $x,y$，你需要选择 $y$ 条树上的路径，使这些路径形成一个包含 $x$ 的连通块，且连通块中包含的边权和最大。
- $n, q \le 10^5$，强制在线。
## 题解
设叶子个数为 $k$。
首先，若 $2y \ge k$，则 $y$ 条路径可以直接覆盖整棵树。
否则，每条路径的两端一定是两个叶子，即一共要选择 $2y$ 个叶子。
考虑以 $x$ 为根时，我们如何选择叶子呢？
注意到，如果一个节点 $x$ 的子树中有叶子被选了，那么 $x$ 所在长链包含的叶子一定也被选择了。
于是对于每一个叶子，它的贡献实际上等于它到它所在的长链的顶点的父亲的距离。
那么我们就可以按贡献从大到小选择叶子了。
但如果每次询问都以 $x$ 为根进行一次 $\mathcal O(n)$ 的长链剖分，复杂度显然太高。
但又可以注意到，在树上经过点 $x$ 的最长链一定经过直径的某一端。
于是我们只需要以直径两端的两个点为根分别做一次就好了。由于直径两端一定是叶子，因此这个时候我们只应该选择 $2y-1$ 个叶子。
但这么做有个问题，如果选择的叶子组成的连通块并不包括 $x$ 怎么办？
可以发现只有两种情况：
1. 将贡献最小的长链去掉并加入 $x$ 所在长链。
2. 是找到离 $x$ 最近的长链将下半部分替换成 $x$ 所在长链。
对于两种情况，都需要向上找到第一个不在贡献内的点。如果暴力跳长链，在边权都为 $1$ 的情况下是可行的，因为这样暴力跳的复杂度为 $\mathcal O(\sqrt n)$。
但这道题边带权，因此暴力跳的复杂度为 $\mathcal O(n)$，所以还需要倍增往上找，复杂度为 $\mathcal O(\log n)$。
总时间复杂度 $\mathcal O((n + q) \log n)$。
## 代码
```cpp
const int N = 1e5 + 7;
int n, q, k, s, ans;
vector <pi> e[N];
struct T {
int rt, f[N][21], g[N][21], d[N], dep[N], son[N], top[N], rnk[N];
int l[N], r[N], s[N], t;
void dfs1(int x, int fa) {
for (pi o : e[x])
if (o.fi != fa) d[o.fi] = d[x] + o.se, dfs1(o.fi, x);
}
void dfs2(int x) {
for (pi o : e[x])
if (o.fi != f[x][0]) {
f[o.fi][0] = x, g[o.fi][0] = o.se;
for (int i = 0; f[o.fi][i]; i++)
f[o.fi][i+1] = f[f[o.fi][i]][i],
g[o.fi][i+1] = g[o.fi][i] + g[f[o.fi][i]][i];
d[o.fi] = d[x] + o.se, dfs2(o.fi);
if (dep[o.fi] + o.se > dep[x])
dep[x] = dep[o.fi] + o.se, son[x] = o.fi;;
}
for (pi o : e[x])
if (o.fi != f[x][0] && o.fi != son[x])
s[l[++t]=o.fi] = dep[o.fi] + o.se;
}
void getrt(int x) {
dfs1(x, 0), rt = x;
for (int i = 1; i <= n; i++) if (d[i] > d[rt]) rt = i;
d[rt] = 0, dfs2(rt), s[l[++t]=rt] = dep[rt];
sort(l + 1, l + t + 1, [&](int i, int j) { return s[i] > s[j]; });
for (int i = 1; i <= t; i++) r[i] = r[i-1] + s[l[i]];
for (int i = 1; i <= t; i++) {
int x = l[i], p = x;
while (x) top[x] = p, rnk[x] = i, x = son[x];
}
}
inline int plan1(int x, int y) {
int z = dep[x];
for (int i = 20; ~i; i--)
if (rnk[f[x][i]] >= y) z += g[x][i], x = f[x][i];
return r[y-1] + z + g[x][0];
}
inline int plan2(int x, int y) {
int z = dep[x];
for (int i = 20; ~i; i--)
if (rnk[f[x][i]] > y) z += g[x][i], x = f[x][i];
return r[y] - dep[f[x][0]] + z + g[x][0];
}
inline int ask(int x, int y) {
y = 2 * y - 1;
return rnk[x] <= y ? r[y] : max(plan1(x, y), plan2(x, y));
}
} t[2];
int main() {
rd(n), rd(q);
for (int i = 1, x, y, z; i < n; i++)
rd(x), rd(y), rd(z),
e[x].pb(mp(y, z)), e[y].pb(mp(x, z)), s += z;
for (int i = 1; i <= n; i++) k += e[i].size() == 1u;
t[0].getrt(1), t[1].getrt(t[0].rt);
for (int i = 1, x, y; i <= q; i++)
rd(x), rd(y),
x = (x + ans - 1) % n + 1, y = (y + ans - 1) % n + 1,
print(ans = 2 * y >= k ? s : max(t[0].ask(x, y), t[1].ask(x, y)));
return 0;
}
```