题目

交了只有45分，下了数据确实挂了，但是自己拍数据不管范围都拍不出来，求神仙有没有小点的数据hack掉，或者看一下我思路有没有错，调了一上午了。

我的思路就是以重心做根，分别统计删根重儿子和非重儿子子树的贡献，分别是pre1,dfs1,pre2dfs2，pre预处理的是删除大小分别对应的重心和。cc存的是子树重心，c是删非重儿子大小为i在重儿子子树（包含根）的重心和，ccc就是删重儿子在次重mxx上的重心。求大佬帮忙看看，多谢了。

我的代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=3e5+10,E=N<<1,INF=0x3f3f3f3f;
int he[N],to[E],ne[E],tot; 
int T,n,ans;
int sum,siz[N],mx[N],rt;
int fa[N],son[N],mxx,g[N],cc[N],c[N],ccc[N]; 

inline void insert(const int x,const int y){
	to[++tot]=y,ne[tot]=he[x],he[x]=tot;
	to[++tot]=x,ne[tot]=he[y],he[y]=tot;
}
inline void init(){
	ans=0;
	tot=0,memset(he,0,sizeof(he));
	sum=0,memset(siz,0,sizeof(siz)),memset(mx,0,sizeof(mx)),rt=0;
	mxx=0,memset(fa,0,sizeof(fa)),memset(son,0,sizeof(son)),memset(g,0,sizeof(g));
	memset(cc,0,sizeof(cc)),memset(c,0,sizeof(c)),memset(ccc,0,sizeof(ccc));
}
inline void getrt(const int p,const int ff){ 
	siz[p]=1,mx[p]=0;
	for(int i=he[p];i;i=ne[i]) if(to[i]!=ff){
		getrt(to[i],p),siz[p]+=siz[to[i]];
		mx[p]=max(mx[p],siz[to[i]]);
	} mx[p]=max(mx[p],sum-siz[p]); if(mx[p]<mx[rt]) rt=p;
}
inline void dfs(const int p){ 
	siz[p]=1; for(int i=he[p];i;i=ne[i]) if(to[i]!=fa[p]){ 
		fa[to[i]]=p,dfs(to[i]),siz[p]+=siz[to[i]]; 
		if(p==rt){
			if(siz[son[p]]<siz[to[i]]) mxx=son[p],son[p]=to[i];
			else if(siz[mxx]<siz[to[i]]) mxx=to[i];
		}
		else if(siz[son[p]]<siz[to[i]]) son[p]=to[i];
	} 
	if(!son[p]) return g[p]=cc[p]=p,void();
	g[p]=g[son[p]]; while(g[p]!=p&&max(siz[son[fa[g[p]]]],siz[p]-siz[fa[g[p]]])<=siz[p]/2) g[p]=fa[g[p]];
	cc[p]=g[p]; if(max(siz[son[son[g[p]]]],siz[p]-siz[son[g[p]]])<=siz[p]/2) cc[p]+=son[g[p]];
//	cout<<"-> "<<p<<' '<<cc[p]<<' '<<g[p]<<' '<<son[g[p]]<<endl;
}
inline void pre1(){ //预处理非son[rt]删siz的rt 
//puts("pre");
	int pos=rt;
	for(int i=0;i<=siz[mxx];i++){
		while(max(siz[son[pos]],n-i-siz[pos])>(n-i)/2) pos=son[pos];
		c[i]=pos; if(max(siz[son[son[pos]]],n-i-siz[son[pos]])<=(n-i)/2) c[i]+=son[pos];
//		cout<<i<<' '<<c[i]<<' '<<pos<<endl;
	}
}
inline void pre2(){ //预处理son[rt]删siz在mxx中的rt 
	int pos=rt;
	for(int i=0;i<=siz[son[rt]];i++){
		if(pos==rt){
			if(max(siz[son[rt]]-i,siz[mxx])>(n-i)/2) pos=mxx;
		}
		if(pos!=rt) while(max(siz[son[pos]],n-i-siz[pos])>(n-i)/2) pos=son[pos];
		ccc[i]=pos; 
		if(pos==rt){
			if(max(siz[son[mxx]],n-i-siz[mxx])<=(n-i)/2) ccc[i]+=mxx;
		}
		else if(max(siz[son[son[pos]]],n-i-siz[son[pos]])<=(n-i)/2) ccc[i]+=son[pos];
//		cout<<i<<' '<<pos<<' '<<ccc[i]<<endl;
	}
}
inline void dfs1(const int p){
	for(int i=he[p];i;i=ne[i]) if(to[i]!=fa[p]&&to[i]!=son[rt])
		ans+=cc[to[i]]+c[siz[to[i]]],dfs1(to[i]);
}
inline void dfs2(const int p){
//	for(int i=he[p];i;i=ne[i]) if(to[i]!=fa[p]) ans+=cc[to[i]]+ccc[siz[to[i]]],dfs2(to[i]);
	ans+=cc[p]+ccc[siz[p]];
	for(int i=he[p];i;i=ne[i]) if(to[i]!=fa[p]) dfs2(to[i]);
}

#define in read()
inline int read(){
	int f=1,k=0; char cp=getchar();
	while(cp!='-'&&(cp<'0'||cp>'9')) cp=getchar();
	if(cp=='-') f=-1,cp=getchar();
	while(cp>='0'&&cp<='9') k=(k<<3)+(k<<1)+cp-48,cp=getchar();
	return f*k;
}
signed main(){ 
	T=in; while(T--){ init(); n=in; for(int i=1;i<n;i++) insert(in,in);
		sum=n,mx[rt=0]=INF,getrt(1,0),dfs(rt);// cout<<rt<<' '<<son[rt]<<' '<<mxx<<endl;
		pre1(),dfs1(rt); //处理非son[rt]
//		cout<<"-> "<<ans<<endl;
		pre2();//,ans+=cc[son[rt]]+ccc[siz[son[rt]]]; //cout<<ans<<' '<<cc[son[rt]]<<' '<<ccc[siz[son[rt]]]<<' '<<endl;
		if(son[rt]) dfs2(son[rt]); //处理son[rt]
		printf("%lld\n",ans); 
	}

	return 0;
}