题解：
随便点分治，用一个t数组,t[i]代表有u到root的值mod3==i； 那么答案就是：t[0]*t[0]+t[1]*t[2]*2;
代码：
#include#include #include #include #define N 20005using namespace std;int pre[N*2],now[N],v[N*2],val[N*2];int d[N],son[N],f[N];int t[4];bool vis[N];int tot,all,n,ans,root;int read(){ int x=0; char ch; bool bo=0; while (ch=getchar(), ch<'0'||ch>'9') if (ch=='-') bo=1; while (x=x*10+ch-'0',ch=getchar(),ch>='0'&&ch<='9'); if (bo) return -x; return x; }void ins(int a,int b,int c){ ++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b; val[tot]=c;}int gcd(int a,int b){ return b==0?a:gcd(b,a%b);}void getroot(int u,int fa){ son[u]=1; f[u]=0; for (int p=now[u]; p; p=pre[p]) { int vv=v[p]; if (vv==fa || vis[vv]) continue; getroot(vv,u); son[u]+=son[vv]; f[u]=max(f[u],son[vv]); } f[u]=max(f[u],all-son[u]); if (f[u]
