Codeforces Round #358 (Div. 2) C. Alyona and the Tree （DFS）

100 阅读 0 评论 66 点赞

我是靠谱客的博主淡定白羊，最近开发中收集的这篇文章主要介绍Codeforces Round #358 (Div. 2) C. Alyona and the Tree （DFS），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Alyona decided to go on a diet and went to the forest to get some apples. There she unexpectedly found a magic rooted tree with root in the vertex 1, every vertex and every edge of which has a number written on.

The girl noticed that some of the tree's vertices are sad, so she decided to play with them. Let's call vertex v sad if there is a vertex u in subtree of vertex v such that dist(v, u) > a_u, where a_u is the number written on vertex u, dist(v, u) is the sum of the numbers written on the edges on the path from v to u.

Leaves of a tree are vertices connected to a single vertex by a single edge, but the root of a tree is a leaf if and only if the tree consists of a single vertex — root.

Thus Alyona decided to remove some of tree leaves until there will be no any sad vertex left in the tree. What is the minimum number of leaves Alyona needs to remove?

Input

In the first line of the input integer n (1 ≤ n ≤ 10⁵) is given — the number of vertices in the tree.

In the second line the sequence of n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹) is given, where a_i is the number written on vertex i.

The next n - 1 lines describe tree edges: i^th of them consists of two integers p_i and c_i (1 ≤ p_i ≤ n, - 10⁹ ≤ c_i ≤ 10⁹), meaning that there is an edge connecting vertices i + 1 and p_i with number c_i written on it.

Output

Print the only integer — the minimum number of leaves Alyona needs to remove such that there will be no any sad vertex left in the tree.

Example

Input

9
88 22 83 14 95 91 98 53 11
3 24
7 -8
1 67
1 64
9 65
5 12
6 -80
3 8

Output

Note

The following image represents possible process of removing leaves from the tree:

题意：给你一棵树，有节点值和边权值，如果一个结点的子节点到这个结点的距离>子节点的权值，那么这个子节点将会被删除，相应的，该子节点的所有子节点也会被一起删除，问删除多少个点

思路：刚开始每太读懂题目，以为这棵树不固定，但是这棵树是固定的，永远都是以结点1为根节点，所以说，我们从结点1开始向下搜，过程中用权值和与其父节点权值作比较取最大值，符合要求的点做标记

ac代码：

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stack>
#include<set>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#define MAXN 1010000
#define LL long long
#define ll __int64
#define INF 0xfffffff
#define mem(x) memset(x,0,sizeof(x))
#define PI acos(-1)
#define eps 1e-8
using namespace std;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
double dpow(double a,ll b){double ans=1.0;while(b){if(b%2)ans=ans*a;a=a*a;b/=2;}return ans;}
//head
struct Edge
{
    int frome,to,val,next;
}edge[MAXN];
int head[MAXN],edgenum;
int v[MAXN],a[MAXN];
void Add(int u,int v,int w)
{
    Edge E={u,v,w,head[u]};
    edge[edgenum]=E;
    head[u]=edgenum++;
}
void DFS(int now,ll sum)
{
    if(sum>a[now])
    {
        return;
    }
    v[now]=1;
    for(int i=head[now];i!=-1;i=edge[i].next)
    {
        if(!v[edge[i].to])
        DFS(edge[i].to,max(sum+edge[i].val,(ll)edge[i].val));
    }
}
int main()
{
    int n;scanf("%d",&n);
    memset(head,-1,sizeof(head));edgenum=0;mem(v);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<n;i++)
    {
        int b,c;scanf("%d%d",&b,&c);
        Add(i+1,b,c);Add(b,i+1,c);
    }
    DFS(1,0);int cnt=0;
    for(int i=1;i<=n;i++)
        if(v[i]) cnt++;
    printf("%dn",n-cnt);
    return 0;
}