全TLE求调

#include<algorithm>
#include<cstdio>
#include<vector>
#define ll long long
#define MaxN 300500
using namespace std;
int read(){
  int X=0;char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
vector<int> g[MaxN];
int siz[MaxN],p[MaxN],f[MaxN];
void pfs(int u)
{
  siz[u]=1;
  for (int i=0,v;i<g[u].size();i++)
    if (!siz[v=g[u][i]]){
      f[v]=u;pfs(v);
      siz[u]+=siz[v];
    }
  p[u]=0;
  for (int i=0,v;i<g[u].size();i++)
    if ((v=g[u][i])!=f[u]&&siz[v]>=siz[p[u]])
      p[u]=v;
}
ll ans;
void upd(int &u,int c)
{
  while (siz[u]*2<c)u=f[u];
  while (siz[p[u]]*2>c)u=p[u];
  if (siz[p[u]]*2==c)ans+=p[u];
  if (siz[u]*2==c)ans+=f[u];
  ans+=u;
}
int n,u1,u2,c1,c2;
void dfs(int u,int fa)
{
  upd(u1,c1);upd(u2,c2);
  if (!p[u])return ;

  f[f[fa]=u]=0;
  siz[u]+=siz[fa];
  int p1=0,p2=0,v,sp=p[u];

    for (int i=0;i<g[u].size();i++){
      v=g[u][i];
      if (siz[v]>=siz[p1]){p2=p1;p1=v;}
      else if (siz[v]>siz[p2])p2=v;
    }
    siz[u]-=siz[v=sp];
      if (p1==v)p[u]=p2;else p[u]=p1;
      c1=siz[u];c2=siz[v];
      if (u2==u)u2=v;
      dfs(v,u);
    siz[u]+=siz[v];

    int s1=u1,s2=u2;
    for (int i=0;i<g[u].size();i++)
      if ((v=g[u][i])!=fa&&v!=sp){
        siz[u]-=siz[v];
          if (p1==v)p[u]=p2;else p[u]=p1;
          c1=siz[u];c2=siz[v];
          dfs(u2=v,u);
        siz[u]+=siz[v];
      }
  siz[u]-=siz[fa];
  f[f[u]=fa]=0;
  p[u]=sp;
}
void solve()
{
  n=read();ans=0;
  for (int i=1;i<=n;i++)
    {g[i].clear();siz[i]=0;}
  for (int i=1,f,t;i<n;i++){
    f=read();t=read();
    g[f].push_back(t);
    g[t].push_back(f);
  }for (int i=1;i<=n;i++)
    if (g[i].size()==1)u1=i;
  c1=1;c2=n-1;
  f[u2=g[u1][0]]=0;pfs(u2);
  siz[u2]--;if (p[u2]==u1)p[u2]=0;
  upd(u2,c2);ans=0;
  dfs(g[u1][0],u1);
  printf("%lld\n",ans);
}
int main()
{
  freopen("centroid.in","r",stdin);
  freopen("centroid.out","w",stdout);
  int T=read();
  while(T--)solve();
  return 0;
}

题目传送门