线段树求调!!!
  • 板块学术版
  • 楼主封禁用户
  • 当前回复9
  • 已保存回复9
  • 发布时间2024/1/23 17:07
  • 上次更新2024/1/23 19:49:17
查看原帖
线段树求调!!!
471571
封禁用户楼主2024/1/23 17:07

link

#include<bits/stdc++.h>
#define M 200001
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
inline ll read()
{
	ll k=0,f=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) f|=c=='-';
	for(;isdigit(c);c=getchar()) k=(k<<1)+(k<<3)+(c^48);
	return f?-k:k;
}
ll n,m,cnt,h[M],ans[M];
ll root[M],node;
struct edge
{
	ll to,ne;
}e[M<<1];
struct tree
{
	ll lson,rson,val;
}t[M<<5];
void add(ll u,ll v)
{
	cnt++;
	e[cnt].to=v,e[cnt].ne=h[u],h[u]=cnt;
}
void push_up(ll p)
{
	t[p].val=t[t[p].lson].val+t[t[p].rson].val;
}
ll modify(ll p,ll l,ll r,ll x)
{
	if(!p) p=++node;
	if(l==r)
	{
		t[p].val=1;
		return p;
	}
	ll mid=(l+r)>>1;
	if(x<=mid) t[p].lson=modify(t[p].lson,l,mid,x);
	else t[p].rson=modify(t[p].rson,mid+1,r,x);
	push_up(p);
	return p;
}
ll merge(ll x,ll y,ll l,ll r)
{
	if(!x) return y;
	if(!y) return x;
	if(l==r)
	{
		t[x].val=1,t[y].val=0;
		return x;
	}
	ll mid=(l+r)>>1;
	t[x].lson=merge(t[x].lson,t[y].lson,l,mid),t[x].rson=merge(t[x].rson,t[y].rson,mid+1,r);
	push_up(x);
	return x;
}
void dfs(ll x,ll father)
{
	for(ll i=h[x];i;i=e[i].ne)
	{
		ll y=e[i].to;
		if(y!=father)
		{
			dfs(y,x);
			root[x]=merge(root[x],root[y],1,1e6);
		}
	}
	ans[x]=t[root[x]].val;
}
int main()
{ 
	n=read();
	for(ll i=1;i<n;i++)
	{
		ll u=read(),v=read();
		add(u,v),add(v,u);
	}
	for(ll i=1;i<=n;i++)
	{
		ll col=read();
		root[i]=modify(root[i],1,1e6,col);
	}
	dfs(1,0);
	m=read();
	while(m--)
	{
		ll x=read();
		printf("%lld\n",ans[x]);
	}
	return 0;
}

2024/1/23 17:07
加载中...