題意翻譯

題目描述

給你一棵樹，邊與節點都有權值，根節點為1，現不停刪除葉子節點形成新樹，問最少刪掉幾個點，能使得最后剩下的樹內，?v與其子樹內?u間邊權的和小于點u權值

輸入輸出格式

輸入格式：

第一行，節點個數n(1≤n≤1e5)

第二行，n個整數——各節點的權值a_i?(1≤a_i?≤1e9)

接下來的n-1行，每行兩個整數p_i與c_i?(1≤p_i?≤n,?1e9≤c_i?≤1e9)，分別表示編號為i+1的節點的父節點以及該邊的邊權

輸出格式：

一個整數，最少需要刪除的點的個數

輸入輸出樣例

輸入樣例#1：?
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 輸出樣例#1：? 5

代碼

思維題。

首先可以轉化成保留多少個節點。

然后每次累加取max(0,sum+e[i].val)

比如說我們v[u]=10,而此時sum=-1000，而∑e[i].val=20，顯然這種情況是不可法的

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+100; int v[maxn],head[maxn]; struct edge {int to,next,val; }e[maxn]; int cnt=0; int size=0; inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*f; } void addedge(int u,int v,int w) {e[++size].to=v;e[size].val=w;e[size].next=head[u];head[u]=size; } void dfs(int u,int sum) {if(sum>v[u])return;cnt++;for(int i=head[u];i;i=e[i].next){int to=e[i].to;dfs(to,max(0,sum+e[i].val));} } int main() {int n=read();for(int i=1;i<=n;i++)v[i]=read();for(int i=2;i<=n;i++){int v=read(),w=read();addedge(v,i,w);}dfs(1,0);printf("%d",n-cnt);return 0; } View Code

?

轉載于:https://www.cnblogs.com/DriverBen/p/11001768.html

總結

以上是生活随笔為你收集整理的CF682C Alyona and the Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。