@[caihaolang](/user/363036) 把 `map` 换成 `unordered_map`，再把 `col` 数组离散化一下？
by Adchory @ 2022-12-30 16:17:19
@[Reimu_Hakurei](/user/590600) 我就是懒得写离散化\kk。
by chlchl @ 2022-12-30 16:18:00
离散化之后第 10 个点 WA 了。
by chlchl @ 2022-12-30 16:24:07
为什么啊啊啊啊啊
by chlchl @ 2022-12-30 16:37:28
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 2e5 + 10;
int n, m, blk, a[N], col[N], dep[N], f[N][17];
int clk, in[N], out[N], euler[N << 1];
int id, head[N << 1], nxt[N << 1], to[N << 1];
int tot, tcol[N], ans[M];
bool vis[N];
struct event{
int s, t, idx;
bool operator < (const event &p) const {
if(s / blk != p.s / blk) return s < p.s;
return t < p.t;
}
} q[M];
void add(int u, int v){
to[++id] = v;
nxt[id] = head[u], head[u] = id;
}
void dfs(int u, int fa){
f[u][0] = fa;
in[u] = ++clk, euler[clk] = u;
for(int i=1;i<=16;i++)
f[u][i] = f[f[u][i - 1]][i - 1];
for(int i=head[u];i;i=nxt[i]){
int v = to[i];
if(v == fa)
continue;
dep[v] = dep[u] + 1;
dfs(v, u);
}
out[u] = ++clk, euler[clk] = u;
}
int lca(int u, int v){
if(dep[u] < dep[v])
swap(u, v);
for(int i=16;i>=0;i--)
if(dep[f[u][i]] >= dep[v])
u = f[u][i];
if(u == v)
return u;
for(int i=16;i>=0;i--)
if(f[u][i] != f[v][i])
u = f[u][i], v = f[v][i];
return f[u][0];
}
void calc(int k){
if(vis[k]){
--tcol[col[k]];
if(tcol[col[k]] == 0)
--tot;
}
else{
++tcol[col[k]];
if(tcol[col[k]] == 1)
++tot;
}
vis[k] ^= 1;
}
int main(){
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++)
scanf("%d", &col[i]), a[i] = col[i];
sort(a + 1, a + 1 + n);
int len = unique(a + 1, a + 1 + n) - a - 1;
for(int i=1;i<=n;i++)
col[i] = lower_bound(a + 1, a + 1 + len, col[i]) - a;
for(int i=1,u,v;i<n;i++){
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
}
dfs(1, 0);
// for(int i=1;i<=clk;i++)
// cout << euler[i];
blk = sqrt(clk);
for(int i=1,u,v;i<=m;i++){
scanf("%d%d", &u, &v);
if(dep[u] > dep[v])
swap(u, v);
if(lca(u, v) == u)
q[i] = (event){in[u], in[v], i};
else
q[i] = (event){out[u], in[v], i};
}
sort(q + 1, q + 1 + m);
// for(int i=1;i<=m;i++)
// cout << q[i].s << ' ' << q[i].t << endl;
int l = 1, r = 0;
for(int i=1;i<=m;i++){
while(r < q[i].t)
calc(euler[++r]);
while(l > q[i].s)
calc(euler[--l]);
while(r > q[i].t)
calc(euler[r--]);
while(l < q[i].s)
calc(euler[l++]);
int chl = lca(euler[q[i].s], euler[q[i].t]);
if(chl != euler[q[i].s])
calc(chl);
ans[q[i].idx] = tot;
if(chl != euler[q[i].s])
calc(chl);
}
for(int i=1;i<=m;i++)
printf("%d\n", ans[i]);
return 0;
}
```
#10 WA。
by chlchl @ 2022-12-30 16:37:47
这井号怎么自动给我渲染了
by chlchl @ 2022-12-30 16:38:26