作者: KSkun

[UOJ207]共价大爷游长沙 题解

[UOJ207]共价大爷游长沙 题解

题目地址:UOJ:共价大爷游长沙 – 题目 – Universal 

[IOI2011]Dancing Elephants 题解

[IOI2011]Dancing Elephants 题解

题目地址:CodeChef:Elephant | CodeChef 题目描述 Pattay 

[CC-GERALD07]Chef and Graph Queries 题解

[CC-GERALD07]Chef and Graph Queries 题解

题目地址:CodeChef:Chef and Graph Queries | CodeChef

题目描述

大厨有一个无向图G。顶点从1到N标号,边从1到M标号。
大厨有Q对询问Li,Ri(1≤Li≤Ri≤M)。对于每对询问,大厨想知道当仅保留编号X满足Li≤X≤Ri所在的边时,图G中有多少连通块。
请帮助大厨回答这些询问。

输入输出格式

输入格式:
输入数据的第一行包含一个整数T,表示数据组数。对于每组数据,第一行包含三个整数N,M,Q。接下来的M行,每行包含两个整数Vi,Ui,依次表示一条无向边。接下来的Q行,每行包含两个整数Li,Ri,依次表示一组询问。

输出格式:
对于每组询问,输出对应的连通块数。

输入输出样例

输入样例#1:

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

输出样例#1:

2
1
3
1
1

说明

  • 1≤T≤1000
  • 1≤N, M, Q≤200000
  • 1≤Ui, Vi≤N
  • 1≤Li≤Ri≤M
  • 数据保证所有N的和不超过200000。所有M的和不超过200000。所有Q的和不超过200000。
  • 注意数据可能包含自环和重边!

题解

我们考虑一条边会对连通块产生什么影响,加一条边会合并某两个连通块,使得答案减少1,当然这仅当加这条边不会成环以及没有重边和自环的时候才会产生影响。因此我们考虑维护一个生成树,使得每加一条边,如果成环,删去该环中编号最小的边。该生成树上编号为[Li, Ri]的边有多少条,答案就是n-几。我们可以在逐条加边的过程中动态维护生成树以及生成树上的边编号计数。动态维护生成树可以用LCT做,而边编号计数则使用权值线段树。
这道题目的强制在线升级版可以看[BZOJ3514]Codechef MARCH14 GERALD07加强版 题解 | KSkun’s Blog
LCT和线段树都是常数大的东西,还好跑过了。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <algorithm>

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 = 400005, INF = 1e9;

struct LCTNode {
    int ch[2], fa, val, mn;
    bool rev;
} lct[MAXN];

inline bool isleft(int p) {
    return lct[lct[p].fa].ch[0] == p;
}

inline bool isroot(int p) {
    register int fa = lct[p].fa;
    return lct[fa].ch[0] != p && lct[fa].ch[1] != p;
}

inline void update(int p) {
    register int ls = lct[p].ch[0], rs = lct[p].ch[1];
    lct[p].mn = p;
    if(lct[lct[ls].mn].val < lct[lct[p].mn].val) lct[p].mn = lct[ls].mn;
    if(lct[lct[rs].mn].val < lct[lct[p].mn].val) lct[p].mn = lct[rs].mn;
}

inline void reverse(int p) {
    std::swap(lct[p].ch[0], lct[p].ch[1]);
    lct[p].rev ^= 1;
}

inline void pushdown(int p) {
    register int ls = lct[p].ch[0], rs = lct[p].ch[1];
    if(lct[p].rev) {
        if(ls) reverse(ls);
        if(rs) reverse(rs);
        lct[p].rev ^= 1;
    }
}

int sta[MAXN], stop;

inline void pushto(int p) {
    stop = 0;
    while(!isroot(p)) {
        sta[stop++] = p;
        p = lct[p].fa;
    }
    pushdown(p);
    while(stop) {
        pushdown(sta[--stop]);
    }
}

