CF516D Drazil and Morning Exercise【并查集，结论】

题目描述：一棵\(n\)个点的树，设\(d(u)=\max_{v\in V}\text{dis}(u,v)\)，每次询问一个数\(l\)，求一个最大的联通子图\(L\)，使得\(\forall u,v\in L,|d(u)-d(v)|\leq l\)。输出\(|L|\).

数据范围：\(n\leq 10^5,w\leq 10^6,l\leq 10^{11},q\leq 50\).

在我的博客阅读更佳

首先我们要计算出\(d(u)\)，这个我们可以把\(d(u)\)拆成\(dep_u+\max_{v\in V}(dep_v-2dep_{\text{lca}(u,v)})\)。枚举当前dfs到的是\(x\)作为lca，那么\(x\)的对子树\(v\)的点贡献为\(\max_{v\in tr(x),v\notin tr(v)}dep_v-2dep_x\)，对自己的贡献为\(\max_{v\in tr(x)}dep_v-2dep_x\)。后者先预处理子树深度最大值，前者可以对于每个儿子\(v\)，排成一排之后计算前缀最大值和后缀最大值。时间复杂度\(O(n)\)。

然后我们会发现一个事情，就是以\(d(u)\)最小的点（中心）为根，\(\forall v\in tr(x),d(v)\ge d(x)\)。

证明：我们只需要证明\(u\)的每个儿子\(x\)满足原命题，那么可以归纳证明所有点都满足。

如果\(x\)的最长路不经过\(v\)，那么\(v\)的路径可以经过\(x\)，然后走\(x\)的最长路，即\(d(v)>d(x)\)。
如果\(x\)的最长路经过\(v\)，那么\(u\)的路径可以经过\(x\)，然后走\(x\)的最长路，即\(d(u)>d(x)\)，矛盾，所以不可能。

现在我们知道，我们可以用two-pointer的方法，按\(d(u)\)从大到小枚举\(u\)，然后将\(d(x)>d(u)+l\)的点全部删除，而且删除的点并不会影响连通性（因为更远离中心），所以可以用并查集维护联通块大小。

时间复杂度\(O(n\log n+qn\alpha(n))\)，莫名其妙跑得比“莫名其妙跑得比并查集老哥们快”的老哥快。

#include<bits/stdc++.h>

#define Rint register int

using namespace std;

typedef long long LL;

const int N = 100003;

int n, q, head[N], to[N << 1], nxt[N << 1], w[N << 1], id[N];

inline void add(int a, int b, int c){

	static int cnt = 0;

	to[++ cnt] = b; nxt[cnt] = head[a]; head[a] = cnt; w[cnt] = c;

}

int fa[N], nod[N], tot;

LL dep[N], len[N], pre[N], suf[N], tag[N], d[N];

inline void dfs(int x){

	len[x] = dep[x];

	for(Rint i = head[x];i;i = nxt[i])

		if(to[i] != fa[x]){

			dep[to[i]] = dep[x] + w[i]; fa[to[i]] = x;

			dfs(to[i]);

			len[x] = max(len[x], len[to[i]]);

		}

	tot = 0;

	for(Rint i = head[x];i;i = nxt[i])

		if(to[i] != fa[x]) nod[++ tot] = to[i];

	pre[0] = suf[tot + 1] = dep[x];

	for(Rint i = 1;i <= tot;i ++) pre[i] = max(pre[i - 1], len[nod[i]]);

	for(Rint i = tot;i;i --) suf[i] = max(suf[i + 1], len[nod[i]]);

	for(Rint i = 1;i <= tot;i ++){

		tag[nod[i]] = max(tag[nod[i]], max(pre[i - 1], suf[i + 1]) - 2 * dep[x]);

		d[nod[i]] = max(d[nod[i]], max(pre[i - 1], suf[i + 1]) - 2 * dep[x]);

	}

	d[x] = max(d[x], len[x] - 2 * dep[x]);

}

inline void push(int x){

	for(Rint i = head[x];i;i = nxt[i]) if(to[i] != fa[x]){

		tag[to[i]] = max(tag[to[i]], tag[x]);

		d[to[i]] = max(d[to[i]], tag[x]);

	}

	for(Rint i = head[x];i;i = nxt[i]) if(to[i] != fa[x]) push(to[i]);

}

inline bool cmp(int a, int b){return d[a] < d[b] || d[a] == d[b] && a < b;}

int f[N], siz[N];

inline int getfa(int x){

	return f[x] == x ? x : f[x] = getfa(f[x]);

}

inline void merge(int u, int v){

	u = getfa(u); v = getfa(v);

	if(u != v){

		if(siz[u] < siz[v]) swap(u, v);

		siz[u] += siz[v]; f[v] = u;

	}

}

int main(){

	scanf("%d", &n);

	for(Rint i = 1;i < n;i ++){

		int a, b, c;

		scanf("%d%d%d", &a, &b, &c);

		add(a, b, c); add(b, a, c);

	}

	memset(len, 0x80, sizeof len);

	dfs(1); push(1);

	for(Rint i = 1;i <= n;i ++) d[i] += dep[i], id[i] = i;

	sort(id + 1, id + n + 1, cmp);

	memset(fa, 0, sizeof fa); fa[id[1]] = 1;

	for(Rint i = 2;i <= n;i ++)

		for(Rint j = head[id[i]];j && !fa[id[i]];j = nxt[j])

			if(fa[to[j]]) fa[id[i]] = to[j];

	scanf("%d", &q);

	while(q --){

		LL l; scanf("%lld", &l);

		int ans = 0;

		for(Rint i = 1;i <= n;i ++) f[i] = i, siz[i] = 1;

		for(Rint i = n, now = n;i;i --){

			while(d[id[now]] - d[id[i]] > l) -- siz[getfa(id[now])], -- now;

			ans = max(ans, siz[getfa(id[i])]);

			merge(id[i], fa[id[i]]);

		}

		printf("%d\n", ans);

	}

}

巴特西

CF516D Drazil and Morning Exercise【并查集，结论】

最新文章

热门文章