自动搬运

查看原文

来自洛谷，原作者为

	p878567 以下证明：这一算法的时空复杂度是 $o(+\infty)$

搬运于2025-08-24 21:34:41，当前版本为作者最后更新于2019-08-02 13:31:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

下面是一个不基于树分块的做法（树分块对块数无法保证，可以用菊花图卡掉）：

虽然这个做法也可以被卡，但必须针对块长（一条链，平分第一块，前一半2操作，后一半3操作，然后询问）。

前置知识：Gty的妹子树

上面这题$O(n^{1.5}\log n)$的解法：对树的DFS序建划分树（线段树的一种，运用归并排序的方法在各个节点维护对应区间内元素排好序的结果，可以$O(logn)$询问区间k大，不支持修改），对每个询问先找到划分树上的结果，然后暴力讨论每个修改对答案的影响，积累到$O(\sqrt{n})$个询问后暴力重建划分树。

如无法理解上面这段话请出门左转该题题解。

现在我们讨论3号操作对答案的影响。（假设当前询问节点为$u$）（先忽略1、2操作）

1.这一操作的节点不是$u$的儿子。它对答案没有影响。$O(1)$

2.这一操作的节点在$u$为根的子树中，并且$u$到该节点的路径上没有其他节点被3号操作影响。那么该节点为根的子树中各个节点都不应当被计入答案（但实际上都被计入了），只要把这一部分的答案去掉即可（在划分树上询问）。$O(\log n)$

3.这一操作的节点在$u$为根的子树中，但$u$到该节点的路径上还有其他节点被3操作影响。那么这一节点对答案的影响已被去除，无需修改。$O(1)$

上面有两个问题：询问是否在$u$为根的子树中（解法：维护每个节点向上跳$2^i$后的节点）、询问某路径（两端点间有祖先——后代关系）上是否有节点被3操作影响（解法：先转化为对被3操作影响的节点进行计数，树上差分转化为对根到某一节点被3操作影响的节点进行计数，则每个3操作对以它为根的子树中的节点有贡献，可以在划分树中节点多开一个变量维护）

1号操作对答案的影响：

1.这一操作的节点不是$u$的儿子。它对答案没有影响。$O(1)$

2.这一操作的节点在$u$为根的子树中，并且$u$到该节点的路径上没有节点被3号操作影响。那么该节点可能对答案有影响，记录修改前后的权值不难判断。$O(1)$

3.这一操作的节点在$u$为根的子树中，但$u$到该节点的路径上还有其他节点被3操作影响。那么这一节点对答案的影响已被去除，无需修改。$O(1)$

2号操作对答案的影响：

1.这一操作的节点不是$u$的儿子。它对答案没有影响。$O(1)$

2.这一操作的节点在$u$为根的子树中，并且$u$到该节点的路径上没有节点被3号操作影响。那么该节点可能对答案有影响，不难判断。$O(1)$

3.这一操作的节点在$u$为根的子树中，但$u$到该节点的路径上还有其他节点被3操作影响。那么这一节点对答案的影响已被去除，无需修改。$O(1)$

下面有一个重要的东西：

维护根到2号操作中新建节点的路径上被3操作影响的节点数（开一个数组记录）：

1.新建了一个节点。那么新建的节点可以继承其父亲的答案。

2.产生了被3操作影响的节点。暴力扫描新建的节点，判断是否被影响。

以下是复杂度分析：

1操作：记录修改其前后的权值$O(1)$，总计$O(n)$

2操作：基础维护$O(1)$，维护向上跳$2^i$后的节点$O(\log n)$，继承父亲的被影响节点数$O(\log n)$，总计$O(n\log n)$

3操作：修改影响到的节点（原树中的节点）$O(\log n)$，（新建的节点）$O(\sqrt{n}\log n)$，总计$O(n^{1.5}\log n)$

询问：可以发现为$O(n^{1.5}\log n)$

重建：单次$O(n\log n)$，总计$O(n^{1.5}\log n)$

