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

发布时间：2020-12-16 10:49:25 所属栏目：百科来源：网络整理

导读：Alyona and the Tree Descriptions 小灵决定节食，于是去森林里摘了些苹果。在那里，她意外地发现了一棵神奇的有根树，它的根在节点 1 上，每个节点和每条边上都有一个数字。小灵注意到树上有一些节点不开心，所以她决定和它们一起玩。如果节点 v 的子树中

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

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
5

提示

下面的图片代表了从树上去除叶子的过程 :

题目链接

https://vjudge.net/problem/CodeForces-682C

对这个问题进行简单的转变，将原来问题求去掉几个转变成满足几个，这道题目就会简单很多。

从祖先到当前的叶子节点，问你有几个满足是其祖先到叶子的权值的和小于等于当前的节点值的。

dfs搜一下即可

如果最大值为负了我们要赋值为0，因为我们在下面可能还会碰到权值为正的边，此时的最大值肯定是这条权值为正的边，所有要把最大值赋值为0

AC代码

#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]=1;//标记x搜过
    if(sum<=a[x])//距离小于x的值则+1
        ans++;
    else
        return;
    for(int i=0;i<v[x].size();i++)
        if(!vis[v[x][i].first])
            dfs(v[x][i].first,max((ll)0,sum+v[x][i].second));
}
int main()
{
    MEM(vis,0);
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    for(int i=2; 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=0;
    dfs(1,0);
    cout<<n-ans<<endl;
    return 0;

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!