其实上想清楚了也是挺好写的一道题。
首先直接算实在太蠢了。还要考虑一棵树有两个重心的情况。可以考虑对于每个点算贡献。也就是算每个点作为重心出现了几次。
那么也就是要在一个子树内断一条边,考虑除了这颗子树之外的子树的大小的最大值\(\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(); }