「JOI2019Final」独特的城市

发表于 | 更新于 | 分类于 | 阅读次数：

题意简述

LOJ 3014

一棵树 $n$ 个点，点有颜色 $c_i$。
对于每个点，求出以其为根时，所有没有其他深度相同点的点的不同颜色个数。
$n\le 2\times 10^5$。

主要思路

不妨称在某个点为根时没有其他深度相同点的点为该点的合法点。
那么显然一个点的合法点在其到它最远点的路径上。最远点显然是直径端点之一，故只需对直径两端点提为根做一次。

那么此时一个点只需要关心它到根路径上的点了。
这条路径上哪些点是合法的呢？考虑一条从这条路径上的点开始的往下的路径，显然该点上方的路径长度个点都不合法。最后剩下的就是合法的。

dfs，用栈维护当前合法的点，用桶维护每种颜色的出现次数。
长链剖分，先往重儿子走（用轻儿子的最大深度弹栈），再往轻儿子走（用重儿子最大深度弹栈）。
注意到这样可以不必撤销——假设现在 dfs 到某点，走到某个儿子时若某个祖先被弹掉，该祖先在该儿子及其他儿子的子树内都应被弹掉。
但是有一个例外就是该点本身可能被弹掉后在别处仍合法，所以 dfs 一个儿子后要重新加回去。
总入栈次数 $O(n)$，故复杂度 $O(n)$。

参考代码

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
#include <bits/stdc++.h>
namespace my_std {
using namespace std;
#define reg register
#define Rint register int
#define FOR(i, a, b) for (register int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (register int i = (a), ed_##i = (b); i >= ed_##i; --i)
#define Templ(T) template <typename T>
Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }
} // namespace my_std
using namespace my_std;

#define MMR (1 << 23)
struct INPUT{
    char buf[MMR], *s;
    INPUT(){ s = buf, fread(buf, 1, MMR, stdin); }
    inline INPUT& operator >>(int &x){
        x = 0;
        while(*s < 48) ++s;
        while(*s > 47) x = x * 10 + *s++ - 48;
        return *this;
    }
}fin;
struct OUTPUT{
    char buf[MMR], *s;
    OUTPUT(){ s = buf; }
    inline OUTPUT& operator <<(int x){
        static int tmp[10];
        Rint *top = tmp;
        do{
            *++top = (x % 10) ^ 48, x /= 10;
        }while(x);
        while(top != tmp) *s++ = *top--;
        *s++ = 10;
        return *this;
    }
    ~OUTPUT(){ fwrite(buf, 1, s - buf, stdout); }
}fout;

#define N 200010
int n, m;
vector<int> E[N];
int c[N], a[N], ans[N];
int dep[N], son[N], len[N];

void init(int u, int f, int &S){
    dep[u] = dep[f] + 1;
    if(dep[S] < dep[u]) S = u;
    for(Rint v: E[u]) if(v != f) init(v, u, S);
}

void dfs1(int u, int f){
    dep[u] = dep[f] + 1;
    son[u] = len[u] = 0;
    for(Rint v: E[u]){
        if(v == f) continue;
        dfs1(v, u);
        if(len[v] > len[son[u]]) son[u] = v;
    }
    len[u] = len[son[u]] + 1;
}

int st[N];
int g, *tp = st, *tg = st;
//tp 是当前栈顶，tg 是当前栈中最靠近栈顶的未被实际扔掉的位置
#define add(x) (g += (++c[a[x]] == 1))
#define del(x) (g -= (--c[a[x]] == 0))
void dfs2(int u, int f){
    while(tg != tp && dep[u] - dep[*(tg + 1)] > len[u] - 1) add(*++tg);
    //更新未被实际扔掉的最靠近栈顶的位置
    chkmax(ans[u], g);
    if(!son[u]) return;
    Rint ll(0);
    for(Rint v: E[u]) if(v != f && v != son[u]) chkmax(ll, len[v]);
    while(tp != st && dep[u] - dep[*tp] <= ll)
        (tg == tp) && del(*tg--), --tp;
    //弹掉距离 u 不超过次长链长度的点
    *++tp = u;
    dfs2(son[u], u);
    for(Rint v: E[u]){
        if(v == f || v == son[u]) continue;
        while(tp != st && dep[u] - dep[*tp] <= len[u] - 1)
            (tg == tp) && del(*tg--), --tp;
        //弹掉距离 u 不超过最长链长度的点
        if(*tp != u) *++tp = u;
        //u 可能不需要弹掉
        dfs2(v, u);
    }
    //不必把栈内留存的 u 子树内的点弹掉
    //因为会在考虑到 u 的兄弟时弹掉
}

inline void sol(int S){
    dfs1(S, 0);
    memset(c, 0, sizeof(c));
    g = 0, tg = tp = st;
    dfs2(S, 0);
}

int main() {
    fin >> n >> m;
    Rint u, v;
    FOR(i, 1, n - 1){
        fin >> u >> v;
        E[u].push_back(v), E[v].push_back(u);
    }
    FOR(i, 1, n) fin >> a[i];
    Rint S(0), T(0);
    init(1, 0, S), init(S, 0, T);
    sol(S), sol(T);
    FOR(i, 1, n) fout << ans[i];
    return 0;
}