树的重心
当 \(u\) 作为根时，其节点数最大的子树最小，则称 \(u\) 为树的重心。
-
性质一：节点数最大的子树的节点数不超过 \(\frac{节点总数}{2}\)。
（反证法，若某重心 \(u\) 的节点数最大的子树的节点数超过 \(\frac{节点总数}{2}\)，则将其一个子节点提起来会更优）
-
性质二：至多两个且一定相邻。
（反证法，若不相邻或不止两个，则将中间的某个提起来会更优）
-
性质三：树上增 / 删一个叶子，重心至多偏移一位。
-
性质四：树上其他节点到重心距离和最小，若有两个，则到两个的距离和相等。
-
性质五：两棵树连一条边，新树的重心一定位于原两重心的路径上。
（同性质二，中间的提起来会更优）
P1395
板子。
code
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int n,ans;
bool vis[N];
vector<int> G[N],ctr;
int siz[N],mx[N];
void get_ctr(int cur,int fa){
siz[cur]=1;
for(int i:G[cur]){
if(i==fa) continue;
get_ctr(i,cur);
siz[cur]+=siz[i];
mx[cur]=max(mx[cur],siz[i]);
}
mx[cur]=max(mx[cur],n-siz[cur]);
if(mx[cur]*2<=n) ctr.push_back(cur);
}
void dfs(int cur,int fa,int sum){
ans+=sum;
for(int i:G[cur]){
if(i==fa) continue;
dfs(i,cur,sum+1);
}
}
int main(){
cin>>n;
for(int i=1,u,v;i<n;i++)
cin>>u>>v,
G[u].push_back(v),
G[v].push_back(u);
get_ctr(1,0);
sort(ctr.begin(),ctr.end());
dfs(ctr[0],0,0);
cout<<ctr[0]<<' '<<ans;
return 0;
}
CF685B
我们从下往上求出每棵子树的重心。
对于任意点 \(cur\)，其所在子树的重心，一定位于 \(cur \to ans_{nxt}\) 的链上（\(ans_{nxt}\) 表示 \(cur\) 的最大子树 \(nxt\) 的重心）。
于是我们令 \(tmp\) 从 \(ans_{nxt}\) 开始不断向上跳（为了使上方子树更小），直到 \(size_{tmp} \ge \frac{size_{cur}}{2}\)（此时 \(tmp\) 为根，\(cur\) 为 \(tmp\) 的子树，于是 \(tmp\) 不能受 \(cur\) 的约束）即为重心。
点击查看代码
#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
const int N=3e5+5;
int t,n,q;
int ans[N],son[N],faa[N];
vector<int> G[N];
int siz[N],mx[N];
void get_ctr(int cur,int fa){
siz[cur]=1;
for(int i:G[cur]){
if(i==fa) continue;
get_ctr(i,cur);
siz[cur]+=siz[i];
if(mx[cur]<siz[i])
mx[cur]=siz[i],
son[cur]=i;
}
mx[cur]=max(mx[cur],n-siz[cur]);
if(!son[cur]){ ans[cur]=cur; return; }
int tmp=ans[son[cur]];
while(siz[tmp]*2<siz[cur]) tmp=faa[tmp];
ans[cur]=tmp;
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>q;
for(int i=2,u;i<=n;i++)
cin>>u,
G[u].push_back(i),
faa[i]=u;
get_ctr(1,0);
while(q--){
int v; cin>>v;
cout<<ans[v]<<'\n';
}
return 0;
}
CF1406C
若重心只有一个，则随便上一条边再加回去。
若重心有两个，根据重心的性质四，就把一个重心的子树内的某一叶子节点连边放到另一个重心的子树里去即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int t,n;
vector<int> G[N],ctr;
int siz[N],mx[N];
int ans1,ans2,ans3;
void get_ctr(int cur,int fa){
siz[cur]=1;
for(int i:G[cur]){
if(i==fa) continue;
get_ctr(i,cur);
siz[cur]+=siz[i];
mx[cur]=max(mx[cur],siz[i]);
}
mx[cur]=max(mx[cur],n-siz[cur]);
if(mx[cur]*2<=n) ctr.push_back(cur);
}
void dfs(int cur,int fa,bool f){
if(G[cur].size()==1){
if(f) ans1=cur,ans2=fa;
else ans3=cur;
return;
}
for(int i:G[cur]){
if(i==fa) continue;
dfs(i,cur,f);
}
}
void init(){
ctr.clear();
for(int i=1;i<=n;i++) G[i].clear();
memset(siz,0,sizeof siz);
memset(mx,0,sizeof mx);
ans1=ans2=ans3=0;
}
void sol(){
init();
cin>>n;
for(int i=1,u,v;i<n;i++)
cin>>u>>v,
G[u].push_back(v),
G[v].push_back(u);
get_ctr(1,0);
if(ctr.size()==1){
cout<<ctr[0]<<' '<<G[ctr[0]][0]<<'\n'<<ctr[0]<<' '<<G[ctr[0]][0]<<'\n';
return;
}
//cout<<ctr[0]<<' '<<ctr[1]<<'\n';
dfs(ctr[0],ctr[1],1);
//dfs(ctr[1],ctr[0],0);
cout<<ans1<<' '<<ans2<<'\n'<<ctr[1]<<' '<<ans1<<'\n';
}
int main(){
cin>>t;
while(t--) sol();
return 0;
}