洛谷 2634 [国家集训队]聪聪可可——点分治

题目：https://www.luogu.org/problemnew/show/P2634

可用点分治。

因为自己和自己也能算上，所以%3=0的点对可以随便一点算，都是 t [0] * t [0] 。

也许不用dfs两边，比如记一个lst，就可以用这次的第一个dfs得出上次的第二个dfs了。不过懒得管了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=2e4+5;
int n,hd[N],xnt,to[N<<1],nxt[N<<1],mn,rt,siz[N],t[5];
ll w[N<<1],ans;
bool vis[N];
void add(int x,int y,ll z)
{
    to[++xnt]=y;nxt[xnt]=hd[x];w[xnt]=z;hd[x]=xnt;
    to[++xnt]=x;nxt[xnt]=hd[y];w[xnt]=z;hd[y]=xnt;
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void getrt(int cr,int fa,int s)
{
    siz[cr]=1;int mx=0;
    for(int i=hd[cr],v;i;i=nxt[i]) if(!vis[v=to[i]]&&v!=fa)
    {
        getrt(v,cr,s);siz[cr]+=siz[v];mx=max(mx,siz[v]);
    }
    mx=max(mx,s-siz[cr]);
    if(mx<mn)mn=mx,rt=cr;
}
void dfs(int cr,int fa,ll dis)
{
    t[dis%3]++;//这里已经让f[rt][0]++了!!! 
    for(int i=hd[cr],v;i;i=nxt[i]) if(!vis[v=to[i]]&&v!=fa)
        dfs(v,cr,dis+w[i]);
}
ll calc(int cr,ll w)
{
    t[0]=t[1]=t[2]=0;
    dfs(cr,0,w);
    return ((ll)t[1]*t[2]<<1)+(ll)t[0]*t[0];
}
void solve(int cr,int s,ll lst)
{
    vis[cr]=1;
    ans+=calc(cr,0);
    for(int i=hd[cr],v;i;i=nxt[i]) if(!vis[v=to[i]])
    {
        ans-=calc(v,w[i]);
        int ts=(siz[cr]>siz[v]?siz[v]:s-siz[cr]);
        mn=N;getrt(v,0,ts);solve(rt,ts);
    }
}
int main()
{
    scanf("%d",&n);int x,y;ll z;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%lld",&x,&y,&z);add(x,y,z);
    }
    mn=N;getrt(1,0,n);solve(rt,n);
    ll sum=(ll)n*n;
//    printf("! ans=%lld sum=%lld
",ans,sum);
    ll g=gcd(ans,sum);
    printf("%lld/%lld
",ans/g,sum/g);
    return 0;
}