inline void rotate(int p) {
    register bool t = !isleft(p); register int fa = lct[p].fa, ffa = lct[fa].fa;
    lct[p].fa = ffa; if(!isroot(fa)) lct[ffa].ch[!isleft(fa)] = p;
    lct[fa].ch[t] = lct[p].ch[!t]; lct[lct[fa].ch[t]].fa = fa;
    lct[p].ch[!t] = fa; lct[fa].fa = p;
    update(fa);
}

inline void splay(int p) {
    pushto(p);
    for(register int fa = lct[p].fa; !isroot(p); rotate(p), fa = lct[p].fa) {
        if(!isroot(fa)) rotate(isleft(fa) == isleft(p) ? fa : p);
    }
    update(p);
}

inline void access(int p) {
    for(register int q = 0; p; q = p, p = lct[p].fa) {
        splay(p);
        lct[p].ch[1] = q;
        update(p);
    }
}

inline void makert(int p) {
    access(p);
    splay(p);
    reverse(p);
}

inline int findrt(int p) {
    access(p);
    splay(p);
    while(lct[p].ch[0]) p = lct[p].ch[0];
    return p;
}

inline void split(int u, int v) {
    makert(u);
    access(v);
    splay(v);
}

inline void link(int u, int v) {
    split(u, v);
    lct[u].fa = v;
}

inline void cut(int u, int v) {
    split(u, v);
    if(lct[v].ch[0] != u || lct[lct[v].ch[0]].ch[1]) return;
    lct[u].fa = lct[v].ch[0] = 0;
}

inline int query(int u, int v) {
    split(u, v);
    return lct[v].mn;
}

int sgt[MAXN << 2];

inline void insert(int o, int l, int r, int x, int v) {
    if(l == r) {
        sgt[o] += v;
        return;
    }
    register int mid = (l + r) >> 1;
    if(x <= mid) insert(o << 1, l, mid, x, v);
    else insert((o << 1) | 1, mid + 1, r, x, v);
    sgt[o] = sgt[o << 1] + sgt[(o << 1) | 1];
}

inline int query(int o, int l, int r, int ll, int rr) {
    if(l >= ll && r <= rr) return sgt[o];
    register int mid = (l + r) >> 1, res = 0;
    if(ll <= mid) res += query(o << 1, l, mid, ll, rr);
    if(rr > mid) res += query((o << 1) | 1, mid + 1, r, ll, rr);
    return res;
}

int T, n, m, q, ut, vt, lst[MAXN], u[MAXN], v[MAXN], ans[MAXN];

struct Edge {
    int u, v;
} edge[MAXN];

struct Query {
    int l, r, id;
    inline bool operator<(const Query &rhs) const {
        return r < rhs.r;
    }
} quer[MAXN];

int main() {
    T = readint();
    while(T--) {
        n = readint(); m = readint(); q = readint();
        // init
        for(int i = 0; i <= n + m; i++) {
            lct[i].ch[0] = lct[i].ch[1] = lct[i].fa = lct[i].mn = lct[i].rev = 0;
            lct[i].val = INF;
        }
        memset(sgt, 0, sizeof(sgt));
        // read
        for(int i = 1; i <= m; i++) {
            edge[i].u = readint(); edge[i].v = readint(); 
        }
        for(int i = 1; i <= q; i++) {
            quer[i].l = readint(); quer[i].r = readint(); quer[i].id = i;
        }
        std::sort(quer + 1, quer + q + 1);
        // work
        int tot = n, ptr = 1;
        for(int i = 1; i <= m; i++) {
            int u = edge[i].u, v = edge[i].v;
            if(u != v && findrt(u) == findrt(v)) {
                int t = query(u, v), tv = lct[t].val;
                cut(edge[tv].u, t);
                cut(edge[tv].v, t);
                insert(1, 1, m, tv, -1);
            }
            if(u != v) {
                tot++;
                lct[tot].mn = tot;
                lct[tot].val = i;
                link(u, tot);
                link(v, tot);
                insert(1, 1, m, i, 1);
            }
            while(ptr <= q && quer[ptr].r <= i) {
                if(quer[ptr].r == i) {
                    ans[quer[ptr].id] = n - query(1, 1, m, quer[ptr].l, quer[ptr].r);
                }
                ptr++;
            }
        }
        for(int i = 1; i <= q; i++) {
            printf("%d\n", ans[i]);
        }
    }
    return 0;
}
[BZOJ3514]Codechef MARCH14 GERALD07加强版 题解

