题目地址：BZOJ：Problem 2610. — [Poi2003]Monkeys

题目描述

一棵树上有n 只猴子. 他们从1 到 n编号. 编号为1 的猴子用它的尾巴盘住了一个树枝. 剩下的猴子要么被其他的猴子钩住要么就是自己用手钩住其他的猴子. 每只猴子都可以用两只手去钩其他的猴子,每只手最多只能钩一只. 从0时刻开始, 每一秒都有一只猴子松开它的一只手. 这也许会造成一些猴子掉落到地上, 我们想要知道它们掉落地上的时间(猴子掉落的速度都非常的快,可以忽略掉落的时间).

题意简述

有一棵树，树根为1没有入边只有出边，每个点都只有一条入边和最多两条出边。现在切断树上的某些边，求每个点最早与树根不连通的时间，时间从0开始计算。

输入输出格式

输入格式：
第一行包含两个整数n和 m, 1 <= n <= 200000, 1 <= m <= 400000. 整数 n 代表猴子总数, 数 m 代表我们观察猴子的总时间. 接下来 n 行描述初始的情形. 第 (k + 1) 行 (1 <= k <= n) 有两个整数分别代表猴子k的左手和右手分别抓住了哪两只猴子. -1 代表它的那只手是空的. 接下来m行代表我们观察到的猴子的活动. 第i行有两个整数(1 <= i <= m) 代表在第i – 1时刻放开手的是哪只猴子和它放开的是哪只手(1 – 左, 2 – 右).

输出格式：
输出n个整数每行一个代表每只猴子掉落到地上的时间, 如果没有掉落, 输出-1.

输入输出样例

输入样例#1：

3 2
-1 3
3 -1
1 2
1 2
3 1

输出样例#1：

-1
1
1

题解

考虑离线做这个问题。先把没砍的边都建到树上去，然后按询问顺序倒序加边更新答案时间。维护连通性可以使用并查集，DFS来更新子树答案即可。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>

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; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 200005;

int n, m;
std::vector<int> gra[MAXN];

int fa[MAXN];

inline int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int ans[MAXN];

inline void dfs(int u, int fa, int res) {
    ans[u] = res;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(v == fa) continue;
        dfs(v, u, res);
    }
}

inline void link(int u, int v, int res) {
    int fu = find(u), fv = find(v), f1 = find(1);
    if(fu == fv) return;
    if(fu == f1) dfs(v, 0, res);
    else if(fv == f1) dfs(u, 0, res);
    else gra[u].push_back(v), gra[v].push_back(u);
    fa[fu] = fv;
}

struct Query {
    int a, b;
} qur[MAXN << 1];

bool del[MAXN][2];
int ch[MAXN][2];

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    for(int i = 1; i <= n; i++) {
        ch[i][0] = readint(); ch[i][1] = readint();
    }
    for(int i = 1; i <= m; i++) {
        qur[i].a = readint(); qur[i].b = readint() - 1;
        del[qur[i].a][qur[i].b] = true;
    }
    for(int i = 1; i <= n; i++) {
        if(!del[i][0] && ch[i][0] > 0) link(i, ch[i][0], -1);
        if(!del[i][1] && ch[i][1] > 0) link(i, ch[i][1], -1);
    }
    for(int i = m; i; i--) {
        link(qur[i].a, ch[qur[i].a][qur[i].b], i - 1);
    }
    ans[1] = -1;
    for(int i = 1; i <= n; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}