P9067 [Ynoi Easy Round 2022] 虚空处刑 题解
5k_sync_closer
·
·
题解
谁告诉你 Ynoi 就要手写数据结构了？
维护 map<int, list<int>> C[N]，C_{i,j} 表示与 i 点所在连通块相邻的 j 色连通块序列。
lxl 说过，这种邻域信息维护父亲一定死，所以令 $C_{i,j}$ 表示在 $i$ 点所在连通块下方的 $j$ 色连通块序列。
$a_x\gets y$ 时，直接对 $C_x$ 和 $C_i|i\in C_{x,y}$ 启发式合并，然后发现只需要更新 $C_{\text{fa}_x,y}$ 了。
这里没必要从 $C_{\text{fa}_x,a_x}$ 里删掉 $x$，启发式合并的时候判断一下是不是真的要合并就行了。
`unordered_map` 跑不过 `map`。
```cpp
#include <map>
#include <list>
#include <cstdio>
using namespace std;
struct E
{
int v, t;
} e[1000050];
map<int, list<int>> C[1000050];
int n, m, c, a[1000050], s[1000050], f[1000050], g[1000050], h[1000050];
void A(int u, int v)
{
e[++c] = {v, h[u]};
h[u] = c;
}
int F(int x) { return x == f[x] ? x : f[x] = F(f[x]); }
void L(int u, int v)
{
f[v = F(v)] = u = F(u);
s[u] += s[v];
}
void D(int u, int k)
{
for (int i = h[u], v; i; i = e[i].t)
if ((v = e[i].v) != k)
{
g[v] = u;
if (a[v] == a[u])
L(u, v);
else
C[F(u)][a[v]].push_back(v);
D(v, u);
}
}
void M(int x, int y)
{
if (C[x].size() < C[y].size())
swap(C[x], C[y]);
for (auto i : C[y])
C[x][i.first].splice(C[x][i.first].end(), i.second);
C[y].clear();
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 2, x; i <= n; ++i)
scanf("%d", &x), A(x, i);
for (int i = 1; i <= n; ++i)
scanf("%d", a + i), s[f[i] = i] = 1;
D(1, 0);
for (int i = 0, o, x, y, z; i < m; ++i)
{
scanf("%d%d", &o, &x);
x = F(x);
if (o & 1)
{
scanf("%d", &y);
if (a[x] == y)
continue;
auto l = C[x][y];
for (auto i : l)
if (y == a[i] && x != F(i))
L(x, i), M(x, i);
if (y == a[z = F(g[x])])
L(z, x), M(z, x);
else if (z)
C[z][y].push_back(x);
C[F(x)][a[x] = y].clear();
}
else
printf("%d\n", s[x]);
}
return 0;
}
```