1633: 能量获取(energy)

$1633$1633: 能量获取(energy)
时间限制: $1 Sec$1Sec 内存限制: $128 MB$128MB
题目描述
“封印大典启动，请出$Nescafe$Nescafe魂珠！”随着圣主$applepi$applepi一声令下，圣剑护法$rainbow$rainbow和魔杖护法$freda$freda将$Nescafe$Nescafe魂珠放置于封印台上。封印台是一个树形的结构，魂珠放置的位置就是根节点（编号为$0$0）。还有n个其它节点（编号$1$1~$n$n）上放置着封印石，编号为i的封印石需要从魂珠上获取Ei的能量。能量只能沿着树边从魂珠传向封印石，每条边有一个能够传递的能量上限$W_{i}$Wi​，魂珠的能量是无穷大的。作为封印开始前的准备工作，请你求出最多能满足多少颗封印石的能量需求？

注意：能量可以经过一个节点，不满足它的需求而传向下一个节点。每条边仅能传递一次能量。

输入
第一行一个整数$n$n，表示除根节点之外其它节点的数量。

接下来$n$n行，第$i+1$i+1行有三个整数$F_{i}、E_{i}、W_{i}$Fi​、Ei​、Wi​，分别表示i号节点的父节点、i号节点上封印石的能量需求、连接节点i与Fi的边最多能传递多少能量。

输出
最多能满足多少颗封印石的能量需求。

样例输入
4
0 3 2
0 100 100
1 1 1
2 75 80
样例输出
2
提示
对于 $100\%$100% 的数据，满足$1 \leq n \leq 1000，0 \leq Fi \leq n，0 \leq Ei,Wi \leq 100$1≤n≤1000，0≤Fi≤n，0≤Ei,Wi≤100。

题解：

考虑贪心，每次取最小值，然后往上更新即可。

#include<bits/stdc++.h>
using namespace std;
#define in inline
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repd(i,a,b) for(int i=a;i>=b;i--)
#define For(i,a,b) for(int i=a;i<b;i++)
#define _(d) while(d(isdigit(ch=getchar())))
template<class T>in void g(T&t){T x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch-48;_()x=x*10+ch-48;t=f*x;}
const int N=5e4+3,M=200004;
int n,ans,id[N];
struct Nod{int fa,v,w,x;}p[N];
in bool cmp(Nod A,Nod B){return A.v<B.v;}
int main(){ 
	g(n);
	rep(i,1,n) g(p[i].fa),g(p[i].v),g(p[i].w),p[i].x=i;
	sort(p+1,p+1+n,cmp);
	rep(i,1,n) id[p[i].x]=i;
	rep(i,1,n){
		int x=p[i].x,ee=p[i].v;bool flag=0;
		while(x){
			if(p[id[x]].w<ee){flag=1;break;}
			p[id[x]].w-=ee; x=p[id[x]].fa;
		}
		if(!flag) ans++; 
	}
	return !printf("%d\n",ans);
}