难度：省选/NOI-

题目描述

        聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。

        他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是3的倍数，则判聪聪赢，否则可可赢。

        聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

输入输出格式

输入格式：

        输入的第1行包含1个正整数n。后面n-1行，每行3个整数x、y、w，表示x号点和y号点之间有一条边，上面的数是w。

输出格式：

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

输入输出样例

Sample input

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

Sample output

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的倍数的点对数目，用点分治求即可，时间复杂度$O(nlog^2n)$。注意点分治时的距离都需要对3取模，这样直接根据距离为0即可判断合法的点对。另外每个点与自身形成的点对也是合法点对。
        在操作中需要实现点分治的work函数，这里的work函数可以在线性时间内解决：统计距离为0、1、2的点的数目，再用排列组合来求点对数目。
        算出数量来，用欧几里得算法去一下最大公因数输出即可。

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>

#define N 20005
using namespace std;
struct Edge {
    int to, next, v;
} edge[N * 2];
int n, head[N], cnt = 1, vis[N] = {0}, size[N], f[N], minn, root, ans = 0, num[3];

inline void add(int x, int y, int z) {
    edge[cnt].v = z, edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

void DFS(int x, int fa, int p) {
    size[x] = 1, f[x] = 0;
    for (int i = head[x]; i != -1; i = edge[i].next) {
        if (vis[edge[i].to] || edge[i].to == fa)continue;
        DFS(edge[i].to, x, p), size[x] += size[edge[i].to], f[x] = max(f[x], size[edge[i].to]);
    }
    f[x] = max(f[x], p - size[x]);
    if (f[x] < minn)minn = f[x], root = x;
}

void findRoot(int x, int s) {
    minn = 0x7fffffff, DFS(x, 0, s);
}

void DFS2(int x, int fa, int v) {
    num[(v % 3 + 3) % 3]++;
    for (int i = head[x]; i != -1; i = edge[i].next) {
        if (vis[edge[i].to] || edge[i].to == fa)continue;
        DFS2(edge[i].to, x, v + edge[i].v);
    }
}

void work(int x, int f, int w) {
    num[0] = num[1] = num[2] = 0, DFS2(x, 0, 0);
    if (f == 0)ans += num[0] * (num[0] - 1) / 2 * w + num[1] * num[2] * w;
    else if (f == 1)ans += num[0] * num[1] * w + num[2] * (num[2] - 1) / 2 * w;
    else ans += num[0] * num[2] * w + num[1] * (num[1] - 1) / 2 * w;
}

void divide(int x) {
    vis[x] = 1, work(x, 0, 1);
    for (int i = head[x]; i != -1; i = edge[i].next) {
        if (!vis[edge[i].to]) {
            work(edge[i].to, (6 - 2 * edge[i].v) % 3, -1);
            findRoot(edge[i].to, size[edge[i].to]);
            divide(root);
        }
    }
}

int gcd(int x, int y) {
    if (y == 0)return x;
    return gcd(y, x % y);
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)head[i] = -1;
    for (int i = 1; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, (z % 3 + 3) % 3), add(y, x, (z % 3 + 3) % 3);
    }
    findRoot(1, n), divide(root);
    int g = gcd(2 * ans + n, n * n);
    cout << (2 * ans + n) / g << "/" << n * n / g;
    return 0;
}

        本题还有一个更优雅的做法，那就是用树型DP。
        令dp(x,y)表示在以x为根的子树上，经过x并且距离总和对3的模为y的点对路径总数（每一个点对都要求两点互异），那么有状态转移方程：

        这里的$c_1,\cdots ,c_s$是x结点的s个子结点，$v(x,c_i)$是两点连边的边权。$\delta_{i,j}$是克罗内克符号，它在i=j时为1，否则为0。克罗内克符号的作用就是计入父结点与子结点连边本身就成立的情况。
        树型DP也需要去重，去重方法与点分治类似。

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
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>

#define N 20005
using namespace std;
struct Edge {
    int to, next, v;
} edge[N * 2];
int n, head[N], cnt = 1, dp[N][3], ans = 0;

inline void add(int x, int y, int z) {
    edge[cnt].v = z, edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

int gcd(int x, int y) {
    if (y == 0)return x;
    return gcd(y, x % y);
}

int DP(int x, int p, int fa) {
    if (dp[x][p] != -1)return dp[x][p];
    dp[x][p] = 0;
    for (int i = head[x]; i != -1; i = edge[i].next) {
        if (edge[i].to != fa)dp[x][p] += DP(edge[i].to, (p - edge[i].v + 3) % 3, x) + (edge[i].v == p ? 1 : 0);
    }
    return dp[x][p];
}

inline void solve(int x, int p, int fa) {//用来去重的函数
    if (p == 0)ans -= DP(x, 0, fa) * (DP(x, 0, fa) - 1) / 2 + DP(x, 1, fa) * DP(x, 2, fa) + DP(x, 0, fa);
    else if (p == 1)ans -= DP(x, 2, fa) * (DP(x, 2, fa) - 1) / 2 + DP(x, 0, fa) * DP(x, 1, fa) + DP(x, 1, fa);
    else ans -= DP(x, 1, fa) * (DP(x, 1, fa) - 1) / 2 + DP(x, 0, fa) * DP(x, 2, fa) + DP(x, 2, fa);
}

void DFS(int x, int fa) {
    ans += DP(x, 0, fa) * (DP(x, 0, fa) + 1) / 2 + DP(x, 1, fa) * DP(x, 2, fa);
    for (int i = head[x]; i != -1; i = edge[i].next) {
        if (edge[i].to != fa)solve(edge[i].to, (6 - 2 * edge[i].v) % 3, x), DFS(edge[i].to, x);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)head[i] = -1, dp[i][0] = dp[i][1] = dp[i][2] = -1;
    for (int i = 1; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, (z % 3 + 3) % 3), add(y, x, (z % 3 + 3) % 3);
    }
    DFS(1, 0);
    int g = gcd(2 * ans + n, n * n);
    cout << (2 * ans + n) / g << "/" << n * n / g;
    return 0;
}