题面

题解

点分治套路走一波，考虑\(calc\)函数怎么写，存一下每条路径在\(\%3\)意义下的路径总数，假设为\(tot[i]\)即\(\equiv i(mod\ 3)\)，这时当前的贡献就是\(tot[0]^2+2\times tot[1]\times tot[2]\)。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using std::min; using std::max;using std::swap; using std::sort;using std::__gcd;typedef long long ll;template
        
         void read(T &x) {    int flag = 1; x = 0; char ch = getchar();    while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;}const int N = 2e4 + 10, Inf = 1e9 + 7;int n, m, k, d[N], Size, ans, tot[4];int cnt, from[N], to[N << 1], nxt[N << 1], dis[N << 1];int p, siz[N], tmp; bool vis[N];inline void addEdge(int u, int v, int w) {    to[++cnt] = v, nxt[cnt] = from[u], dis[cnt] = w, from[u] = cnt;}void getrt(int u, int f) {    siz[u] = 1; int max_part = 0;    for(int i = from[u]; i; i = nxt[i]) {        int v = to[i]; if(v == f || vis[v]) continue;        getrt(v, u), siz[u] += siz[v];        max_part = max(max_part, siz[v]);    } max_part = max(max_part, Size - siz[u]);    if(max_part < tmp) tmp = max_part, p = u;}void getpoi(int x, int y, int f) {    ++tot[y];    for(int i = from[x]; i; i = nxt[i]) {        int v = to[i]; if(v == f || vis[v]) continue;        getpoi(v, (y + dis[i]) % 3, x);    }}void calc (int x, int y, int dd) {    memset(tot, 0, sizeof tot);    getpoi(x, y % 3, 0);    ans += dd * (tot[0] * tot[0] + 2 * tot[1] * tot[2]);}void doit(int x) {     tmp = Inf, getrt(x, 0), vis[p] = true;    calc(p, 0, 1);    for(int i = from[p]; i; i = nxt[i]) {        int v = to[i]; if(vis[v]) continue;        calc(v, dis[i], -1);        Size = siz[v], doit(v);    }}int main () {    read(n), Size = n;    for(int i = 1, u, v, w; i < n; ++i) {        read(u), read(v), read(w);        addEdge(u, v, w), addEdge(v, u, w);    } doit(1);    int m = n * n, gg = __gcd(m, ans);    printf("%d/%d\n", ans / gg, m / gg);    return 0;}