本文主要是介绍聪聪可可[点分治]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。
他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是3的倍数，则判聪聪赢，否则可可赢。
聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。
输入格式：
输入的第1行包含1个正整数n。后面n-1行，每行3个整数x、y、w，表示x号点和y号点之间有一条边，上面的数是w。
输出格式：
以即约分数形式输出这个概率（即“a/b”的形式，其中a和b必须互质。如果概率为1，输出“1/1”）。
输入样例#1：
5 1 2 1 1 3 2 1 4 1 2 5 3
输出样例#1：
13/25
说明
【样例说明】
13组点对分别是(1,1) (2,2) (2,3) (2,5) (3,2) (3,3) (3,4) (3,5) (4,3) (4,4) (5,2) (5,3) (5,5)。
【数据规模】
对于100%的数据，n<=20000。
先找树的重心,求经过他的路径倍数为3的条数
然后递归找儿子,再在儿子的子树中找重心
如何求条数?我们维护cnt[0],cnt[1],cnt[2] 表示到根路径长度%3的点的个数
答案就是 cnt[1]*cnt[2]*2 + cnt[0]*cnt[0]
#include<bits/stdc++.h>
#define N 40005
using namespace std;
int first[N],next[N],to[N],w[N],tot;
int n,rt,cnt[5],dis[N],size[N],Maxson[N];
int ans,siz,vis[N];
int read(){int cnt=0;char ch=0;while(!isdigit(ch))ch=getchar();while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar();return cnt;
}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
void add(int x,int y,int z){next[++tot]=first[x],first[x]=tot,to[tot]=y,w[tot]=z;
}
void get_root(int u,int f){size[u]=1,Maxson[u]=0; for(int i=first[u];i;i=next[i]){int t=to[i]; if(t==f||vis[t]) continue;get_root(t,u); size[u] += size[t];Maxson[u] = max(Maxson[u] , size[t]);}Maxson[u] = max(Maxson[u] , siz-Maxson[u]);if(Maxson[rt] > Maxson[u]) rt = u;
}
void get_dis(int u,int f){cnt[dis[u]%3]++;for(int i=first[u];i;i=next[i]){int t=to[i]; if(t==f||vis[t]) continue;dis[t] = dis[u] + w[i];get_dis(t,u);}
}
int calc(int x,int d){cnt[0] = cnt[1] = cnt[2] = 0;dis[x] = d;get_dis(x,0);return cnt[1] * cnt[2] *2 + cnt[0] * cnt[0];
}
void solve(int x){ans += calc(x,0);vis[x]=1;for(int i=first[x];i;i=next[i]){int t=to[i]; if(vis[t]) continue;ans -= calc(t,w[i]);rt = 0 , siz = size[t];get_root(t,0);solve(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); }Maxson[0] = siz = n;get_root(1,0);solve(rt); int x = n * n , g = gcd(x,ans);printf("%d/%d\n",ans/g,x/g);return 0;
}
这篇关于聪聪可可[点分治]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
