bzoj 3720 Gty的妹子树

Posted on | Views:

树上分块.

考虑对树分块,限制块大小为 $\sqrt n$ .

加入一个点时,若它的父亲所在块大小达到了 $\sqrt n$ ,就给它新建一个块,否则将它加入父亲所在块.

对于每个块,用一个数组维护块内所有的权值,若有修改,直接将它重新 sort 一遍.

询问时,从 u 开始向下 dfs ,遇到 u 所在的块,暴力统计,遇到其他块,在维护的权值数组中二分即可算出贡献.

时间复杂度 $O(n\sqrt n \log n)$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=6e4+10,B=250;
int n,m,lastans=0,ecnt=0,head[MAXN],to[MAXN<<1],nx[MAXN<<1];
void addedge(int u,int v)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
int w[MAXN],bel[MAXN],tot=0;
struct Block
{
	int siz,val[B];
	void Sort()
	{
		sort(val,val+siz);
	}
	void add(int x)
	{
		val[siz++]=w[x];
		Sort();
	}
	void modify(int x,int y)
	{
		int pos=lower_bound(val,val+siz,w[x])-val;
		val[pos]=w[x]=y;
		Sort();
	}
	int query(int x)
	{
		return siz-(upper_bound(val,val+siz,x)-val);
	}
}b[MAXN];
int Fa[MAXN];
vector<int> G[MAXN];
void dfs(int u,int fa)
{
	Fa[u]=fa;
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==fa)
			continue;
		if(b[bel[u]].siz==B)
		{
			bel[v]=++tot;
			b[tot].add(v);
			G[bel[u]].push_back(tot);
		}
		else
		{
			bel[v]=bel[u];
			b[bel[v]].add(v);
		}
		dfs(v,u);
	}
}
int dfs_block(int u,int x)
{
	int res=b[u].query(x);
	for(int i=0;i<(signed)(G[u].size());++i)
	{
		int v=G[u][i];
		res+=dfs_block(v,x);
	}
	return res;
}
int dfs_calc(int u,int x)
{
	int res=0;
	if(w[u]>x)
		++res;
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==Fa[u])
			continue;
		if(bel[v]==bel[u])
			res+=dfs_calc(v,x);
		else
			res+=dfs_block(bel[v],x);
	}
	return res;
}
int main()
{
	n=read();
	for(int i=1;i<n;++i)
	{
		int u=read(),v=read();
		addedge(u,v);
		addedge(v,u);
	}
	for(int i=1;i<=n;++i)
		w[i]=read();
	bel[1]=++tot;
	b[tot].add(1);
	dfs(1,0);
	int m=read();
	for(int i=1;i<=m;++i)
	{
		int op=read(),x=read()^lastans,y=read()^lastans;
		if(op==0)
			printf("%d\n",lastans=dfs_calc(x,y));
		else if(op==1)
			b[bel[x]].modify(x,y);
		else
		{
			int z=++n;
			w[z]=y;
			addedge(x,z);
			if(b[bel[x]].siz==B)
			{
				bel[z]=++tot;
				b[tot].add(z);
				G[bel[x]].push_back(tot);
			}
			else
			{
				bel[z]=bel[x];
				b[bel[z]].add(z);
			}
		}
	}
	return 0;
}