CF526G Spiders Evil Plan 题解

CF526G Spiders Evil Plan

题意

• 给定一棵 $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)$。

代码

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;
}