BZOJ 2152 聪聪可可

据说可以树形 DP O(n) 过去？
反正我喜欢点分治！

由于题目限制的仅是 3 的余数（当然开到 105 点分治也可做），所以我们可以对于距离除以 3 的余数 0,1,2 来统计。
即，设 cnt0/1/2 表示距离膜 3 为 0/1/2 的点的个数。
那么对于结点 p，把答案加上 cntx(disp+x≡0(mod3),0≤x<3)。
显然 x 就是 −dispmod3。

然后有一些细节，比如到当前分治的点的路径只会被统计一次，
所以我们干脆只统计 x<y 的 (x,y) 的个数，并在输出时乘 2 加 n。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e4;
int n;
int to[(N << 1) + 5],pre[(N << 1) + 5],val[(N << 1) + 5],first[N + 5];
inline void add(int u,int v,int w)
{
    static int tot = 0;
    to[++tot] = v;
    val[tot] = w;
    pre[tot] = first[u];
    first[u] = tot;
}
int vis[N + 5],sum,cnt[N + 5];
long long dis[N + 5];
int sz[N + 5],max_part[N + 5],rt;
long long ans;
void get_rt(int p,int fa)
{
    sz[p] = 1,max_part[p] = 0;
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa && !vis[to[i]])
        {
            get_rt(to[i],p);
            sz[p] += sz[to[i]];
            max_part[p] = max(max_part[p],sz[to[i]]);
        }
    max_part[p] = max(max_part[p],sum - sz[p]);
    if(max_part[p] < max_part[rt])
        rt = p;
}
void get_dis(int p,int fa)
{
    ++cnt[dis[p] % 3];
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa && !vis[to[i]])
        {
            dis[to[i]] = dis[p] + val[i];
            get_dis(to[i],p);
        }
}
void clear(int p,int fa)
{
    --cnt[dis[p] % 3];
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa && !vis[to[i]])
            clear(to[i],p);
}
void calc(int p,int fa)
{
    ans += cnt[(3 - dis[p] % 3) % 3];
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa && !vis[to[i]])
            calc(to[i],p);
}
void solve(int p)
{
    vis[p] = 1;
    cnt[0] = cnt[1] = cnt[2] = 0;
    dis[p] = 0;
    get_dis(p,0);
    for(register int i = first[p];i;i = pre[i])
        if(!vis[to[i]])
            clear(to[i],p),calc(to[i],p);
    for(register int i = first[p];i;i = pre[i])
        if(!vis[to[i]])
        {
            rt = 0,sum = sz[to[i]],get_rt(to[i],p);
            solve(rt);
        }
}
int main()
{
    max_part[0] = 0x3f3f3f3f;
    scanf("%d",&n);
    int u,v,w;
    for(register int i = 1;i < n;++i)
        scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
    rt = 0,sum = n,get_rt(1,0);
    solve(rt);
    ans += ans + n;
    printf("%lld/%lld\n",ans / __gcd(ans,(long long)n * n),(long long)n * n / __gcd(ans,(long long)n * n));
}