CF516D Drazil and Morning Exercise 题解

CF516D Drazil and Morning Exercise

题意

• 给定一棵 $n$ 个点的树，边有边权。
• 定义 $f_x = \max_{i=1}^n \text{dist}(x,i)$。
• $q$ 次询问最大的满足 $\max_{x \in s} f_x - \min_{x \in s} f_x \le l$ 的连通块 $s$ 包含的点数。
• $n \le 10^5$，$q \le 50$。

题解

先把 $f$ 线性求出来，然后由大到小双指针扫一遍，发现只会合并，因此并查集维护连通性即可，时间复杂度 $\mathcal O(n \log n + qn\alpha(n))$。

代码

const int N = 1e5 + 7;
int n, q, fa[N], s[N], v[N], ans;
ll m, f[N][2], g[N];
pair< ll, int > p[N];
vector< pi > e[N];

void dfs1(int x, int fa) {
	for (ui i = 0; i < e[x].size(); i++) {
		int y = e[x][i].fi;
		if (y == fa) continue;
		dfs1(y, x);
		ll z = f[y][0] + e[x][i].se;
		if (z > f[x][1]) f[x][1] = z;
		if (z > f[x][0]) swap(f[x][0], f[x][1]);
	}
}

void dfs2(int x, int fa) {
	for (ui i = 0; i < e[x].size(); i++) {
		int y = e[x][i].fi;
		if (y == fa) continue;
		int z = e[x][i].se;
		g[y] = max(g[x], f[y][0] + z == f[x][0] ? f[x][1] : f[x][0]) + z;
		dfs2(y, x);
	} 
}

int get(int x) {
	return x == fa[x] ? x : (fa[x] = get(fa[x]));
}

inline void merge(int x, int y) {
	if (x == y) return;
	if (s[x] > s[y]) swap(x, y);
	fa[x] = y, s[y] += s[x];
	ans = max(ans, s[y]);
}

int main() {
	rd(n);
	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));
	dfs1(1, 0);
	dfs2(1, 0);
	for (int i = 1; i <= n; i++) p[i] = mp(max(f[i][0], g[i]), i);
	sort(p + 1, p + n + 1);
	reverse(p + 1, p + n + 1);
	rd(q);
	while (q--) {
		rd(m), ans = 1;
		for (int i = 1; i <= n; i++) fa[i] = i, s[i] = 1, v[i] = 0;
		for (int l = 1, r = 0; l <= n; l++) {
			while (r < n && p[l].fi - p[r+1].fi <= m) {
				int x = p[++r].se;
				v[x] = 1;
				for (ui i = 0; i < e[x].size(); i++) {
					int y = e[x][i].fi;
					if (v[y]) merge(get(x), get(y));
				}
			}
			--s[get(p[l].se)], v[get(p[l].se)] = 0;
		}
		print(ans);
	}
	return 0;
}