[BZOJ3514]Codechef MARCH14 GERALD07加强版 题解

题目地址:BZOJ:Problem 3514. — Codechef MARC 

[HNOI2010]弹飞绵羊 题解

[HNOI2010]弹飞绵羊 题解

题目地址:洛谷:【P3203】[HNOI2010]弹飞绵羊 – 洛谷、BZOJ 

Link-Cut Tree(动态树)原理与实现

Link-Cut Tree(动态树)原理与实现

概述

LCT是一种实用数据结构(?),它滋磁维护树上信息,而且这个树是可以变换结构的。具体而言,它维护了一个Splay森林,利用Splay的功能可以维护树上信息,且可以对树结构进行拆分、连接等操作。下面介绍LCT的原理与实现。

原理与实现

一些定义

辅助树(auxiliary tree):在LCT中,用于维护重链信息的Splay。其维护的有序性以深度为参数,即其中序遍历为该链从根到重儿子的顺序。
访问(access):从树根出发,将根到某个节点的路径设置为重链。
重儿子(偏好儿子,preferred child):访问到的树链的最底层节点。
重边(偏好边,preferred edge):重链中,指向重儿子方向的边。
重链(偏好链,preferred path):访问时走过的路径,由重边和重儿子组成。
所有的访问都会创造出重链,但是由于LCT的操作,重链可能会断掉。具体的操作需要等到讲到操作的时候才能够说清楚。
注意,辅助树是为了便于维护树上信息,其形态不一定与原树相同,我们后面会讲到辅助树与原树的关系。

树的结构

刚刚也说到了,实际上LCT维护的是一个Splay森林。一棵Splay维护的是一条重链的信息。下面是一个LCT的示意图。
LCT示意图
图片来自Wikipedia:Link/cut tree – Wikipedia
图片中,粗边即为重边,而细边我们将它定义为轻边。左→中表示的是以a为根的有根树访问l节点所造成的变化。右图展示的是Splay的划分。
我们说,Splay维护的是重链信息,而当前Splay和原树中重链顶的父节点通过轻边(右图虚线箭头)来连接。
从现在开始,文章内容默认你已经会使用Splay的操作。如果Splay仍不会,可以参考Splay原理与实现 | KSkun’s Blog一文。

LCT的核心:访问(access)

访问,即从树根出发,将树根到某节点x的路径设置为重链的操作。要实现这个操作,我们需要将这一排点加入到一个Splay中。
实现上,我们要断掉链上的点与之前重儿子的连接,将其合并到一个Splay中。我们从重儿子x向树根处理,每次将节点splay到所在辅助树的根,此时该点的右子树为以前重链上需要切掉的一段。切断这条重边,并将右儿子的连边设置为向当前重儿子的重边即可。
实现上,我们统一用fa这一变量来存储父亲的信息,也就是说这个fa可能指的并非所在Splay的父节点,而是轻边的父节点。但是每个节点的儿子信息则完全是Splay中的儿子信息,即轻边的儿子不会在父节点有记录。因此我们只需更改每个节点的右儿子即可,并不需要重置右儿子的父亲信息。

inline void access(int p) {
    for(int q = 0; p; q = p, p = tr[p].fa) {
        splay(p);
        tr[p].ch[1] = q;
        update(p);
    }
}

换根(make_root)

换根,即将原树转换为以某节点x为树根的有根树。
我们可以访问该节点,并将其splay至根。由于Splay内部的有序以深度为依据,x只有左儿子,此时表示x在重链的底端。我们对这棵Splay进行翻转,x就变为重链的顶端,即原树树根。

