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

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

Sample Output

13/25

Data Range

对于 100% 的数据, 满足 \(n \leq 20000\).

Explanation

首先一看就知道有这样一个性质:

子树不会影响父节点上面的数据...... 就是说, 可以只统计出每棵子树下边权为 \(0, 1, 2\) 的情况各有多少种, 然后再把整个东西乘上一个系数 (因为总的方案数为 \(\frac{n(n-1)}{2}\)) . 最后得到的约分一下就得到了那个所求的即约分数.

顺便说一下 #include <algorithm> 里面似乎有一个函数叫 __gcd(a, b), 自带欧几里得 辗转相除法简直良心......

不过网上那些搞树分治的都有点过分了吧...... 毕竟这个是 \(O(n)\) 的做法=w=

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 20010, maxm = 40010;

class TreeDP
{
public:
    struct edge {
        int u, v, len;
        edge *next;
    };
    int n, ecnt;
    edge *edges[maxn], epool[maxm];
    void add_edge(int u, int v, int len)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->len = len % 3;
        p->next = edges[u]; edges[u] = p;
        q->u = v; q->v = u; q->len = len % 3;
        q->next = edges[v]; edges[v] = q;
        return ;
    }
    int par[maxn];
    int dp[maxn][3];
    void dfs(int p, lli& res)
    {
        dp[p][0] = 1;
        dp[p][1] = 0;
        dp[p][2] = 0;
        for (edge *ep = edges[p]; ep; ep = ep->next)
            if (ep->v != par[p]) {
                par[ep->v] = p;
                dfs(ep->v, res);
                for (int i = 1; i <= ep->len; i++) {
                    swap(dp[ep->v][0], dp[ep->v][1]);
                    swap(dp[ep->v][0], dp[ep->v][2]);
                } // Equivalent to left shifting (rotating)
                res += dp[p][0] * dp[ep->v][0]
                    + dp[p][1] * dp[ep->v][2]
                    + dp[p][2] * dp[ep->v][1];
                for (int i = 0; i < 3; i++)
                    dp[p][i] += dp[ep->v][i];
            }
        return ;
    }
    lli eval(void)
    {
        par[1] = 0;
        lli res = 0;
        dfs(1, res);
        return res;
    }
} tdp;

int n;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1, a, b, c; i < n; i++) {
        scanf("%d%d%d", &a, &b, &c);
        tdp.add_edge(a, b, c);
    }
    lli res = tdp.eval() * 2 + n;
    lli _g = __gcd(res, (lli)n*n);
    lli __a = res / _g, __b = n*n / _g;
    printf("%lld/%lld\n", __a, __b);
    return 0;
}