CodeForces 682C Alyona and the Tree 搜索

78 阅读 0 评论 52 点赞

我是靠谱客的博主壮观吐司，最近开发中收集的这篇文章主要介绍CodeForces 682C Alyona and the Tree 搜索，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述：

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) > au, where au 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 ≤ 105) is given — the number of vertices in the tree.

In the second line the sequence of n integers a1, a2, …, an (1 ≤ ai ≤ 109) is given, where ai is the number written on vertex i.

The next n - 1 lines describe tree edges: ith of them consists of two integers pi and ci (1 ≤ pi ≤ n, - 109 ≤ ci ≤ 109), meaning that there is an edge connecting vertices i + 1 and pi with number ci 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:

这里写图片描述

题目分析：

有一棵树，节点有权值，边也有权值，若要使每个子节点到其祖宗节点的路径权之和小于或者等于子节点的权，需要从原图中删除多少个节点？

这里的难点是在构图之前你不知道谁是父节点，谁是子节点，事实上，不需要判断谁是父节点，谁是子节点，只需要按无向图的建法，对每个节点都进行搜索，记录节点权值大于等于其路径权值的点，（不需要删除）。
答案就是原图节点数-留下的节点数。

代码如下：

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const double eps = 1e-4;
const int MAXN=100010;

struct Edge
{
    int to,next;
    ll w;
}edge[MAXN*2];

int a[MAXN];
int n;
int id;
int head[MAXN];
int remain;

void init()
{
    id=0;
    memset(head,-1,sizeof(head));
}

void addedge(int u,int v, ll w)
{
    edge[id].to=v;
    edge[id].next=head[u];
    edge[id].w=w;
    head[u]=id++;
}

void dfs(int u,int pre, ll w)
{
    if (a[u]<w) return;
    remain++;
    for(int i=head[u]; i!=-1; i=edge[i].next)
    {
        int v=edge[i].to;
        if (v==pre) continue;
        dfs(v,u,max(0LL,w+edge[i].w));
    }
}


int main()
{
    init();
    remain=0;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
       scanf("%d",&a[i]);
    for(int i=2; i<=n; i++)
    {
        int v,w;
        scanf("%d%lld",&v,&w);
        addedge(i,v,w);
        addedge(v,i,w);
    }
    dfs(1,1,0);
    printf("%dn",n-remain);
    return 0;
}