正经人谁吃泡菜肥牛啊？

第一行输入节点数 $n (1\le n\le 10^6)$

第二行是输入 ${n}$ 个整数泡菜肥牛值 $a_i (1\le a_i \le 10^6)$

接下来 ${n-1}$ 行，每行包括两个数 ${u,v(1\le u,v \le n) }$ 表示 ${u}$ 与 ${v}$ 相连

接下来一行输入一个整数 $q (1\le q \le 10^6)$ ，表示Azir的询问数

之后的 $q$ 行每行输入两个整数 ${x,k(1\le x \le n,1\le k\le10^6)}$ ，表示 $Azir$ 询问的是以x为根结点的子树中有多少结点的泡菜肥牛值不大于 $k$ （包括 $x$ 这个结点）

C++ 解法, 执行用时: 1705ms, 内存消耗: 151056K, 提交时间: 2022-07-04 22:15:08

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
vector<int>g[N];
int n,a[N],tr[N],son[N],sz[N],idx,hd[N],ret,u,v,q;
struct edge{
	int v,nxt;
}e[N<<1];
struct ans{
	int x,y,ans;
}ans[N];
void add_edge(int u,int v)
{
	e[++idx]=(edge){v,hd[u]};
	hd[u]=idx;
}
void update(int x,int y)
{
	for(int i=x;i<N;i+=i&-i)
		tr[i]+=y;
}
int ask(int x)
{
	for(ret=0;x;x-=x&-x)
		ret+=tr[x];
	return ret;
}
void dfs1(int x,int y)
{
	sz[x]=1;
	for(int i=hd[x];i;i=e[i].nxt)
	{
		if(e[i].v==y)
			continue;
		dfs1(e[i].v,x);
		sz[x]+=sz[e[i].v];
		if(sz[e[i].v]>sz[son[x]])
			son[x]=e[i].v;
	}
}
void calc(int x,int y,int z)
{
	update(a[x],z);
	for(int i=hd[x];i;i=e[i].nxt)
		if(e[i].v!=y)
			calc(e[i].v,x,z);
}
void dsu(int x,int y,int z)
{
	for(int i=hd[x];i;i=e[i].nxt)
		if(e[i].v!=y&&e[i].v!=son[x])
			dsu(e[i].v,x,1);
	if(son[x])
		dsu(son[x],x,0);
	update(a[x],1);
	for(int i=hd[x];i;i=e[i].nxt)
		if(e[i].v!=son[x]&&e[i].v!=y)
			calc(e[i].v,x,1);
	for(int i=0;i<(int)g[x].size();i++)
		ans[g[x][i]].ans=ask(ans[g[x][i]].y);
	if(z)
		calc(x,y,-1);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		add_edge(u,v);
		add_edge(v,u);
	}
	dfs1(1,0);
	scanf("%d",&q);
	for(int i=1;i<=q;i++)	
	{
		scanf("%d%d",&ans[i].x,&ans[i].y);
		g[ans[i].x].push_back(i);
	} 
	dsu(1,0,0);
	for(int i=1;i<=q;i++)
		printf("%d\n",ans[i].ans);
}

详情