bzoj2152 树分治

还是太菜了，自己写的wa，但是找不到哪里错了，，

感觉现在学树分治早了点。。以后回来再看吧

/*

多少点对之间的路径是3的倍数

*/

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

#include<algorithm>

#define MAXN 20010

int N;

struct E{

    int v,next,w;

}edge[MAXN<<];

int head[MAXN],tot;

int size[MAXN];

int maxv[MAXN];

int vis[MAXN];

int dis[MAXN];

int num,ans,Max,root;

void init(){

    tot=ans=;

    memset(head,-,sizeof head);

    memset(vis,,sizeof vis);

}

void addedge(int u,int v,int w){

    edge[tot].v=v;

    edge[tot].w=w;

    edge[tot].next=head[u];

    head[u]=tot++;

}

//一次dfs处理子树的大小

void dfssize(int u,int f){

    size[u]=;

    maxv[u]=;

    for(int i=head[u];i!=-;i=edge[i].next){

        int v=edge[i].v;

        if(v==f||vis[v]) continue;

        dfssize(v,u);

        size[u]+=size[v];

        maxv[u]=max(maxv[u],size[v]);

    }

}

//一次dfs找重心

void dfsroot(int r,int u,int f){

    maxv[u]=max(maxv[u],size[r]-maxv[u]);

    if(maxv[u]<Max)

        Max=maxv[u],root=u;

    for(int i=head[u];i!=-;i=edge[i].next){

        int v=edge[i].v;

        if(v==f||vis[v])

            continue;

        dfsroot(r,v,u);

    }

}

int tmp[];

//一次dfs求路径长度

void dfsdis(int u,int d,int f){

    dis[u]=d%;

    tmp[dis[u]]++;

    for(int i=head[u];i!=-;i=edge[i].next){

        int v=edge[i].v;

        if(v==f||vis[v])

            continue;

        dfsdis(v,d+edge[i].w,u);

    }

}

//计算以u为根的子树中有多少点对的距离%3==0

int calc(int u,int d){

    tmp[]=tmp[]=tmp[]=;

    dfsdis(u,d,-);//得到dis数组

    return tmp[]*tmp[]+tmp[]*tmp[]*;

}

//分治

void dfs(int u){

    Max=N;

    dfssize(u,-);

    dfsroot(u,u,-);

    ans+=calc(root,);

    vis[root]=;

    for(int i=head[u];i!=-;i=edge[i].next){

        int v=edge[i].v;

        if(vis[v])

            continue;

        ans-=calc(v,edge[i].w);

        dfs(v);

    }

}

int gcd(int a,int b){

    if(b==) return a;

    else return gcd(b,a%b);

}

int main(){

    scanf("%d",&N);

    init();

    for(int i=;i<=N-;i++){

        int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        addedge(u,v,w%);

        addedge(v,u,w%);

    }

    dfs();

    int g=gcd(ans,N*N);

    printf("%d/%d",ans/g,N*N/g);

    return ;

}