模板题。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define MAXN 20001#define INF 2147483647typedef pair
         
           Point;int n,K,ans,T[3];int v[MAXN<<1],w[MAXN<<1],first[MAXN],next[MAXN<<1],en;int dis[MAXN],En,last;void AddEdge(const int &U,const int &V,const int &W){    v[++en]=V;    w[en]=W;    next[en]=first[U];    first[U]=en;}bool centroid[MAXN];int size[MAXN];int calc_sizes(int U,int Fa){    int res=1;    for(int i=first[U];i;i=next[i])      if(v[i]!=Fa&&(!centroid[v[i]]))        res+=calc_sizes(v[i],U);    return size[U]=res;}Point calc_centroid(int U,int Fa,int nn){    Point res=make_pair(INF,-1);    int sum=1,maxv=0;    for(int i=first[U];i;i=next[i])      if(v[i]!=Fa&&(!centroid[v[i]]))        {          res=min(res,calc_centroid(v[i],U,nn));          maxv=max(maxv,size[v[i]]);          sum+=size[v[i]];        }    maxv=max(maxv,nn-sum);    res=min(res,make_pair(maxv,U));    return res;}void calc_dis(int U,int Fa,int d){    dis[En++]=d;    for(int i=first[U];i;i=next[i])      if(v[i]!=Fa&&(!centroid[v[i]]))        calc_dis(v[i],U,(d+w[i])%3);}int calc_pairs(int s){    for(int i=last;i