【悬关】关于Oi-wiki上U41492 树上数颜色 其他做法的疑问

#include<bits/stdc++.h>
#define endl '\n'
#define MIN(a,b,c) min(min(a,b),c)
#define MAX(a,b,c) max(max(a,b),c)
#define ri register int
#define int long long
#define fixedset(a) fixed << setprecision(a)
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
#define ls(x) x<<1
#define rs(x) x<<1|1
#define MAXN 9.2211e18
#define inf 114514
#define mf 5011
#define sf 1011
#define eps 1e-7
#define MOD 114514
#define mod(x) (x+MOD)%MOD
using namespace std;
mt19937_64 randint{std::chrono::steady_clock::now().time_since_epoch().count()};
struct Msg{
	int val,l,r;
	Msg():val(0),l(0),r(0){}
	Msg(int VAL,int L,int R):val(VAL),l(L),r(R){}
	Msg operator +(const Msg &p) const{
		return {val+p.val,l,p.r};
	}
}msg[(inf+sf)*4];
struct Tag{
	int add;
	Tag():add(0){}
	Tag(int ADD):add(ADD){}
	Tag operator <(const Tag &p) const{
		return {add+p.add};
	}
	Msg apply(const Msg &p) const{
		return {p.val+add*(p.r-p.l+1),p.l,p.r};
	}
}tag[(inf+sf)*4];
int n,m,tmp[inf],num[inf],lst[inf],suf[inf],ans[inf];
vector<tuple<int,int,int> > modify[inf];
vector<tuple<int,int> > query[inf];
vector<int> edge[inf];
int cnt,siz[inf],dfn[inf],rnk[inf];
void pushup(int p){
	msg[p]=msg[ls(p)]+msg[rs(p)];
	return ;
}
void pushdown(int p){
	msg[ls(p)]=tag[p].apply(msg[ls(p)]); msg[rs(p)]=tag[p].apply(msg[rs(p)]);
	tag[ls(p)]=tag[ls(p)]<tag[p]; tag[rs(p)]=tag[rs(p)]<tag[p];
	tag[p]=Tag();
	return ;
}
void build(int p,int s,int t){
	if(s==t){
		msg[p]=Msg(0,s,t);
		return ;
	}
	int mid=s+((t-s)>>1);
	build(ls(p),s,mid);
	build(rs(p),mid+1,t);
	pushup(p);
	return ;
}
void modifyadd(int p,int s,int t,int l,int r,Tag c){
	if(l<=s && t<=r){
		msg[p]=c.apply(msg[p]);
		tag[p]=tag[p]<c;
		return ;
	}
	int mid=s+((t-s)>>1);
	pushdown(p);
	if(l<=mid) modifyadd(ls(p),s,mid,l,r,c);
	if(r >mid) modifyadd(rs(p),mid+1,t,l,r,c);
	pushup(p);
	return ;
}
Msg nodesum(int p,int s,int t,int g){
	if(s==t) return msg[p];
	int mid=s+((t-s)>>1);
	pushdown(p); Msg res;
	if(g<=mid) res=res+nodesum(ls(p),s,mid,g);
	if(g >mid) res=res+nodesum(rs(p),mid+1,t,g);
	pushup(p);
	return res;
}
int dfs(int u,int fa){
	cnt++; siz[u]++;
	dfn[u]=cnt,rnk[cnt]=u;
	for(auto v:edge[u]){
		if(v==fa) continue;
		siz[u]+=dfs(v,u);
	}
	return siz[u];
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin >> n;
    for(ri i=2;i<=n;i++){
    	int x,y; cin >> x >> y;
    	edge[x].push_back(y); edge[y].push_back(x);
	}
	for(ri i=1;i<=n;i++) cin >> tmp[i];
	dfs(1,0); build(1,1,n); cin >> m;
	for(ri i=1;i<=n;i++) num[dfn[i]]=tmp[i];
	for(ri i=1;i<=n;i++) lst[i]=n+1;
	for(ri i=n;i>=1;i--){
		suf[i]=lst[num[i]];
		lst[num[i]]=i;
		modify[1].push_back({i,suf[i]-1,1});
		modify[i+1].push_back({i,suf[i]-1,-1});
	}
	for(ri i=1;i<=m;i++){
		int x; cin >> x;
		query[dfn[x]].push_back({dfn[x]+siz[x]-1,i});
	}
	
	for(ri i=1;i<=n;i++){
		for(auto [l,r,c]:modify[i]) modifyadd(1,1,n,l,r,Tag(c));
		for(auto [g,id]:query[i]) ans[id]=nodesum(1,1,n,g).val;
	}
	
	for(ri i=1;i<=m;i++) cout << ans[i] << endl;
	return 0;
}