BZOJ 4551: [Tjoi2016&Heoi2016]树

Description

在2016年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树（根为1），有以下两种操作：

标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）
询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先）你能帮帮他吗?

Input

输入第一行两个正整数N和Q分别表示节点个数和操作次数接下来N-1行，每行两个正整数u,v(1≤u,v≤n)表示u到v有一条有向边接下来Q行，形如“opernum”oper为“C”时表示这是一个标记操作,oper为“Q”时表示这是一个询问操作。

对于每次询问操作，1 ≤ N, Q ≤ 100000。

Output

输出一个正整数，表示结果

Sample Input

5 5

1 2

1 3

2 4

2 5

Q 2

C 2

Q 2

Q 5

Q 3

Sample Output

Solution

DFS序+线段树。

因为是祖先中最近的染黑的，因此打的标记只有最深的那个有用。

先跑一遍DFS，求出DFS序来，那么修改子树操作可以变成区间修改（区间按照深度取max），用线段树维护一下就好了。

貌似有更强的并查集的离线搞法（然而人太弱不会）。。。

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
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
73
74
75
76
77
78
79
80
81
82
83
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
int getop() {
    char c = getchar();
    for (; 'A' > c || c > 'Z'; c = getchar());
    return c == 'Q';
}
struct edge_type {
    int to, next;
} edge[400005];
int h[400005], cnte = 0;
int tid[400005], dfn[400005], dep[400005], clo, laz[400005];
void ins(int x, int y) {
    edge[++cnte].to = y;
    edge[cnte].next = h[x];
    h[x] = cnte;
}
void dfs(int x) {
    tid[x] = ++clo;
    for (int i = h[x]; i; i = edge[i].next) {
        dep[edge[i].to] = dep[x] + 1;
        dfs(edge[i].to);
    }
    dfn[x] = clo;
}
void add(int now, int val) {
    if (dep[laz[now]] > dep[val]) return;
    laz[now] = val;
}
void pd(int x) {
    if (laz[x]) {
        add(x << 1, laz[x]);
        add(x << 1 | 1, laz[x]);
        laz[x] = 0;
    }
}
int query(int now, int l, int r, int x) {
    if (l == r) return laz[now];
    pd(now);
    int mid = (l + r) >> 1;
    if (x <= mid) return query(now << 1, l, mid, x);
    else return query(now << 1 | 1, mid + 1, r, x);
}
void change(int now, int l, int r, int ll, int rr, int val) {
    if (ll <= l && r <= rr) {
        add(now, val);
        return;
    }
    pd(now);
    int mid = (l + r) >> 1;
    if (ll <= mid) change(now << 1, l, mid, ll, rr, val);
    if (rr > mid) change(now << 1 | 1, mid + 1, r, ll, rr, val);
    return;
}
int n, m;
int main() {
    n = getint(); m = getint();
    int x, y;
    for (int i = 1; i < n; ++i) {
        x = getint(); y = getint();
        ins(x, y);
    }
    dep[1] = 1; dfs(1); laz[1] = 1;
    while (m--) {
        x = getop(); y = getint();
        if (x) {
            printf("%d\n", query(1, 1, n, tid[y]));
        } else {
            change(1, 1, n, tid[y], dfn[y], y);
        }
    }
    return 0;
}