Luogu6018 [Ynoi2010] Fusion tree

tony102

2021 年 05 月 30 日

1947 次浏览

暂无评论

956字数

题解

[Link](https://www.luogu.com.cn/problem/P6018)

## Sol

对于一个点来说,在树上距离为 $1$ 的点, 只有父亲和儿子. 维护一个点的所有儿子对它的贡献,单独处理父亲对自己的,那么每个点唯一对应一个父亲,这样是方便容易维护的.

Trie 树是无法对应一个区间之类的东西的.所以只能对每一个点建一棵 01 Trie 维护其儿子的值. 那么现在要支持的操作就是全局 $+1$ 和回答全局异或和. 第二个操作可以通过打标记的方式处理掉.

考虑细节, 在做全局 $+1$ 的操作时要考虑对父亲和爷爷的影响. 加入爷爷是根节点则不处理.否则更新

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 5e5 + 5;
const int MAX = 20;

int n, m, tot, num;
int head[SIZE], fa[SIZE], a[SIZE], tag[SIZE], root[SIZE * 60];

struct node {
	int to, nxt;
} edge[SIZE << 1];

struct trie {
	int w, sum, son[2];
} t[SIZE * 60];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

#define lson(p) t[p].son[0]
#define rson(p) t[p].son[1]

void addEdge(int u, int v) {
	edge[++ num] = (node) {v, head[u]}, head[u] = num;
}

void dfs(int u, int anc) {
	fa[u] = anc;
	for (int i = head[u], v; i; i = edge[i].nxt) {
		v = edge[i].to;
		if (v == anc) continue;
		dfs(v, u);
	}
}

void upd(int p) {
	t[p].w = t[lson(p)].w + t[rson(p)].w, t[p].sum = 0;
	if (lson(p)) t[p].sum ^= t[lson(p)].sum << 1;
	if (rson(p)) t[p].sum ^= (t[rson(p)].sum << 1) | (t[rson(p)].w & 1);
	t[p].w &= 1;
}

void insert(int &p, int x, int dep = 0) {
	if (!p) p = ++ tot;
	if (dep > MAX) return ++ t[p].w, void();
	insert(t[p].son[x & 1], x >> 1, dep + 1); upd(p);
}

void del(int &p, int x, int dep = 0) {
	if (dep > MAX) return -- t[p].w, void();
	del(t[p].son[x & 1], x >> 1, dep + 1); upd(p);
}

void add(int p) {
	std::swap(lson(p), rson(p));
	if (lson(p)) add(lson(p));
	upd(p);
}

int judge(int x) { return (fa[x] == -1 ? 0 : tag[fa[x]]) + a[x]; }

int main() {
	// freopen("code.in", "r", stdin);
	n = read(), m = read();
	for (int i = 1, u, v; i < n; ++ i) {
		u = read(), v = read();
		addEdge(u, v), addEdge(v, u);
	}
	dfs(1, -1);
	for (int i = 1; i <= n; ++ i) {
		a[i] = read();
		if (fa[i] != -1) insert(root[fa[i]], a[i]);
	}
	int opt, x, v;
	while (m --) {
		opt = read(), x = read();
		if (opt == 1) {
			++ tag[x];
			if (x != 1) {
				if (fa[fa[x]] != -1) del(root[fa[fa[x]]], judge(fa[x]));
				++ a[fa[x]];
				if (fa[fa[x]] != -1) insert(root[fa[fa[x]]], judge(fa[x]));
			}
			add(root[x]);
		}
		if (opt == 2) {
			v = read();
			if (x != 1) del(root[fa[x]], judge(x));
			a[x] -= v;
			if (x != 1) insert(root[fa[x]], judge(x));
		}
		if (opt == 3) {
			int res = t[root[x]].sum;
			res ^= judge(fa[x]);
			printf("%d\n", res);
		}
	}
	return 0;
}
```

最后修改：2021 年 09 月 07 日