inline void makert(int p) {
    access(p);
    splay(p);
    reverse(p);
}

找根(find_root)

找根,即找到某节点x所在原树的树根。
先访问该节点,splay至根。此时这条链上深度最小的点即为原树树根。因此我们只需找到最左的左儿子即可。

inline int findrt(int p) {
    access(p);
    splay(p);
    while(tr[p].ch[0]) p = tr[p].ch[0];
    return p;
}

分离树链(split)

分离树链,即将原树中某节点u到v的路径分离出来。
我们考虑将链的一端u设为树根,并访问v,将v splay到根。此时对于这条树链,在u、v所在的Splay上的体现即为v及v的左子树。

inline void split(int u, int v) {
    makert(u);
    access(v);
    splay(v);
}

连接原树(link)

连接原树,即将某节点u、v所在的原树通过边(u, v)连接起来。
先将其中一点u设为原树根,以轻边接到v上即可。如果此处利用split,效果其实是一样的。

inline void link(int u, int v) {
    split(u, v);
    tr[u].fa = v;
}

切断原树(cut)

切断原树,即将本相连的节点u、v之间的边切断。
先将这条边split出来,然后切断父子关系即可。如果左儿子不是u或者左儿子有右儿子,那么表示不存在(u, v)这条边。

inline void cut(int u, int v) {
    split(u, v);
    if(tr[v].ch[0] != u || tr[tr[v].ch[0]].ch[1]) return;
    tr[u].fa = tr[v].ch[0] = 0;
}

改变点值(modify)

你需要把该点提至整棵树的树根,再做修改,这样可以避免修改后还要向上更新根的信息。

inline void modify(int u, int w) {
    access(u);
    splay(u);
    tr[u].val = w; // 更改值
    update(u);
}

与单独Splay操作的区别

由于我们用fa混着存两种边关系,即轻儿子、重儿子,我们不好判断Splay根的位置。下面是一种判断是否为Splay根的方法。

inline bool isroot(int p) {
    int fa = tr[p].fa;
    return tr[fa].ch[0] != p && tr[fa].ch[1] != p;
}

对于Splay中常见的旋转(rotate)、伸展(splay)操作,实现上有些许区别。主要原因判断Splay根的方式变了。

inline void rotate(int p) {
    bool t = !isleft(p); int fa = tr[p].fa, ffa = tr[fa].fa;
    tr[p].fa = ffa; if(!isroot(fa)) tr[ffa].ch[!isleft(fa)] = p;
    tr[fa].ch[t] = tr[p].ch[!t]; tr[tr[fa].ch[t]].fa = fa;
    tr[p].ch[!t] = fa; tr[fa].fa = p;
    update(fa);
}

inline void splay(int p) {
    pushto(p);
    for(int fa = tr[p].fa; !isroot(p); rotate(p), fa = tr[p].fa) {
        if(!isroot(fa)) rotate(isleft(fa) == isleft(p) ? fa : p);
    }
    update(p); // 对p只update一次,优化常数
}

辅助树与原树的关系

原树在LCT中其实是剖成几条树链的,每条树链一个Splay。原树的结构中树链顺序,则为Splay的顺序,父子关系也依赖着轻重边来进行管理。但是LCT这个奇妙的Splay森林结构并不和原来的有根树完全相同,Splay根和树根也并不相同。
最开始看LCT就是在这里搞不懂的。而且直到现在我也不知道应该怎么写这段内容GG。

例题:【P3690】【模板】Link Cut Tree (动态树) – 洛谷

题目描述

  1. 求链点权异或和
  2. 连接树边
  3. 断开树边
  4. 改变点权

题解

我们在节点处维护一个子树异或和(Splay意义上的子树),每次查询split以后查。
修改操作则先访问它并且把这个点splay到根再改。

代码

// Code by KSkun, 2018/4
#include <cstdio>

#include <algorithm>

