【bzoj2152】 聪聪可可

http://www.lydsy.com/JudgeOnline/problem.php?id=2152 (题目链接)

题意

　　给出一棵n个节点的带权树，求有多少点对的距离是3的倍数。

solution

　　点分治。对于每个重心统计出每棵子树到重心的距离%3=0/1/2的点的数量即可。求出ans后与n²进行下gcd出解。

　　许久之后回来复习了一下，发现点分治的关键其实就是在如何处理经过重心的情况上，每道题的做法都不同，有时候还会有很神奇的方法水过。。。

代码

// bzoj2152

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#define MOD 1000000007

#define inf 2147483640

#define LL long long

#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);

using namespace std;

inline int getint() {

    int x=0,f=1;char ch=getchar();

    while (ch>'9' || ch<'0') {if (ch=='-') f=-1;ch=getchar();}

    while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

const int maxn=20010;

struct edge {int  next,to,w;}e[maxn<<2];

int head[maxn],d[maxn],t[10],f[maxn],vis[maxn],son[maxn],sum,ans1,ans2,cnt,root,n;

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

    e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].w=w;

    e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;e[cnt].w=w;

}

void init() {

    ans1=cnt=sum=root=0;

    scanf("%d",&n);

    for (int i=1;i<n;i++) {

        int u=getint(),v=getint(),w=getint()%3;

        insert(u,v,w);

    }

    ans2=n*n;

}

void calroot(int u,int fa) {

    son[u]=1;f[u]=0;

    for (int i=head[u];i;i=e[i].next) {

        if (vis[e[i].to] || e[i].to==fa) continue;

        calroot(e[i].to,u);

        son[u]+=son[e[i].to];

        f[u]=max(f[u],son[e[i].to]);

    }

    f[u]=max(f[u],sum-son[u]);

    if (f[u]<f[root]) root=u;

}

void caldeep(int u,int fa) {

    t[d[u]]++;

    for (int i=head[u];i;i=e[i].next) {

        if (vis[e[i].to] || e[i].to==fa) continue;

        d[e[i].to]=(d[u]+e[i].w)%3;

        caldeep(e[i].to,u);

    }

}

int cal(int u,int now) {

    t[0]=t[1]=t[2]=0;

    d[u]=now;caldeep(u,0);

    return t[1]*t[2]*2+t[0]*t[0];

}

void work(int u) {

    ans1+=cal(u,0);

    vis[u]=1;

    for (int i=head[u];i;i=e[i].next) if (!vis[e[i].to]) {

        ans1-=cal(e[i].to,e[i].w);

        sum=son[e[i].to];

        root=0;

        calroot(e[i].to,0);

        work(root);

    }

}

int gcd(int a,int b) {

    return a%b==0?b:gcd(b,a%b);

}

int main() {

    init();

    sum=n;f[0]=inf;

    calroot(1,0);

    work(root);

    int x=gcd(ans1,ans2);

    printf("%d/%d",ans1/x,ans2/x);

    return 0;

}