同poj1741一样，只是将统计每一个点的深度改为深度除以3余数为0、1和2的点数量，注意(1,2)和(2,1)算两种。

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 #define N 20005 6 struct ji{ 7     int nex,to,len; 8 }edge[N<<1]; 9 int E,r,n,x,y,z,ans,a[11],head[N],vis[N],sz[N];10 int gcd(int x,int y){11     if (!y)return x;12     return gcd(y,x%y);13 }14 void add(int x,int y,int z){15     edge[E].nex=head[x];16     edge[E].to=y;17     edge[E].len=z;18     head[x]=E++;19 }20 void tot(int k,int fa,int sh){21     a[sh]++;22     for(int i=head[k];i!=-1;i=edge[i].nex)23         if ((!vis[edge[i].to])&&(edge[i].to!=fa))24             tot(edge[i].to,k,(sh+edge[i].len)%3);25 }26 int calc(int k,int p){27     memset(a,0,sizeof(a));28     tot(k,0,p);29     return a[0]*a[0]+2*a[1]*a[2];30 }31 void get(int k,int fa){32     int ma=0;33     sz[k]=1;34     for(int i=head[k];i!=-1;i=edge[i].nex)35         if ((!vis[edge[i].to])&&(edge[i].to!=fa)){36             get(edge[i].to,k);37             sz[k]+=sz[edge[i].to];38             ma=max(ma,sz[edge[i].to]);39         }40     ma=max(ma,sz[0]-sz[k]);41     if (ma<=sz[0]/2)r=k;42 }43 void dfs(int k){44     ans+=calc(k,0);45     vis[k]=1;46     get(k,0);47     for(int i=head[k];i!=-1;i=edge[i].nex)48         if (!vis[edge[i].to]){49             ans-=calc(edge[i].to,edge[i].len);50             sz[0]=sz[edge[i].to];51             get(edge[i].to,0);52             dfs(r);53         }54 }55 int main(){56     scanf("%d",&n);57     memset(head,-1,sizeof(head));58     for(int i=1;i