SP10707 COT2 - Count on a tree II

72 阅读 0 评论 48 点赞

我是靠谱客的博主耍酷烧鹅，最近开发中收集的这篇文章主要介绍SP10707 COT2 - Count on a tree II，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

原题链接
树上莫队模板.
预处理给定数的欧拉序列eul, 记i在eul中第一次出现的位置为fir[N], 第二次出现的位置为sec[N],
对于任意x, y, 不妨设fir[x] < fir[y].
若lca(x, y) == x, 则x->y的路径经过的点为eul[fir[x], fir[y]]中只出现一次的点.
若lca(x, y) != x, 则x->y的路径经过的点为eul[las[x], fir[y]]中只出现一次的点 + lca(x, y) .
对于本题，维护cnt, st, 其中st[i]表示i在eul中出现次数的奇偶, cnt[i]表示eul中c[y] = i&&st[y] = 1的y的个数.
用普通莫队维护即可.
注意：①cnt, st数组含义②各数组范围
代码如下：

#include <cstdio>
#include <cctype>
#include <cmath>
#include <algorithm>
using namespace std;
inline int read() {
int x = 0, f = 0; char ch = getchar();
while (!isdigit(ch)) f = ch == '-', ch = getchar();
while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int x) {
if (x < 0) putchar('-'), x = -x;
if (x < 10) putchar(x
+ '0');
else {
print(x / 10);
putchar(x % 10 + '0');
}
}
const int N = 40010, M = 1e5 + 100;
int n, m;
int head[N], nex[N << 1], ver[N << 1], tot;
int fa[N][17], dep[N];
int c[N], ans[M];
int tmp[N], len;
int eul[N << 1], top, fir[N], las[N];
int pos[N << 1], block;
int cnt[N], st[N];
struct Ask {
int l, r, id, opt;
};
Ask a[M];
bool cmp1(Ask x, Ask y) {
if (pos[x.l] == pos[y.l]) return x.r < y.r;
else return x.l < y.l;
}
void Addedge(int x, int y) {
ver[++tot] = y;
nex[tot] = head[x];
head[x] = tot;
}
void dfs(int x, int fat) {
eul[++top] = x; fir[x] = top;
dep[x] = dep[fat] + 1;
fa[x][0] = fat;
for (int i = 1; i < 17; ++i) fa[x][i] = fa[fa[x][i - 1]][i - 1];
for (int i = head[x]; i; i = nex[i]) {
int y = ver[i];
if (y == fat) continue;
dfs(y, x);
}
eul[++top] = x; las[x] = top;
}
int lca(int x, int y) {
if (dep[x] > dep[y]) swap(x, y); // dep[x] <= dep[y]
while (dep[x] != dep[y]) y = fa[y][(int)log2(dep[y] - dep[x])];
if (x == y) return x;
for (int j = 16; j >= 0; --j) {
if (fa[x][j] != fa[y][j]) {
x = fa[x][j]; y = fa[y][j];
}
}
return fa[x][0];
}
void update(int x, int& res)
{
st[x] ^= 1;
if (st[x] == 0)
{
cnt[c[x]] -- ;
if (!cnt[c[x]]) res -- ;
}
else
{
if (!cnt[c[x]]) res ++ ;
cnt[c[x]] ++ ;
}
}
void Solve() {
int l = 1, r = 0, res = 0;
for (int i = 1; i <= m; ++i) {
while (a[i].l < l) { update(eul[--l], res); }
while (a[i].l > l) { update(eul[l++], res); }
while (a[i].r < r) { update(eul[r--], res); }
while (a[i].r > r) { update(eul[++r], res); }
if (a[i].opt) update(a[i].opt, res);
ans[a[i].id] = res;
if (a[i].opt) update(a[i].opt, res);
}
}
int main() {
n = read(); m = read();
for (int i = 1; i <= n; ++i) c[i] = tmp[i] = read();
sort(tmp + 1, tmp + n + 1);
len = unique(tmp + 1, tmp + n + 1) - (tmp + 1);
for (int i = 1; i <= n; ++i) c[i] = lower_bound(tmp + 1, tmp + len + 1, c[i]) - tmp;
for (int i = 1; i < n; ++i) {
int uu = read(), vv = read();
Addedge(uu, vv); Addedge(vv, uu);
}
dfs(1, 0);
for (int i = 1; i <= m; ++i) {
int uu = read(), vv = read(), f = lca(uu, vv);
if (f == uu || f == vv) {
a[i].l = fir[uu]; a[i].r = fir[vv]; a[i].opt = 0; a[i].id = i;
if (a[i].l > a[i].r) swap(a[i].l, a[i].r);
} else {
if (fir[uu] > fir[vv]) swap(uu, vv);
a[i].l = las[uu]; a[i].r = fir[vv]; a[i].opt = f; a[i].id = i;
}
}
block = sqrt(n << 1);
for (int i = 1; i <= (n << 1); ++i) pos[i] = i / block + 1;
sort(a + 1, a + m + 1, cmp1);
Solve();
for (int i = 1; i <= m; ++i) {
print(ans[i]); putchar('n');
}
}