题解 P5666 【树的重心【民间数据】】

本题解远短于其他题解,只需要两次dfs和一次倍增 二叉树: 深度较浅,暴力换重儿子 对于一个点,若x不是重心,重心要么在重儿子子树里,要么在父亲节点上 第一次dfs求出son[x],s[x] p[x][i]表示x沿着重儿子走$2^i$步 第二次dfs换根,把上面数组的定义从以1为根改为以x为根 对于一条边,以下方的重心,可以直接倍增,可以跳的条件为上方 的size<=sum/2 对于上方的重心,换根时记录信息,倍增方法一样 于是我们就用纯CSP算法解决了CSP2019 Day2 T3 给出简短的代码 ```cpp #include<bits/stdc++.h> #define o 300005 #define g0(a) memset(a,0,sizeof(a)) #define gc(a,b) memcpy(a,b,sizeof(a)) using namespace std; inline int read() { register int data=0,w=1; char ch=0; while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); if(ch=='-')w=-1,ch=getchar(); while(ch>='0'&&ch<='9')data=(data<<1)+(data<<3)+(ch^48),ch=getchar(); return data*w; } struct node { int to,next; }w[o*2]; int n,T,son[o],s[o],pr[o],son2[o],p[o][18],son3[o],f[o],h[o],cnt,s2[o]; void add(int x,int y){++cnt;w[cnt].to=y;w[cnt].next=h[x];h[x]=cnt;} void dfs(int x,int fa) { s[x]=1;pr[x]=fa; for(int i=h[x];i;i=w[i].next) { int y=w[i].to; if(y==fa)continue; dfs(y,x);s[x]+=s[y]; if(s[y]>s[son[x]])son2[x]=son[x],son[x]=y; else if(s[y]>s[son2[x]])son2[x]=y; } p[x][0]=son[x]; for(int i=1;i<=17;i++)p[x][i]=p[p[x][i-1]][i-1]; } long long ans; int judge(int x,int sum) { return x*(max(s2[son3[x]],sum-s2[x])<=sum/2); } void dfs2(int x,int fa) { for(int i=h[x];i;i=w[i].next) { int y=w[i].to; if(y==fa)continue; s2[x]=s[1]-s[y];f[y]=0;f[x]=0; if(son[x]==y)son3[x]=son2[x]; else son3[x]=son[x]; if(s2[fa]>s2[son3[x]])son3[x]=fa; p[x][0]=son3[x]; for(int j=1;j<=17;j++)p[x][j]=p[p[x][j-1]][j-1]; int b=x; for(int j=17;j>=0;j--)if(s2[x]-s2[p[b][j]]<=s2[x]/2)b=p[b][j]; ans+=judge(son3[b],s2[x])+judge(b,s2[x])+judge(f[b],s2[x]); b=y; for(int j=17;j>=0;j--)if(s2[y]-s2[p[b][j]]<=s2[y]/2)b=p[b][j]; ans+=judge(son3[b],s2[y])+judge(b,s2[y])+judge(f[b],s2[y]); f[x]=y; dfs2(y,x); } son3[x]=p[x][0]=son[x];f[x]=pr[x]; for(int j=1;j<=17;j++)p[x][j]=p[p[x][j-1]][j-1]; s2[x]=s[x]; } int main() { T=read(); while(T--) { g0(h);g0(son);g0(f);g0(pr);cnt=0;ans=0; n=read(); for(int i=1;i<n;i++) { int x=read(),y=read(); add(x,y);add(y,x); } dfs(1,0); gc(s2,s);gc(son3,son);gc(f,pr); dfs2(1,0); cout<<ans<<'\n'; } return 0; } ```