Problem
给出 \(n\) 个点 \(m\) 条边的无向连通图，且每条边最多被包含在一个环中，每个点有颜色，有 \(q\) 次询问，每次询问给出一个点 \(x\) 和参数 \(y\)，假如将 \(1\) 到 \(x\) 所有简单路径上的边删去后，从 \(x\) 出发，能到达的所有点中，颜色编号小于等于 \(y\) 且出现次数为奇数或偶数次的颜色有几种（没出现的颜色不统计）。
Input
一行两个整数 \(n,m\) 表示点数和边数
一行 \(n\) 个整数，表示每个点的颜色
\(m\) 行，每行两个整数 \(x,y\) 表示一条无向边
一行一个整数 \(q\)，表示询问数
\(q\) 行，每行三个整数 \(opt,x,y\)，\(opt=0\) 时询问偶数，\(opt=1\) 时询问奇数
Output
一共 \(q\) 行，对于每个询问输出一个答案。
Sample
Input 1
10 12
1 10 4 5 2 10 1 8 4 8
1 2
1 3
1 4
2 5
4 6
4 7
7 8
2 9
8 10
1 6
8 10
4 7
10
0 3 9
1 7 6
0 5 2
1 10 9
0 5 7
1 7 4
0 7 3
1 2 7
0 3 4
0 3 8
Output 1
0
1
0
1
0
1
0
2
0
0
Solution
不难发现一个性质，对原图建圆方树，那么删去 \(1\) 到 \(x\) 的所有简单路径后 \(x\) 所到达的点只有 \(x\) 的子树了。那么原问题就转化成一个经典的问题了,我们需要维护好子树内颜色出现的奇偶情况即可，可以考虑树上启发式合并套树状数组的方式求解。
代码：
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int kmax = 1e6 + 3;
struct E {
int p, y;
} e[kmax << 1];
struct Q {
int k, op, id;
};
int n, m, q;
int h[kmax], ec;
int ct;
int col[kmax];
int c[2][kmax];
vector<int> ee[kmax];
int dfn[kmax], low[kmax], idx;
int stk[kmax], tp;
int siz[kmax], son[kmax], num[kmax];
vector<Q> qry[kmax];
int bc[kmax];
int res[kmax];
int l[kmax], r[kmax];
void Addedge(int x, int y) {
e[++ec] = {h[x], y};
h[x] = ec;
}
void Tarjan(int x) { // 求点双
dfn[x] = low[x] = ++idx;
stk[++tp] = x;
for (int i = h[x]; i; i = e[i].p) {
int y = e[i].y;
if (!dfn[y]) {
Tarjan(y);
low[x] = min(low[x], low[y]);
if (dfn[x] == low[y]) {
ct++;
for (int z = 0; z != y; tp--) {
z = stk[tp];
ee[z].push_back(ct);
ee[ct].push_back(z);
// cout << z << ' ' << ct << '\n';
}
ee[x].push_back(ct);
ee[ct].push_back(x);
// cout << x << ' ' << ct << '\n';
}
} else {
low[x] = min(low[x], dfn[y]);
}
}
}
int Lowbit(int x) {
return x & -x;
}
void Modify(int x, int op, int v) {
for (; x < kmax; x += Lowbit(x)) { // 树状数组修改
c[op][x] += v;
}
}
int Getres(int x, int op) {
int tot = 0;
for (; x; x -= Lowbit(x)) {
tot += c[op][x];
}
return tot;
}
void Dfs(int x, int fa) {
l[x] = ++idx;
num[idx] = x;
siz[x] = 1;
for (int y : ee[x]) {
if (y == fa) continue;
Dfs(y, x);
siz[x] += siz[y];
if (siz[y] > siz[son[x]]) {
son[x] = y;
}
}
r[x] = idx;
}
void Change(int x, int v) {
if (bc[x]) {
Modify(x, bc[x] & 1, -1);
}
bc[x] += v;
if (bc[x]) {
Modify(x, bc[x] & 1, 1);
}
}
void Dfss(int x, int fa) {
for (int y : ee[x]) {
if (y == fa || y == son[x]) continue;
Dfss(y, x); // 先处理轻儿子
for (int i = l[y]; i <= r[y]; i++) {
Change(col[num[i]], -1);
}
}
if (son[x]) Dfss(son[x], x); // 处理重儿子
Change(col[x], 1); // 加入根节点
for (int y : ee[x]) {
if (y == fa || y == son[x]) continue;
for (int i = l[y]; i <= r[y]; i++) {
Change(col[num[i]], 1); // 将轻儿子的结果加入
}
}
for (Q cur : qry[x]) {
res[cur.id] = Getres(cur.k, cur.op); // 处理询问
}
}
int main() {
ios::sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> col[i];
col[i]++;
}
for (int i = 1, x, y; i <= m; i++) {
cin >> x >> y;
Addedge(x, y);
Addedge(y, x);
}
ct = n;
for (int i = 1; i <= n; i++) {
if (dfn[i]) continue;
Tarjan(i); // 建圆方树
}
for (int i = n + 1; i <= ct; i++) {
col[i] = kmax - 1; // 方点颜色设为极大值
}
// cout << "ct = " << ct << '\n';
cin >> q;
for (int i = 1, op, x, k; i <= q; i++) {
cin >> op >> x >> k;
k++;
qry[x].push_back({k, op, i});
}
idx = 0;
Dfs(1, 0);
// for(int i = 1; i <= ct; i++) {
// cout << i << ' ' << l[i] << ' ' << r[i] << '\n';
// }
Dfss(1, 0); // 树上启发式合并
for (int i = 1; i <= q; i++) {
cout << res[i] << '\n';
}
return 0;
}