BZOJ4551 - [Tjoi2016&Heoi2016]树

2017/11/01

题目

增强版数据可见 COGS 2332

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

  1. 标记操作:对某个结点打上标记(在最开始,只有结点1有标记,其他结点均无标记,而且对于某个 结点,可以打多次标记。)
  2. 询问操作:询问某个结点最近的一个打了标记的祖先(这个结点本身也算自己的祖先)

你能帮帮他吗?

做法 #1

树剖查位置最低的 1 或线段树维护 dfs 序上深度最大值。

做法 #2

答案是单调的,离线之后用路径压缩并查集倒序求解。

线段树维护 dfs 序

注意懒标记下放时需要讨论子节点是否有懒标记。

辣鸡蒟蒻懒得维护高端标记于是搞了个倍增。

  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
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cassert>
using namespace std;
const int SIZ = 5e5 + 2007;

struct tgno {
    int v; tgno *n;
} POOL[SIZ<<1], *Head[SIZ]; int ppos;
int N, Q;

inline void _add(int u, int v) {
    POOL[ppos].v = v;
    POOL[ppos].n = Head[u];
    Head[u] = &POOL[ppos++];
}

inline void addEdge(int u, int v) {
    _add(u, v), _add(v, u);
}

int dl[SIZ], dr[SIZ], dep[SIZ], fa[SIZ][23]; int T;
void dfs(int u = 1, int p = 0, int dd = 1) {
    dl[u] = ++T;

    dep[u] = dd;
    fa[u][0] = p;
    for(int i=1;i<23;i++)
        fa[u][i] = fa[fa[u][i-1]][i-1];

    typedef tgno* It;
    for(It i=Head[u];i;i=i->n) {
        if(i->v != p) dfs(i->v, u, dd + 1);
    }

    dr[u] = T;
}

const int inf = 0x3f3f3f3f;
int mx[SIZ<<2]; int M;
int lz[SIZ<<2];
#define ls(x) ((x) << 1)
#define rs(x) (ls(x) | 1)

void sinit(int C) {
    for(M=1;M<=C;M<<=1);

    for(int i=1;i<=M;i++)
        mx[M + i - 1] = 1;
    
    for(int i=M-1;i;i--)
        mx[i] = max(mx[ls(i)], mx[rs(i)]);
}

void push_down(int x) {
    if(lz[x] && x < M) {
        int lzy = lz[x];
        lz[ls(x)] = max(lz[ls(x)], lzy);
        lz[rs(x)] = max(lz[rs(x)], lzy);
        mx[ls(x)] = max(mx[ls(x)], lzy);
        mx[rs(x)] = max(mx[rs(x)], lzy);
    }

    lz[x] = 0;
}

int squery(int ql, int qr, int l = 1, int r = M, int x = 1) {
    push_down(x);

    if(ql == l && qr == r)
        return mx[x];

    int mid = (l + r) >> 1;

    if(qr <= mid)
        return squery(ql, qr, l, mid, ls(x));
    else if(ql > mid)
        return squery(ql, qr, mid+1, r, rs(x));
    else {
        return max(
                squery(ql, mid, l, mid, ls(x)),
                squery(mid+1, qr, mid+1, r, rs(x)));
    }
}

void schange(int c, int ql, int qr, int l = 1, int r = M, int x = 1) {
    push_down(x);
    
    if(ql == l && qr == r) {
        lz[x] = c;
        mx[x] = max(mx[x], c);
        return;
    }

    int mid = (l + r) >> 1;
    if(qr <= mid)
        return schange(c, ql, qr, l, mid, ls(x));
    else if(ql > mid)
        return schange(c, ql, qr, mid+1, r, rs(x));
    else {
        schange(c, ql, mid, l, mid, ls(x));
        schange(c, mid+1, qr, mid+1, r, rs(x));
        return;
    }
}

int query(int x) {
    int d = squery(dl[x], dl[x]);
    int dx = dep[x];
    assert(d != 0);
    assert(d <= dx);

    int r = x;
    for(int i=22;i>=0;i--) {
        if(dep[fa[r][i]] >= d)
            r = fa[r][i];
    }

    return r;
}

void change(int x) {
    schange(dep[x], dl[x], dr[x]);
}

int main() {
    scanf("%d %d", &N, &Q);

    int u, v;
    for(int i=1;i<N;i++) {
        scanf("%d %d", &u, &v); addEdge(u, v);
    }

    dfs();

    sinit(T);

    char opr[16];
    while(Q--) {
        scanf("%s %d", opr, &u);
        if(opr[0] == 'Q')
            printf("%d\n", query(u));
        else
            change(u);
    }
}

离线并查集

 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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int SIZ = 1e6 + 2007;
int N, Q;
int stk[SIZ], fa[SIZ], rt[SIZ];
int tag[SIZ], ans[SIZ];

int find(int x) {
    int pos = 0;
    while(x != fa[x]) {
        stk[++pos] = x;
        x = fa[x];
    }

    while(pos) fa[stk[pos--]] = x;
    return x;
}

char op[SIZ]; int opr[SIZ];

int main() {
    scanf("%d %d", &N, &Q);

    fa[1] = 1, tag[1] = 1;
    for(int i=1, u, v;i<N;i++) {
        scanf("%d %d", &u, &v);
        fa[v] = u;
    }

    for(int i=1;i<=N;i++)
        rt[i] = fa[i];

    char buf[8];
    for(int i=Q;i>=1;i--) {
        scanf("%s %d", buf, &opr[i]);
        op[i] = buf[0];
        if(op[i] == 'C') tag[opr[i]]++;
    }

    for(int i=1;i<=N;i++)
        if(tag[i])
            fa[i] = i;

    for(int i=1;i<=Q;i++) {
        if(op[i] == 'Q')
            if(tag[opr[i]])
                ans[i] = opr[i];
            else
                ans[i] = find(rt[opr[i]]);
        else {
            tag[opr[i]]--;
            if(!tag[opr[i]])
                fa[opr[i]] = rt[opr[i]];
        }
    }

    for(int i=Q;i>=1;i--)
        if(ans[i])
            printf("%d\n", ans[i]);
}