# CodeForces 740D Alyona and a tree 题解：DFS + 二分

vector 真的好用～

## Problem

Alyona has a tree with $n$ vertices. The root of the tree is the vertex 1. In each vertex Alyona wrote an positive integer, in the vertex $i$ she wrote $a_i$. Moreover, the girl wrote a positive integer to every edge of the tree (possibly, different integers on different edges).

Let's define $dist(v, u)$ as the sum of the integers written on the edges of the simple path from $v$ to $u$.

The vertex $v$ controls the vertex $u$ $(v ≠ u)$ if and only if $u$ is in the subtree of $v$ and $dist(v, u) ≤ a_u$.

Alyona wants to settle in some vertex. In order to do this, she wants to know for each vertex $v$ what is the number of vertices $u$ such that $v$ controls $u$.

## Input

The first line contains single integer $n$ $(1 ≤ n ≤ 2·105)$.

The second line contains $n$ integers $a_1, a_2, ..., a_n$ $(1 ≤ a_i ≤ 10^9)$ — the integers written in the vertices.

The next $(n - 1)$ lines contain two integers each. The $i$-th of these lines contains integers $p_i$ and $w_i$ $(1 ≤ p_i ≤ n, 1 ≤ w_i ≤ 10^9)$ — the parent of the $(i + 1)$-th vertex in the tree and the number written on the edge between $p_i$ and $(i + 1)$.

It is guaranteed that the given graph is a tree.

## Output

Print $n$ integers — the $i$-th of these numbers should be equal to the number of vertices that the $i$-th vertex controls.

## Examples

### Input #1

5
2 5 1 4 6
1 7
1 1
3 5
3 6

### Output #1

1 0 1 0 0

### Input #2

5
9 7 8 6 5
1 1
2 1
3 1
4 1

### Output #2

4 3 2 1 0

## Notes

In the example test case the vertex 1 controls the vertex 3, the vertex 3 controls the vertex 5 (note that is doesn't mean the vertex 1 controls the vertex 5).

## Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
const int maxn=200005,maxe=400005;
int n,tot=0,a[maxn],fa[maxn],sum[maxn],lnk[maxn],son[maxe],nxt[maxe],w[maxe];
long long dst[maxn];
bool vis[maxn];
vector <int> vec;
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
inline void add(int x,int y,int z){
tot++;son[tot]=y;w[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;
}
inline long long myabs(long long x){
return x>0?x:-x;
}
inline void BuildDistance(int x){
vis[x]=1;
for (int i=lnk[x];i;i=nxt[i]) if (!vis[son[i]]){
fa[son[i]]=x;
dst[son[i]]=(long long)dst[x]+w[i];
BuildDistance(son[i]);
}
}
inline long long GetDistance(int x,int y){
return myabs((long long)dst[x]-dst[y]);
}
inline void BuildSum(int x){
vis[x]=1;
int L=0,R=vec.size()-1,mid,now=-1;
while (L<=R){
mid=((R-L)>>1)+L;
if ((long long)GetDistance(x,vec[mid])<=(long long)a[x]){
now=mid;
R=mid-1;
} else L=mid+1;
}
if (now!=-1){
now=vec[now];
if (now!=x||GetDistance(x,now)<=a[x]) sum[fa[x]]++,sum[fa[now]]--;
}
vec.push_back(x);
for (int i=lnk[x];i;i=nxt[i]) if (!vis[son[i]]){
BuildSum(son[i]);
}
vec.erase(vec.end()-1);
}
vis[x]=1;
for (int i=lnk[x];i;i=nxt[i]) if (!vis[son[i]]){
sum[x]+=sum[son[i]];
}
}
int main(){
for (int i=2;i<=n;i++){
}
BuildDistance(1);
memset(vis,0,sizeof(vis));
vec.clear();
vec.push_back(1);
BuildSum(1);
memset(vis,0,sizeof(vis));