bzoj2152: 聪聪可可 点分治

链接

https://www.lydsy.com/JudgeOnline/problem.php?id=2152

luogu爆搜都能过，总时间超过100ms就是写错了

思路

直接mod上面跑点分治就行了，又是模板

代码

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
const int N=5e5+7;
const int inf=0x3f3f3f3f;
int read() {
   int x=0,f=1;char s=getchar();
   for(;s<'0'||s>'9';s=getchar()) if(s=='-') f=-1;
   for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
   return x*f;
}
int n,ans;
struct node {
    int v,nxt,q;
}e[N<<1];
int head[N<<1],tot;
void add(int u,int v,int w) {
    e[++tot].v=v;
    e[tot].q=w;
    e[tot].nxt=head[u];
    head[u]=tot;
}
int rt,rt_val;
int vis[N],siz[N],dis[N];
void get_rt(int u,int f) {
    siz[u]=1;
    int tmp=0;
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if(v==f||vis[v]) continue;
        get_rt(v,u);
        siz[u]+=siz[v];
        tmp=max(tmp,siz[v]);
    }
    tmp=max(tmp,tot-siz[u]);
    if(tmp<rt_val) rt_val=tmp,rt=u;
}
int T[5];
void get_dis(int u,int f) {
    T[dis[u]]++;
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if(v==f||vis[v]) continue;
        dis[v]=(dis[u]+e[i].q)%3;
        get_dis(v,u);
    }
}
int q[N];
void calc(int u) {
    int a=1,b=0,c=0;
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if(vis[v]) continue;
        dis[v]=e[i].q;
        T[0]=T[1]=T[2]=0;
        get_dis(v,u);
        ans+=a*T[0]+c*T[1]+b*T[2];
        a+=T[0],b+=T[1],c+=T[2];
    }
}
void dfs(int u) {
    vis[u]=1;calc(u);
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if(vis[v]) continue;
        rt_val=inf;
        tot=siz[v],get_rt(v,0);
        dfs(rt);
    }
}
int main() {
    n=read();
    for(int i=1;i<n;++i) {
        int x=read(),y=read(),z=read()%3;
        add(x,y,z);
        add(y,x,z);
    }
    tot=n;
    rt_val=inf;
    get_rt(1,0);
    dfs(rt);
    int a=n*n,b=ans*2+n,gcd=__gcd(a,b);
    a/=gcd,b/=gcd;
    printf("%d/%d",b,a);
    return 0;
}