题解 模板

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010
#define ll long long 
#define fir first
#define sec second
#define make make_pair
//#definE int long long 

char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inlinE int read() {
	int ans=0, f=1; char c=getchar();
	while (!isdigit(C)) {if (c=='-') f=-f; c=getchar();}
	while (isdigit(C)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
	return ans*f;
}

int n, m, q;
int head[n], size, k[n], uni[n], usize, qx[n], qc[n], ans[n], siz2[n], msiz[n], mson[n];
struct edge{int to, next;}e[N<<1];
inline void add(int s, int t) {e[++size].to=t; e[size].next=head[s]; head[s]=size;}

int tot, rab[N<<3], rtop;
int siz[N<<3], col[N<<3], tim[N<<3], val[N<<3], sum[N<<3], son[N<<3][2], fa[N<<3];
#define siz(p) siz[p]
#define col(p) col[p]
#define tim(p) tim[p]
#define val(p) val[p]
#define sum(p) sum[p]
#define son(a, b) son[a][b]
#define fa(p) fa[p]
#define loc(p) (son(fa(p), 1)==p)
#define tran(a, X) son(a, (X)>tim(a))
#define pushup(p) 	sum(p)=sum(son(p, 0))+sum(son(p, 1))+val(p);
					siz(p)=siz(son(p, 0))+siz(son(p, 1))+1
struct Splay{
	int rot;
	unordered_map< int, pair<int, int> > mp;
	Splay():rot(0){ins(-INF, -1, 0); ins(INF, -1, 0);}
	void ror(int X) {
		int y=fa(X), z=fa(y), k=loc(X);
		son(z, loc(y))=x; fa(X)=z;
		son(y, k)=son(x, k^1); fa(son(x, k^1))=y;
		son(x, k^1)=y; fa(y)=x;
		pushup(y); pushup(X);
	}
	void splay(int x, int pos) {
		int y, z;
		while (fa(X)!=pos) {
			y=fa(X), z=fa(y);
			if (z!=pos) loc(X)^loc(y)?ror(X):ror(y);
			ror(X);
		}
		if (!pos) rot=x;
	}
	void ins(int t, int c, int d) {
		//if (c!=-1) cout<<"ins: "<<t<<' '<<c<<' '<<d<<endl;
		if (d && mp.find(C)!=mp.end()) {
			pair<int, int> tem=mp[c];
			if (tem.fir<t) d=0;
			else {
				val(tem.seC)=0;
				splay(tem.sec, 0);
			}
		}
		int u=rot, f=0;
		while (u) f=u, u=tran(u, t);
		//u=(rtop?rab[rtop--]:++tot);
		u=++tot;
		siz(u)=1; col(u)=c; tim(u)=t;
		val(u)=sum(u)=d;
		if (f) tran(f, t)=u;
		if (d) mp[c]=make(t, u);
		son(u, 0)=son(u, 1)=0; fa(u)=f;
		splay(u, 0);
		//if (c!=-1) cout<<"u: "<<u<<' '<<val(u)<<' '<<sum(u)<<endl;
	}
	void find(int X) {
		int u=rot;
		while (u&&tran(u, X)) u=tran(u, X);
		splay(u, 0);
	}
	int rk(int X) {
		//cout<<"rk: "<<x<<' '<<siz(rot)<<endl;
		int u=rot, v;
		if (x>=siz(u)) return sum(u);
		while (1) {
			v=son(u, 0);
			if (x<=siz(v)) u=v;
			else if (x>siz(v)+1) u=son(u, 1), x-=siz(v)+1;
			else {splay(u, 0); return sum(son(u, 0));}
		}
	}
	void merge(int u, Splay& a) {
		//cout<<"merge "<<u<<' '<<tim(u)<<' '<<col(u)<<endl;
		if (son(u, 0)) merge(son(u, 0), a);
		if (son(u, 1)) merge(son(u, 1), a);
		if (col(u)!=-1) a.ins(tim(u), col(u), 1);
		rab[++rtop]=u;
	}
}rot[n];

void dfs(int u, int fa) {
	//cout<<"dfs "<<u<<' '<<fa<<endl;
	msiz[u]=siz2[u]=siz(rot[u].rot)-2; mson[u]=u;
	for (int i=head[u],v; ~i; i=e[i].next) {
		v = e[i].to;
		if (v==fa) conTinue;
		dfs(v, u);
		siz2[u]+=siz(rot[v].rot)-2;
		if (siz(rot[v].rot)-2>msiz[u])
			msiz[u]=siz(rot[v].rot)-2, mson[u]=v;
	}
	//cout<<"mson: "<<mson[u]<<endl;
	swap(rot[u], rot[mson[u]]);
	//cout<<"swap "<<u<<endl;
	for (int i=head[u],v; ~i; i=e[i].next) {
		v = e[i].to;
		if (v==fa) conTinue;
		//cout<<"goto merge "<<u<<' '<<v<<endl;
		rot[v].merge(rot[v].rot, rot[u]);
		//cout<<"return merge"<<endl;
	}
	ans[u]=rot[u].rk(k[u]+2);
	//cout<<"return "<<u<<endl;
}

signed main()
{
	memset(head, -1, sizeof(head));
	n=read();
	for (int i=1,u,v; i<n; ++i) {
		u=read(); v=read();
		add(u, v); add(v, u);
	}
	for (int i=1; i<=n; ++i) k[i]=read();
	m=read();
	for (int i=1; i<=m; ++i) qx[i]=read(), qc[i]=read(), unI[i]=qc[i];
	//cout<<"qc: "; for (int i=1; i<=m; ++i) cout<<qc[i]<<' '; cout<<endl;
	sort(uni+1, uni+m+1);
	usize=unique(uni+1, uni+m+1)-uni-1;
	for (int i=1; i<=m; ++i) qc[i]=lower_bound(uni+1, uni+usize+1, qc[i])-uni;
	//cout<<"qc: "; for (int i=1; i<=m; ++i) cout<<qc[i]<<' '; cout<<endl;
	for (int i=1; i<=m; ++i) rot[qx[i]].ins(i, qc[i], 1); //, cout<<"qins"<<endl;
	dfs(1, 0);
	q=read();
	for (int i=1; i<=q; ++i) printf("%dn", ans[read()]);
	
	return 0;
}