[国家集训队]聪聪可可 题解
题目地址:洛谷:【P2634】[国家集训队]聪聪可可 – 洛谷、BZOJ:Problem 2152. — 聪聪可可
题目描述
聪聪和可可是兄弟俩,他们俩经常为了一些琐事打起来,例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑(可是他们家只有一台电脑)……遇到这种问题,一般情况下石头剪刀布就好了,可是他们已经玩儿腻了这种低智商的游戏。
他们的爸爸快被他们的争吵烦死了,所以他发明了一个新游戏:由爸爸在纸上画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
题解
直接把距离、边权对3取模存起来,这样可以减少模运算的次数,优化常数。
统计一个子树下点的距离对3取余为0、1、2的点有多少,答案即c_0^2 + 2c_1c_2(距离被3整除的点之间以及和根,距离余3为1、2的点互相构成点对)。然后把不合法方案减掉,套个gcd,就解决了。
代码
// Code by KSkun, 2018/3
#include <cstdio>
inline int max(int a, int b) {
return a > b ? a : b;
}
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int readint() {
register int res = 0, neg = 1;
char c = fgc();
while(c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 20005, INF = 1e9;
int n, m, ut, vt, wt, k, rt, res = 0;
int siz[MAXN], dep[MAXN], msz[MAXN], sum;
bool vis[MAXN];
struct Edge {
int to, w, nxt;
} gra[MAXN << 1];
int head[MAXN], tot = 0;
inline void addedge(int u, int v, int w) {
tot++;
gra[tot].to = v;
gra[tot].w = w;
gra[tot].nxt = head[u];
head[u] = tot;
}
int c[3];
inline void getroot(int u, int fa) {
siz[u] = 1;
msz[u] = 0;
for(int i = head[u]; i; i = gra[i].nxt) {
int v = gra[i].to;
if(vis[v] || v == fa) continue;
getroot(v, u);
siz[u] += siz[v];
msz[u] = max(msz[u], siz[v]);
}
msz[u] = max(msz[u], sum - siz[u]);
if(msz[u] < msz[rt]) rt = u;
}
inline void caldep(int u, int fa) {
c[dep[u]]++;
for(int i = head[u]; i; i = gra[i].nxt) {
int v = gra[i].to, w = gra[i].w;
if(vis[v] || v == fa) continue;
dep[v] = (dep[u] + w) % 3;
caldep(v, u);
}
}
inline int work(int u, int w) {
c[0] = c[1] = c[2] = 0;
dep[u] = w;
caldep(u, 0);
return c[0] * c[0] + c[1] * c[2] * 2;
}
inline void dfs(int u) {
res += work(u, 0);
vis[u] = true;
for(int i = head[u]; i; i = gra[i].nxt) {
int v = gra[i].to, w = gra[i].w;
if(vis[v]) continue;
res -= work(v, w);
rt = 0;
sum = siz[v];
getroot(v, 0);
dfs(rt);
}
}
inline int gcd(int a, int b) {
int t;
while(t = a % b) {
a = b; b = t;
}
return b;
}
int main() {
n = readint();
for(int i = 1; i < n; i++) {
ut = readint(); vt = readint(); wt = readint() % 3;
addedge(ut, vt, wt);
addedge(vt, ut, wt);
}
rt = 0;
msz[0] = INF;
sum = n;
getroot(1, 0);
dfs(rt);
int t1 = n * n, t2 = gcd(res, t1);
printf("%d/%d", res / t2, t1 / t2);
return 0;
}