BZOJ2152 聪聪可可 <点分治>

Posted on Symbols count in article: 909 Reading time ≈ 3 mins.

Problem

聪聪可可

Time  Limit:  3  Sec\mathrm{Time\;Limit:\;3\;Sec}
Memory  Limit:  259  MB\mathrm{Memory\;Limit:\;259\;MB}

Description

聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画nn个“点”，并用n−1n-1条“边”把这nn个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是33的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

Input

输入的第11行包含11个正整数nn。后面n−1n-1行，每行33个整数xx、yy、ww，表示xx号点和yy号点之间有一条边，上面的数是ww。

Output

以即约分数形式输出这个概率（即“a/ba/b”的形式，其中aa和bb必须互质。如果概率为11，输出“1/11/1”）。

Sample Input

1
2
3
4
5
5
1 2 1
1 3 2
1 4 1
2 5 3

Sample Output

1
13/25

Hint

样例说明
共1313组点对分别是(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)(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%100\%的数据，n≤2×104n\le 2\times 10^4。

标签：点分治

Solution

经典点分治例题。
对于每个点，只考虑经过它的符合条件的路径，统计后递归分治左右子树。
这样我们只需要计算经过指定点长度为33的倍数的路径即可。
不难发现我们只需分别统计模33余0,1,20,1,2的一段在指定点的路径条数即可。
统计后，设三种余数的条数为cnt0cnt_0, cnt1cnt_1, cnt2cnt_2，则答案为cnt0×cnt0−cnt1×cnt2×2cnt_0\times cnt_0-cnt_1\times cnt_2\times 2。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#define MAX_N 200000
using namespace std;
int n, rt, tot, ans;    vector <int> G[MAX_N+5], E[MAX_N+5];
int s[MAX_N+5], h[MAX_N+5], dep[MAX_N+5], cnt[3];    bool mrk[MAX_N+5];
void addedge(int u, int v, int c) {G[u].push_back(v), E[u].push_back(c%3);}
int gcd(int a, int b) {return b ? gcd(b, a%b) : a;}
int frac(int a, int b) {return a/gcd(a, b);}
void getrt(int u, int fa) {
    s[u] = 1, h[u] = 0;
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i];	if (v == fa || mrk[v]) continue;
        getrt(v, u);	s[u] += s[v], h[u] = max(h[u], s[v]);
    }
    h[u] = max(h[u], tot-s[u]);
    if (h[u] < h[rt])	rt = u;
}
void getdep(int u, int fa) {
    cnt[dep[u]]++;
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i], c = E[u][i];
        if (v == fa || mrk[v]) continue;
        dep[v] = (dep[u]+c)%3, getdep(v, u);
    }
}
int calc(int u, int init) {
    cnt[0] = cnt[1] = cnt[2] = 0;
    dep[u] = init, getdep(u, 0);
    return cnt[0]*cnt[0]+cnt[1]*cnt[2]*2;
}
void DFS(int u) {
    ans += calc(u, 0), mrk[u] = true;
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i], c = E[u][i];	if (mrk[v])	continue;
        ans -= calc(v, c), rt = 0, tot = s[v], getrt(v, 0), DFS(rt);
    }
}
int main() {
    scanf("%d", &n);	for (int i = 1, u, v, c; i < n; i++) scanf("%d%d%d", &u, &v, &c), addedge(u, v, c), addedge(v, u, c);
    tot = h[0] = n, getrt(1, 0), DFS(rt);	printf("%d/%d", frac(ans, n*n), frac(n*n, ans));	return 0;
}