忽然感慨，现在可以随便用__gcd这种函数了。
点分治一下就好了，最开始点分治的时候忘记选重心，T了一发。
考虑对于当前点，所有其他点到当前的路径，长为0的t[0]个，长为1的t[1]个，长为2的t[2]个。（取模后长度）那么我们对于一个点x来说，经过他的路径的总数为t[0]*t[0] + t[1] * t[2] * 2。这里t[0]和t[0]相乘，其某个长为0的路径和其本身组合产生一个合法路径，可以看作是，点x为终点的路径。但是有一个其他问题，可能存在两条源于x同一个孩子y的路径产生了组合，这种组合是非法的，我们要想办法删掉这些组合的数量。我们考虑x和y之间长度为v。那么我们只要减掉calc(y,v)即可。即经过y点，长度为v的路径组合后的数量。两个到y的边，各长度为v，正好对应我们之前错误经过x，来回的两个v。calc(y,v)和刚刚的非法组合的数量是相同的。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 const int MAXN = 21000,inf = 100000000; 5 typedef long long ll; 6 bool vis[MAXN]; 7 int head[MAXN],siz[MAXN],to[MAXN * 2],nxt[MAXN * 2],val[MAXN * 2]; 8 int n,cnt,root,sum,mx,t[3]; 9 ll ans; 10 void add(int x,int y,int v) 11 { 12 nxt[++cnt] = head[x]; 13 to[cnt] =y; 14 head[x] = cnt; 15 val[cnt] = v; 16 } 17 void get_root(int x,int frm) 18 { 19 siz[x] = 1; 20 int tmx = 0; 21 for (int i = head[x];i;i = nxt[i]) 22 { 23 if (to[i] == frm || vis[to[i]] == true) 24 continue; 25 get_root(to[i],x); 26 siz[x] += siz[to[i]]; 27 tmx = max(tmx,siz[to[i]]); 28 } 29 tmx = max(tmx,sum - siz[x]); 30 if (tmx < mx) root = x,mx = tmx; 31 } 32 void get_dis(int x,int frm,int mod) 33 { 34 t[mod]++; 35 for (int i = head[x];i;i = nxt[i]) 36 { 37 if (to[i] == frm || vis[to[i]] == true) 38 continue; 39 get_dis(to[i],x,(mod + val[i]) % 3); 40 } 41 } 42 ll calc(int x,int mod) 43 { 44 t[0] = t[1] = t[2] = 0; 45 get_dis(x,0,mod); 46 return (ll)t[0] * t[0] + (ll)t[1] * t[2] * 2; 47 } 48 void pot_div(int x) 49 { 50 ans += calc(x,0); 51 vis[x] = true; 52 for (int i = head[x];i;i = nxt[i]) 53 { 54 if (vis[to[i]] == true) continue; 55 ans -= calc(to[i],val[i]); 56 mx = inf; 57 sum = siz[to[i]]; 58 get_root(to[i],0); 59 pot_div(root); 60 } 61 } 62 int main() 63 { 64 scanf("%d",&n); 65 int tx,ty,tv; 66 for (int i = 1;i <= n - 1;i++) 67 { 68 scanf("%d%d%d",&tx,&ty,&tv); 69 add(tx,ty,tv % 3); 70 add(ty,tx,tv % 3); 71 } 72 mx = inf; 73 sum = n; 74 get_root(1,0); 75 pot_div(root); 76 ll tot = (ll)n * n; 77 ll g = __gcd(tot,ans); 78 printf("%lld/%lld ",ans / g,tot / g); 79 return 0; 80 }