Luogu [国家集训队]聪聪可可

题解

解

点分治 / 树形dp
这里用点分解决
我们不需要记录真是的dis[], 只需使用 dis[] % 3 后的值
那么只需要这样传参数

void Getdis(u， fa, len % 3) {;}

表示: js[i] 表示 dis[] % 3 == i 的个数
那么怎么统计 Answer 呢？？
我们考虑 js[0] 对 Answer 的贡献为 js[0] * js[0]
这是显然的
对于 js[1] 和 js[2] 发现 (js[1] + js[2]) % 3 == 0,
满足条件
所以 js[1], js[2] 对 Answer 的贡献为 js[1] * js[2] * 2
所以 Answer += js[1] * js[2] * 2 + js[0] * js[0];

Code

#include <bits/stdc++.h>
const int N = 2e4 + 10;
int n, now = 1, head[N], dis[N];
struct Node {int v, w, nxt;} G[N << 1];
int size[N], maxson[N], Root;
bool vis[N];
int js[N];
int Answer;
int Size;
#define gc getchar()
inline int read() {
    int x = 0; char c = gc;
    while(c < '0' || c > '9') c = gc;
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
    return x;
} 
inline void Add(int u, int v, int w) {G[now].v = v; G[now].w = w; G[now].nxt = head[u]; head[u] = now ++;}
void Getroot(int u, int fa) {
    size[u] = 1;
    maxson[u] = 0;
    for(int i = head[u]; ~ i; i = G[i].nxt) {
        int v = G[i].v;
        if(vis[v] || v == fa) continue ;
        Getroot(v, u);
        size[u] += size[v];
        maxson[u] = std:: max(maxson[u], size[v]); 
    }
    maxson[u] = std:: max(maxson[u], Size - size[u]);
    if(maxson[u] < maxson[Root]) Root = u;
}
void Getdis(int u, int fa, int len) {
    dis[u] = len; js[dis[u]] ++;
    for(int i = head[u]; ~ i; i = G[i].nxt) {
        int v = G[i].v;
        if(vis[v] || v == fa) continue ;
        Getdis(v, u, (len + G[i].w) % 3);
    }
}
int Calc(int u, int len) {
    js[0] = js[1] = js[2] = 0;
    Getdis(u, 0, len % 3);
    return js[1] * js[2] * 2 + js[0] * js[0];
}
void Getans(int u) {
    vis[u] = 1;
    Answer += Calc(u, 0);
    for(int i = head[u]; ~ i; i = G[i].nxt) {
        int v = G[i].v;
        if(vis[v]) continue ;
        Answer -= Calc(v, G[i].w);
        Root = 0;
        Size = size[v];
        Getroot(v, u);
        Getans(Root);
    }
}
int Gcd(int a, int b) {
    return b == 0 ? a : Gcd(b, a % b);
}
int main() {
    n = read();
    for(int i = 1; i <= n; i ++) head[i] = -1;
    for(int i = 1; i < n; i ++) {
        int u = read(), v = read(), w = read();
        Add(u, v, w), Add(v, u, w);
    }
    maxson[Root] = n;
    Size = n;
    Getroot(1, 0);
    Getans(Root);
    int gcd = Gcd(Answer, n * n);
    std:: cout << Answer / gcd << "/" << n * n / gcd << "\n";
    return 0;
}