typedef long long LL;

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 LL readint() {
    register LL 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 = 300005;

struct Node {
    int ch[2], fa, val, xsum;
    bool rev;
} tr[MAXN];

inline bool isleft(int p) {
    return tr[tr[p].fa].ch[0] == p;
}

inline bool isroot(int p) {
    return tr[tr[p].fa].ch[0] != p && tr[tr[p].fa].ch[1] != p;
}

inline void update(int p) {
    tr[p].xsum = tr[p].val ^ tr[tr[p].ch[0]].xsum ^ tr[tr[p].ch[1]].xsum;
}

inline void reverse(int p) {
    std::swap(tr[p].ch[0], tr[p].ch[1]);
    tr[p].rev ^= 1;
}

inline void pushdown(int p) {
    if(tr[p].rev) {
        if(tr[p].ch[0]) reverse(tr[p].ch[0]);
        if(tr[p].ch[1]) reverse(tr[p].ch[1]);
        tr[p].rev ^= 1;
    }
}

int sta[MAXN], stop;

inline void pushto(int p) {
    stop = 0;
    while(!isroot(p)) {
        sta[stop++] = p;
        p = tr[p].fa;
    }
    sta[stop++] = p;
    while(stop) {
        pushdown(sta[--stop]);
    }
}

inline void rotate(int p) {
    bool t = !isleft(p); int fa = tr[p].fa, ffa = tr[fa].fa;
    tr[p].fa = ffa; if(!isroot(fa)) tr[ffa].ch[!isleft(fa)] = p;
    tr[fa].ch[t] = tr[p].ch[!t]; tr[tr[fa].ch[t]].fa = fa;
    tr[p].ch[!t] = fa; tr[fa].fa = p;
    update(fa);
}

inline void splay(int p) {
    pushto(p);
    for(int fa = tr[p].fa; !isroot(p); rotate(p), fa = tr[p].fa) {
        if(!isroot(fa)) rotate(isleft(fa) == isleft(p) ? fa : p);
    }
    update(p);
}

inline void access(int p) {
    for(int q = 0; p; q = p, p = tr[p].fa) {
        splay(p);
        tr[p].ch[1] = q;
        update(p);
    }
}

inline void makert(int p) {
    access(p);
    splay(p);
    reverse(p);
}

inline int findrt(int p) {
    access(p);
    splay(p);
    while(tr[p].ch[0]) p = tr[p].ch[0];
    return p;
}

inline void split(int u, int v) {
    makert(u);
    access(v);
    splay(v);
}

inline void link(int u, int v) {
    split(u, v);
    tr[u].fa = v;
}

inline void cut(int u, int v) {
    split(u, v);
    if(tr[v].ch[0] != u || tr[u].ch[1]) return;
    tr[u].fa = tr[v].ch[0] = 0;
}

inline void modify(int u, int w) {
    access(u);
    splay(u);
    tr[u].val = w;
    update(u);
}

int n, m, op, x, y;

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) {
        tr[i].val = tr[i].xsum = readint();
    }
    while(m--) {
        op = readint(); x = readint(); y = readint();
        switch(op) {
        case 0:
            split(x, y);
            printf("%d\n", tr[y].xsum);
            break;
        case 1:
            link(x, y);
            break;
        case 2:
            cut(x, y);
            break;
        case 3:
            modify(x, y);
        }
    }
    return 0;
}

参考资料

[CFGym100633D]LWDB 题解

[CFGym100633D]LWDB 题解

题目地址:Codeforces:Problem – 100633D &#821 

[ZJOI2007]捉迷藏 题解

[ZJOI2007]捉迷藏 题解

题目地址:洛谷:【P2056】[ZJOI2007]捉迷藏 – 洛谷、BZOJ: 

[国家集训队]聪聪可可 题解

[国家集训队]聪聪可可 题解

题目地址:洛谷:【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;
}
[BZOJ1468]Tree 题解

[BZOJ1468]Tree 题解

题目地址:洛谷:【P4178】Tree – 洛谷、BZOJ:Problem 1