luogu P5666 [CSP-S2019] 树的重心

本文主要是介绍luogu P5666 [CSP-S2019] 树的重心，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

其实上想清楚了也是挺好写的一道题。
首先直接算实在太蠢了。还要考虑一棵树有两个重心的情况。可以考虑对于每个点算贡献。也就是算每个点作为重心出现了几次。
那么也就是要在一个子树内断一条边，考虑除了这颗子树之外的子树的大小的最大值\(\max\)，最后肯定不能小于\(2\max\)
另外当前这个子树在全树不能占到一半以上，那么就至少要砍掉\(2siz-n\)个点。
以这两个东西直接二维数点就好了，时间复杂度\(O(Tn\log n)\)
code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define ll long long
#define db double
#define lb long db
#define N (300000+5)
#define M ((1<<16)+5)
#define K (1000+5)
#define mod 998244353
#define Mod (mod-1)
#define eps (1e-9)
#define ull unsigned ll
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using namespace std;vector<int> S[N];
I void read(int &x){x=0;char c=Gc();while(c<'0'||c>'9') c=Gc();while(c>='0'&&c<='9') x=x*10+c-48,c=Gc();}
int n,m,k,x,y,z,T,Df[N],Si[N],Bg[N],H;ll Ans;
struct Ques{int x,y,w;};vector<Ques> Q[N];
struct BT{int F[N];I void Cl(){Me(F,0);}I void Ins(int x,int y){while(x<=n) F[x]+=y,x+=x&-x;}I int Qry(int x){int Ans=0;while(x) Ans+=F[x],x-=x&-x;return Ans;}}F;
I void dfs(int x,int La){Si[x]=1;Df[Bg[x]=++H]=x;for(int i:S[x]) i^La&&(dfs(i,x),Si[x]+=Si[i]);}
I void Make(int x,int La){int X,Y,P1=0,P2=0;
    for(int i:S[x]) i^La&&(F.Ins(n-Si[i],1),F.Ins(Si[x],-1),Make(i,x),F.Ins(n-Si[i],-1),F.Ins(Si[x],1),Si[i]>P1?(P2=P1,P1=Si[i]):(P2=max(P2,Si[i])),0);n-Si[x]>P1?(P2=P1,P1=n-Si[x]):(P2=max(P2,n-Si[x]));
	for(int i:S[x]) {if(i==La) continue;X=max(n-2*(n-Si[i]),1),Y=min(n-2*(P1^Si[i]?P1:P2),Si[i]),X<=Y&&(Q[Bg[i]+Si[i]-1].PB((Ques){X,Y,x}),Q[Bg[i]-1].PB((Ques){X,Y,-x}),0);}
	if(La) X=max(n-2*(Si[x]),1),Y=min(n-2*(P1^(n-Si[x])?P1:P2),n-Si[x]),X<=Y&&(Q[Bg[x]-1].PB((Ques){X,Y,x}),Q[n].PB((Ques){X,Y,x}),Q[Bg[x]+Si[x]-1].PB((Ques){X,Y,-x}),Ans+=1ll*x*(F.Qry(Y)-F.Qry(X-1)));
}
I void Solve(){
	int i;Ans=0;F.Cl();for(i=1;i<=n;i++) S[i].clear(),Q[i].clear();read(n);for(i=1;i<n;i++) read(x),read(y),S[x].PB(y),S[y].PB(x);H=0;dfs(1,0);Make(1,0);
	for(i=1;i<=n;i++) {F.Ins(Si[Df[i]],1);for(Ques d:Q[i]) Ans+=1ll*d.w*(F.Qry(d.y)-F.Qry(d.x-1));}printf("%lld\n",Ans);
}
int main(){
	freopen("1.in","r",stdin);
	read(T);while(T--) Solve();
}

这篇关于luogu P5666 [CSP-S2019] 树的重心的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！