萌新求助

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define clr(f, n) memset(f, 0, sizeof(int) * (n))
#define cpy(f, g, n) memcpy(f, g, sizeof(int) * (n))
#define rev(f, n) reverse(f, f + n)
#define pir pair<int, int>
#define mkp make_pair
#define fst it->first
#define sec it->second
#define int long long
#define up(i,x,y) for(int i=x,i##end=y;i<=i##end;++i)
#define down(i,x,y) for(int i=x,i##end=y;i>=i##end;--i)
#define graph(i,x) for(int i=head[x];i;i=nxt[i])
using namespace std;
int n, m, k;
int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}
inline void print(int *f, int len)
{
    for (int i = 0; i < len; i++)
        printf("%lld ", f[i]);
    puts("");
}
const int maxn=4e5+10;
int head[maxn],to[maxn],nxt[maxn],tot,w[maxn];
void add(int a,int b,int c)
{
	to[++tot]=b;
	nxt[tot]=head[a];
	head[a]=tot;
	w[tot]=c;
}
int dis[maxn],p[maxn],bit[maxn];
int dfn[maxn],out[maxn],tim,a[maxn];
int lowbit(int x)
{
	return x&(-x);
}
void upt(int x,int y)
{
	for(;x<=n;x+=lowbit(x))bit[x]+=y;
}
int qry(int x)
{
	int anss=0;
	for(;x>0;x-=lowbit(x))anss+=bit[x];
	return anss;
}
struct node
{
	int l,r,id,x,ans;
}q[maxn];
void dfs(int x,int fa,int dist)
{
	dis[x]=dist;
	dfn[x]=++tim;
	graph(i,x)
	{
		int v=to[i];
		if(v==fa)continue;
		dfs(v,x,dist+w[i]);
	}
	out[x]=tim;
	q[x]=(node){dfn[x]+1,out[x],x,dis[x],0};
}
bool cmp(node a,node b)
{
	return a.x<b.x;
}
int qaq[maxn];
struct qwq
{
	int v,id;
}s[maxn];
/*
dis[i]表示1->i的距离
dist(u,v)<=av
dis[v]-dis[u]<=av 
dis[v]-av<=dis[u] 
*/
bool cmp2(qwq a,qwq b)
{
	return a.v<b.v;
}
signed main()
{
	n=read();
	up(i,1,n)a[i]=read();
	up(i,2,n)
	{
		int x=read(),y=read();
		add(i,x,y),add(x,i,y);
	}
	dfs(1,0,0);
	up(i,1,n)p[i]=dis[i]-a[i];
	up(i,1,n)s[i]=(qwq){p[i],i};
	sort(s+1,s+n+1,cmp2);
	sort(q+1,q+n+1,cmp);
	int nw=1;
	up(i,1,n)
	{
		while(s[i].v>q[nw].x)
		{
			qaq[q[nw].id]=qry(q[nw].r)-qry(q[nw].l-1);
			++nw;
		}
		upt(s[i].id,1);
	} 
	while(nw<=n)
	{
		qaq[q[nw].id]=qry(q[nw].r)-qry(q[nw].l-1);
		++nw;
	}
	up(i,1,n)printf("%lld ",qaq[i]);
}