P3180 [HAOI2016] 地图

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;
}