B. Alyona and a tree

#include "a.h"int n;
aLL a;
struct edge
{
int to, nx, w;
} e[N << ];
arr fi;
int ce = ;
aLL sum, ans;
aLL vec, up, down, res;
ll tot = ;
ll rs = ;inline void add(int u, int v, int w)
{
e[++ce] = edge{v, fi[u], w};
fi[u] = ce;
}void dfs(int x)
{
if (fi[x] == -)
{
rs = res[x];
rs += up[x], rs -= down[x];
ans[x] = rs;
return;
}
for (int i = fi[x]; i != -; i = e[i].nx)
{
int v = e[i].to, w = e[i].w;
sum[++tot] = sum[tot - ] + w;
int p = lower_bound(sum + , sum + + tot, sum[tot] - a[v]) - sum;
if (tot - >= p)
up[vec[tot - ]]++, down[vec[p - ]]++;
vec[tot] = v;
dfs(v);
tot--;
res[x] += rs;
rs = ;
}
rs = res[x];
rs += up[x], rs -= down[x];
ans[x] = rs;
}int main()
{
// file("test");
while (~scanf("%d", &n))
{
me(fi, -);
For(i, , n) sdf(a[i]);
For(i, , n)
{
int x, y;
sdf(x), sdf(y);
add(x, i, y);
}
vec[] = ;
sum[] = ;
dfs();
For(i, , n)
printf("%d ", ans[i]);
}
return ;
}