2152: 聪聪可可
Time Limit: 3 Sec Memory Limit: 259 MBSubmit: 3991 Solved: 2054
[Submit][Status][Discuss]
Description
聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是3的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。
Input
输入的第1行包含1个正整数n。后面n-1行，每行3个整数x、y、w，表示x号点和y号点之间有一条边，上面的数是w。
Output
以即约分数形式输出这个概率（即“a/b”的形式，其中a和b必须互质。如果概率为1，输出“1/1”）。
Sample Input
1 2 1
1 3 2
1 4 1
2 5 3
Sample Output
【样例说明】
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。
又A了一道点分治，加深了对点分治的理解【加深了打板的熟练度（逃】
【先吐槽系列】
mmp接连bug涌现：
①GUIDE**我声明变量多个逗号没有任何警告？？【迎来我BZOJ第一个CE = =】
②求重心把max写成min，直接导致T
③自作多情特判结果为1输出1，结果为1输出1/1 = =
【mmp我还打了个对拍，结果都是什么错误啊。。。当是为省选赚rp了。。】
现在说说解法：
很常规的点分治，是3的倍数我们就将路径长对3取模
每次求出经过根的路径长为3的路径数
我们用t[0],t[1],t[2]来记录取模后各种长度路径的数量
显然ans = t[1] * t[2] + t[2] * t[1] + t[0] * t[0]
再减去子树的多算的就好了
再往下分治就解决啦~
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 20005,maxm = 40005,INF = 1000000000;
inline int RD(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}
return out * flag;
}
int n,sum,vis[maxn],head[maxn],nedge = 0,F[maxn],Siz[maxn],rt = 0;
int t[3],d[maxn],ans = 0;
struct EDGE{int to,w,next;}edge[maxm];
inline void build(int u,int v,int w){
edge[nedge] = (EDGE){v,w,head[u]}; head[u] = nedge++;
edge[nedge] = (EDGE){u,w,head[v]}; head[v] = nedge++;
}
void getRT(int u,int fa){
int to; F[u] = 0; Siz[u] = 1;
Redge(u) if (!vis[to = edge[k].to] && to != fa){
getRT(to,u);
Siz[u] += Siz[to];
F[u] = max(F[u],Siz[to]);
}
F[u] = max(F[u],sum - Siz[u]);
if (F[u] < F[rt]) rt = u;
}
void dfs(int u,int fa){
t[d[u]]++; int to;
Redge(u) if (!vis[to = edge[k].to] && to != fa){
d[to] = (d[u] + edge[k].w) % 3;
dfs(to,u);
}
}
int cal(int u,int v){
t[0] = t[1] = t[2] = 0; d[u] = v;
dfs(u,0);
return 2 * t[1] * t[2] + t[0] * t[0];
}
void solve(int u){
d[u] = 0; ans += cal(u,0);
int to;
vis[u] = true;
Redge(u) if (!vis[to = edge[k].to]){
ans -= cal(to,edge[k].w);
F[rt = 0] = INF; sum = Siz[to];
getRT(to,rt);
solve(rt);
}
}
void init(){
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
int a,b,w; n = RD();
REP(i,n - 1) a = RD(),b = RD(),w = RD() % 3,build(a,b,w);
sum = n; F[rt = 0] = INF;
}
int gcd(int a,int b){return b ? gcd(b,a % b) : a;}
void Print(){
int y = gcd(ans,n * n);
printf("%d/%d",ans / y,n * n / y);
}
int main(){
init();
getRT(1,0); solve(rt);
Print();
return 0;
}