【CodeForces - 682C】Alyona and the Tree（dfs）

Alyona and the Tree

Descriptions

小灵决定节食，于是去森林里摘了些苹果。在那里，她意外地发现了一棵神奇的有根树，它的根在节点 1 上，每个节点和每条边上都有一个数字。

小灵注意到树上有一些节点不开心，所以她决定和它们一起玩。 如果节点 v 的子树中有一个节点 u 使得dist(v, u) > a _u ，那么节点 v 就会不开心。a _u 代表节点 u 上的数字，dist(v, u)代表连接节点 v 到节点 u 的所有边上的数字和，也就是两个节点的距离。

通过 1 条边连接到 1 个节点的那些节点被称为树的叶子，如果树只包含一个顶点，那么根也就是树的叶子。

因此小灵决定移除一些树叶，直到树上没有任何不开心的节点。请问小灵最少需要去除多少叶子呢?

Input

第 1 行输入一个整数 n (1 ≤ n ≤ 10 ⁵ )  —— 代表树上的节点数。

第 2 行输入 n 个整数 a ₁ , a ₂ , ..., a _n (1 ≤ a _i ≤ 10 ⁹ ) ， a _i 代表节点 i 上写着的数字。

接下来的 n - 1 行描述了树的边：第 i 行包含两个整数 p _i 和 c _i (1 ≤ p _i ≤ n ,  - 10 ⁹ ≤ c _i ≤ 10 ⁹ )，代表有一条边连接着节点 i + 1 和节点 p _i ， c _i 是写在边上的数字。

Output

输出 1 个整数 —— 代表为了使得树上完全没有不开心的节点，小灵最少需要去除的叶子数量。

Example

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#define IOS ios_base::sync_with_stdio(0); cin.tie(0);

#define Mod 1000000007

#define eps 1e-6

#define ll long long

#define INF 0x3f3f3f3f

#define MEM(x,y) memset(x,y,sizeof(x))

#define Maxn 100000+5

using namespace std;

int n;

//v[i].push_back(x,y)

//i点与x点的距离为y

//v[x].push_back(i,y)

//x点与i点的距离为y

vector<pair<int,ll> >v[Maxn];

int a[Maxn];//存点

int vis[Maxn];//标记这个点是否搜过

ll ans;

void dfs(int x,ll sum)//从根节点1到x的距离sum

{

    vis[x]=;//标记x搜过

    if(sum<=a[x])//距离小于x的值则+1

        ans++;

    else

        return;

    for(int i=;i<v[x].size();i++)

        if(!vis[v[x][i].first])

            dfs(v[x][i].first,max((ll),sum+v[x][i].second));

}

int main()

{

    MEM(vis,);

    cin>>n;

    for(int i=; i<=n; i++)

        cin>>a[i];

    for(int i=; i<=n; i++)

    {

        int p;

        ll c;

        cin>>p>>c;

        v[i].push_back(make_pair(p,c));

        v[p].push_back(make_pair(i,c));;

    }

    ans=;

    dfs(,);

    cout<<n-ans<<endl;

    return ;

}