因此总复杂度仍为$O(n^{1.5}\log n)$

实现细节：

看着不长，写完以后发现和树套树差不多……

准备对拍吧（去掉重建部分对拍一次，每次重建再对拍一次）

块长取大一点，恰好$\sqrt{n}$容易被卡常（如果知道为什么请私信）

#include<bits/stdc++.h>
using namespace std;
int read() {
	char c=getchar();while(!isdigit(c))c=getchar();
	int num=0;while(isdigit(c))num=num*10+c-'0',c=getchar();
	return num;
}
void write(int num){if(num>=10)write(num/10);putchar(num%10+'0');}
int head[200001], ver[400001], nxt[400001], sz;
void addedge(int u, int v) {
	ver[++sz] = v, nxt[sz] = head[u], head[u] = sz;
	ver[++sz] = u, nxt[sz] = head[v], head[v] = sz;
}
int fa[200001], dep[200001];
void dfs(int x) {
	for (int i = head[x]; i; i = nxt[i])
		if (fa[x] != ver[i]) {
			fa[ver[i]] = x;
			dep[ver[i]] = dep[x] + 1;
			dfs(ver[i]);
		}
}
int n;
int seq[200001], pt[200001];
int top;
int size[200001];
int w[200001];
void getsq(int x) {
	seq[++top] = x, pt[x] = top;
	size[x] = 1;
	for (int i = head[x]; i; i = nxt[i])
		if (fa[ver[i]] == x) {
			getsq(ver[i]);
			size[x] += size[ver[i]];
		}
}
int bf;
vector<int> sq[800001];
int dat[800001];
int cnt[800001];
int out[100001];
void erase(int p, int l, int r) {
	sq[p].clear();
	dat[p] = cnt[p] = 0;
	if (l == r) return;
	int mid = (l + r) / 2;
	erase(p * 2, l, mid);
	erase(p * 2 + 1, mid + 1, r);
}
void pushdown(int p, int l, int r) {
	int mid = (l + r) / 2;
	cnt[p*2] += dat[p]*(mid-l+1);
	cnt[p*2+1] += dat[p]*(r-mid);
	dat[p*2] += dat[p];
	dat[p*2+1] += dat[p];
	dat[p] = 0;
}
void init(int p, int l, int r) {
	if (l == r) {sq[p].push_back(w[seq[l]]);return;}
	int mid = (l + r) / 2;
	init(p * 2, l, mid);
	init(p * 2 + 1, mid + 1, r);
	int p1 = 0, p2 = 0;
	while (p1 < sq[p*2].size() && p2 < sq[p*2+1].size())
		if (sq[p*2][p1]<sq[p*2+1][p2]) sq[p].push_back(sq[p*2][p1++]);
		else sq[p].push_back(sq[p*2+1][p2++]);
	while (p1 < sq[p*2].size()) sq[p].push_back(sq[p*2][p1++]);
	while (p2 < sq[p*2+1].size()) sq[p].push_back(sq[p*2+1][p2++]);
}
void insert(int p, int l, int r, int l0, int r0) {
	if (l0 >= l && r0 <= r) {
		++dat[p];
		cnt[p] += r0 - l0 + 1;
		return;
	}
	pushdown(p, l0, r0);
	int mid = (l0 + r0) / 2;
	if (l <= mid) insert(p * 2, l, r, l0, mid);
	if (r > mid) insert(p * 2 + 1, l, r, mid + 1, r0);
	cnt[p] = cnt[p*2] + cnt[p*2+1];
}
int query(int p, int l0, int r0, int u) {
	if (l0 == r0) return cnt[p];
	pushdown(p, l0, r0);
	int mid = (l0 + r0) / 2;
	if (u <= mid) return query(p * 2, l0, mid, u);
	else return query(p * 2 + 1, mid + 1, r0, u);
}
int query(int p, int l, int r, int l0, int r0, int k) {
	if (l0 >= l && r0 <= r) return sq[p].end() - upper_bound(sq[p].begin(), sq[p].end(), k);
	int ans = 0, mid = (l0 + r0) / 2;
	if (l <= mid) ans += query(p * 2, l, r, l0, mid, k);
	if (r > mid) ans += query(p * 2 + 1, l, r, mid + 1, r0, k);
	return ans;
}
int qu(int u, int maxn) {
	if (u > maxn) return out[u];
	return query(1, 1, maxn, pt[u]);
}
int f[200001][20];
void build() {
    top = 0;
	for (int i = 1; i <= n; i++) if (!fa[i]) getsq(i);
	erase(1, 1, bf);
	memset(f, 0, sizeof(f));
	for (int i = 1; i <= n; i++) f[i][0] = fa[i];
	for (int j = 1; j <= 18; j++)
		for (int i = 1; i <= n; i++)
			f[i][j] = f[f[i][j-1]][j-1];
	init(1, 1, n);
}
inline int jmp(int x, int d) {
	for (int i = 18; i >= 0; i--)
		if (dep[f[x][i]] >= d)
			x = f[x][i];
	return x;
}
struct cmd {
	int op, u, x, x0;
}c[100001];
int main() {
	n = read();
	for (int i = 1; i < n; i++) {
		int u = read(), v = read();
		addedge(u, v);
	}
	dep[1] = 1;
	dfs(1);
	for (int i = 1; i <= n; i++) w[i] = read();
	bf = n;
	build();
	int m = read();
	int s = sqrt(m) * 4;
	int q = 1;
	int lastans = 0;
	for (int i = 1; i <= m; i++) {
		int op = read();
		switch (op) {
			case 0: {
				int u = read() ^ lastans, x = read() ^ lastans;
				int ans = 0;
				if (u <= bf) ans = query(1, pt[u], pt[u]+size[u]-1, 1, bf, x);
				for (int j = 1; j < q; j++) {
					if (c[j].op == 1) {
						if (jmp(c[j].u, dep[u]) != u || qu(c[j].u, bf) > qu(u, bf)) continue;
						if (c[j].x > x) ++ans;
						if (c[j].x0 > x) --ans;
					}
					if (c[j].op == 2) {
						if (jmp(c[j].u, dep[u]) != u || qu(c[j].u, bf) > qu(u, bf)) continue;
						if (c[j].x > x) ++ans;
					}
					if (c[j].op == 3) {
						if (c[j].u > bf || jmp(c[j].u, dep[u]) != u || qu(fa[c[j].u], bf) != qu(u, bf)) continue;
						ans -= query(1, pt[c[j].u], pt[c[j].u]+size[c[j].u]-1, 1, bf, x);		
					}
				}
				write(lastans = ans);
				putchar('\n');
				break;
			}
			case 1: {
				int u = read() ^ lastans, x = read() ^ lastans;
				c[q].op = op, c[q].u = u, c[q].x = x, c[q].x0 = w[u];
				w[u] = x;
				++q;
				break;
			}
			case 2: {
				int u = read() ^ lastans, x = read() ^ lastans;
				++n;
				fa[n] = u, w[n] = x, dep[n] = dep[u] + 1;
				f[n][0] = u;
				addedge(n, u);
				for (int i = 1; i <= 18; i++) f[n][i] = f[f[n][i-1]][i-1];
				out[n] = qu(u, bf);
				c[q].op = op, c[q].u = n, c[q].x = x;
				++q;
				break;
			}
			case 3: {
				int u = read() ^ lastans;
				if (u <= bf) insert(1, pt[u], pt[u]+size[u]-1, 1, bf);
				for (int j = bf + 1; j <= n; j++)
					if (jmp(j, dep[u]) == u) ++out[j];
				c[q].op = op, c[q].u = u;
				++q;
				break;
			}
		}
		if (q > s) {
			for (int j = 1; j <= q; j++)
				if (c[j].op == 3) fa[c[j].u] = 0;
			q = 1;
			bf = n;
			build();
		}
	}
}