【题解】LuoGu5666：树的重心

最新推荐文章于 2024-02-04 21:22:03 发布

丰川样子小孩姐

最新推荐文章于 2024-02-04 21:22:03 发布

阅读量360

点赞数 1

分类专栏：题解 noip 树状数组文章标签：题解 LuoGu NOIp 树状数组树

本文链接：https://blog.csdn.net/ModestCoder_/article/details/107750874

版权

题解同时被 3 个专栏收录

435 篇文章

订阅专栏

noip

53 篇文章

订阅专栏

树状数组

28 篇文章

订阅专栏

本文介绍了一种基于重心分解的算法，通过树状数组动态维护节点被作为重心的次数，解决了特定条件下的计数问题。算法利用差分思想处理重叠计算，确保精确性。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

放在开头
学弟cjc写了一篇题解，我觉得很好
题解

原题传送门

把重心换成新的根，记为 $r t$ ，接着考虑针对，每个 $u (u! = r t)$ ，被作为重心的次数
令 $s_u$ 表示 $u$ 的子树的节点数和， $g_u$ 表示 $u$ 的重儿子子树节点数和， $S$ 表示切断一条边之后，一棵树中有 $u$ 这个点，另一棵没有 $u$ 的树的节点数和
若 $u$ 是新树的重心，必须满足
(1) $2g_u<=n-S$
(2) $2(n-S-s_u)<=n-S$
(3)切断的这条边又显然不在 $u$ 的子树内，这是因为我的 $r t$ 是整棵树的重心
整理得 $n-2s_u<=S<=n-2g_u$
所以对于每个 $u$ ，有几个这样的 $S$ ， $u$ 就被当做重心几次，用树状数组动态维护 $S$ 的个数就好了
但是如果存在 $S=s_v(v在u子树中)$ 满足上述条件，也会被计算进去，那就不行了，这里可以用差分思想解决。再开一个树状数组专门维护这个，每次进入遍历和回溯的时候求一个差值，把多余的减掉
最后解决 $r t$ 的问题。一边遍历，一边看看可不可以砍掉当前边，记根的重儿子 $f i r$ ，次重儿子 $s e c$ ，若砍掉的边在 $f i r$ 子树中，需满足 $2s_{sec}<=n-s_u$ ；否则需满足 $2s_{fir}<=n-s_u$

Code：

#include <bits/stdc++.h>
#define maxn 300010
#define LL long long
using namespace std;
struct Edge{
	int to, next;
}edge[maxn << 1];
int num, head[maxn], tree1[maxn], tree2[maxn], n, iffir[maxn], fir, sec, s[maxn], g[maxn], rt;
LL ans;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y){ edge[++num] = (Edge){y, head[x]}, head[x] = num; }
int lowbit(int x){ return x & -x; }
void upd1(int x, int y){ if (!x) return; for (; x <= n; x += lowbit(x)) tree1[x] += y; }
void upd2(int x){ if (!x) return; for (; x <= n; x += lowbit(x)) ++tree2[x]; }
int qry1(int x){ if (x < 1) return 0; int sum = 0; for (; x; x -= lowbit(x)) sum += tree1[x]; return sum; }
int qry2(int x){ if (x < 1) return 0; int sum = 0; for (; x; x -= lowbit(x)) sum += tree2[x]; return sum; }

void dfs1(int u, int pre){
	s[u] = 1, g[u] = 0;
	int flag = 0;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre){
			dfs1(v, u);
			s[u] += s[v], g[u] = max(g[u], s[v]);
			if (s[v] > (n >> 1)) flag = 1;
		}
	}
	if (n - s[u] > (n >> 1)) flag = 1;
	if (!flag) rt = u;
}

void dfs2(int u, int pre){
	upd1(s[pre], -1), upd1(n - s[u], 1);
	if (u != rt){
		ans += 1LL * u * (qry1(n - (g[u] << 1)) - qry1(n - (s[u] << 1) - 1));
		ans += 1LL * u * (qry2(n - (g[u] << 1)) - qry2(n - (s[u] << 1) - 1));
		if (!iffir[u] && iffir[pre]) iffir[u] = 1;
		ans += 1LL * rt * (s[u] <= n - (s[iffir[u] ? sec : fir] << 1));
	}
	upd2(s[u]);
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre) dfs2(v, u);
	}
	if (u != rt) ans += 1LL * u * (qry2(n - (s[u] << 1) - 1) - qry2(n - (g[u] << 1)));
	upd1(s[pre], 1), upd1(n - s[u], -1);
}

int main(){
	int T = read();
	while (T--){
		n = read();
		num = ans = 0;
		memset(head, 0, sizeof(head));
		memset(tree1, 0, sizeof(tree1));
		memset(tree2, 0, sizeof(tree2));
		for (int i = 1; i < n; ++i){
			int x = read(), y = read();
			addedge(x, y), addedge(y, x);
		}
		dfs1(1, 0);
		dfs1(rt, 0);
		for (int i = 1; i <= n; ++i) upd1(s[i], 1);
		fir = sec = 0;
		for (int i = head[rt]; i; i = edge[i].next){
			int v = edge[i].to;
			if (s[v] > s[fir]) sec = fir, fir = v; 
			else if (s[v] > s[sec]) sec = v;
		} //printf("%d %d %d\n", rt, fir, sec);
		memset(iffir, 0, sizeof(iffir)); iffir[fir] = 1;
		dfs2(rt, 0);
		printf("%lld\n", ans);
	}
	return 0;
}