Tony102's Blog - 重心
type: channel
link: https://tony102.com/index.php/tag/%E9%87%8D%E5%BF%83/
items: 浅谈求每个子树重心的方法

浅谈求每个子树重心的方法
type: item
date: 2021-09-24T16:27:00+08:00
description: 问题引入给定一棵 $n$ 个点的树，求以每个点为根的子树的重心。数据范围：$n \leq 2 \times 10^5$朴素方法$O(n^2)$ 对每个点求出重心，时间无法承受。方法一考虑到重心的性质：一个子树的重心一定在其根节点所在重链上。发现重心的定义等价于重心的最大子树不超过整棵子树的一半，因此直接在重链上向下倍增即可。时间复杂度：$O(n \log n)$代码：int get(int x, int rt) { return std::max(siz[rt] - siz[x], siz[son[x]]); } void dfs1(int u) { if (siz[son[u]] <= siz[u] / 2) tag[ctr[u] = u] = 1; for (int i = head[u], v; i; i = edge[i].nxt) { v = edge[i].to; if (v == fa[u]) continue; dfs1(v); int c = ctr[v]; if (ctr[u] || siz[v] <= siz[u] / 2) continue; while (fa[c] && get(c, u) > siz[u] / 2) c = fa[c]; while (fa[c] && get(fa[c], u) <= siz[u] / 2) c = fa[c]; tag[ctr[u] = c] = 1; } }方法二还想再优秀一点？试图求得 $O(n)$ 的做法。有一个假的结论，可以让你爆零：重心只有可能是儿子的重心、儿子重心的父亲和它自己。在这些点组成的可能集合中找子树大小最大的。还有一个假的结论：重链上连续的一段节点的重心也是该重链上连续的一段节点。这两个结论为什么假掉了，我们可以构造一棵树，使得存在点不是任何子树的重心。如图：例如在一个应用中，每次修改的点都是重心。其中标黄的边为重边,未标黄的为轻边。如果我们更新重链上连续的一段：1,2,4。那么对应的需要修改的重心为 1,4。并不是连续的一段。所以上述结论是假的。稍微将这个结论换一下就真了：即对于任意节点 $u$ ,以它为重心的节点一定和 $u$ 在同一条重链上并且为连续的一段。有了这个结论，结合重链的性质：$\sum$ 重链长度 是 $O(n)$ 级别的，我们可以找到 $O(n)$ 做法。以 20210923 CDQZ NOIp模拟赛中秋特别版 T2为例，代码如下：（by CJ_wyz)#include<cstdio> #include<cctype> #include<set> #include<ctime> #include<cmath> #include<queue> #include<vector> #include<bitset> #include<random> #include<cstring> #include<cstdlib> #include<algorithm> #define mp std::make_pair #define swap std::swap #define lowbit(k) (k&(-k)) #define mod 31607 template<class T> inline T read(){ T r=0,f=0; char c; while(!isdigit(c=getchar()))f|=(c=='-'); while(isdigit(c))r=(r<<1)+(r<<3)+(c^48),c=getchar(); return f?-r:r; } template<class T> inline T min(T a,T b){ return a<b?a:b; } template<class T> inline T max(T a,T b){ return a>b?a:b; } #define ll long long inline ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; } inline ll lcm(ll a,ll b){ return a/gcd(a,b)*b; } inline ll qpow(ll a,int b){ ll ans=1; for(;b;b>>=1){ if(b&1)(ans*=a)%=mod; (a*=a)%=mod; } return ans; } #undef ll struct Z{ #define add(x) (x>=mod?x-mod:x) #define sub(x) (x<0?x+mod:x) int x; inline int val() const{ return x; } inline int inv() const{…