Description

给定一颗n个节点的有根树，每个节点有一个固定的权值和一种颜色(黑/白)，初始时都为白色，需实现以下操作： 1. Modify v：将v的颜色改为黑色 2. Query v： 找到一个黑色节点u，使得u和v的最近公共祖先z对应的权值尽可能大，输出z的权值，若不存在输出-1

Solution

考试的时候差一点想到正解 考虑统计贡献。对于每一个节点，显然它只会对它子树中的节点产生贡献。 我们考虑将节点x染黑时，我们先用W[x]更新x的子树中的所有节点， 然后对于x的每一个祖先f，设x在f的子节点g所对应的子树中，那么在f的子树中除掉g的子树的部分就是需要用W[f]更新的部分。 接下来有个非常重要的优化：如果对于一个节点x，如果它在此次修改操作前子树中已经存在黑色节点，那么显然在用W[x]更新完答案后就不需要更新x的祖先了。 因为x的祖先肯定已经通过同样的方式更新过一次了。 加上这个优化后，更新的总次数最多为n+mn+m次 那么我们直接在dfs序上用线段树维护子树信息即可 总复杂度

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
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
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 100000 + 100, Maxm = 2 * 100000 + 100;

int N, M;

int e, Begin[Maxn], To[Maxm], Next[Maxm];
int W[Maxn], fa[Maxn], dfn[Maxn], Index, size[Maxn];
int Vis[Maxn];

namespace DS
{
    int Tree[Maxn << 2], tag[Maxn << 2];

    inline void init ()
    {
        memset(Tree, -1, sizeof Tree);
        memset(tag, -1, sizeof tag);
    }

    inline void push_up (int x)
    {
        Tree[x] = max(Tree[x << 1], Tree[x << 1 | 1]);
    }

    inline void push_down (int x)
    {
        if (tag[x] == -1) return ;
        Tree[x << 1] = max(tag[x], Tree[x << 1]);
        Tree[x << 1 | 1] = max(tag[x], Tree[x << 1 | 1]);
        tag[x << 1] = max(tag[x], tag[x << 1]);
        tag[x << 1 | 1] = max(tag[x], tag[x << 1 | 1]);
        tag[x] = -1;
    }

    inline void update (int root, int l, int r, int x, int y, int v)
    {
        if (x > r || y < l) return ;
        if (x <= l && r <= y)
        {
            Tree[root] = max(Tree[root], v);
            tag[root] = max(tag[root], v);
            return ;
        }
        int mid = (l + r) >> 1;
        push_down (root);
        if (x <= mid) update (root << 1, l, mid, x, y, v);
        if (y > mid) update (root << 1 | 1, mid + 1, r, x, y, v);
        push_up (root);
    }

    inline int query (int root, int l, int r, int x)
    {
        if (l == r) return Tree[root];
        int mid = (l + r) >> 1;
        push_down(root);
        if (x <= mid) return query (root << 1, l, mid, x);
        else return query (root << 1 | 1, mid + 1, r, x);
    }
}

inline void add_edge (int x, int y)
{
    To[++e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
}

inline void dfs (int x)
{
    dfn[x] = ++Index;
    size[x] = 1;
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (fa[x] == y) continue;
        fa[y] = x;
        dfs(y);
        size[x] += size[y];
    }
}

inline void update (int x)
{
    DS :: update(1, 1, N, dfn[x], dfn[x] + size[x] - 1, W[x]);
    if (Vis[x]) return ;
    Vis[x] = 1;
    int last = x;
    x = fa[x];
    while (x)
    {
        DS :: update (1, 1, N, dfn[x], dfn[last] - 1, W[x]);
        DS :: update (1, 1, N, dfn[last] + size[last], dfn[x] + size[x] - 1, W[x]);
        if (Vis[x]) return ;
        Vis[x] = 1;
        last = x;
        x = fa[x];
    }
}

int main()
{
    freopen("lca.in", "r", stdin);
    freopen("lca.out", "w", stdout);
    scanf("%d%d", &N, &M);

    for (int i = 1; i <= N; ++i) scanf("%d", &W[i]);
    for (int i = 1; i < N; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        add_edge (x, y);
        add_edge (y, x);
    }

    dfs(1);

    DS :: init();
    char S[10];
    while (M--)
    {
        int x;
        scanf("%s%d", S, &x);
        if (S[0] == 'M') update (x);
        else
            printf("%d\n", DS :: query (1, 1, N, dfn[x]));
    }
    return 0;
}