比较容易想到的是建图之后，然后二分，nlogn的复杂度，可以通过此题
然后，还有一种做法，需要并查集维护已经dfs过的点的祖先，大概复杂度是alpha（n）（并查集的复杂度），，比On高一点点，
看了前几名的做法，，貌似是每次输入之后都往上爬。暴力判断。，，但奇怪的是会用时这么少。。应该是数据水吧，，毕竟很容易就可以构造出使它复杂度为n*n的例子（一条链，且一直不会断）。。。
#include<cstdio> #include<cstring> #include<iostream> #include<math.h> #include<algorithm> #include<queue> using namespace std; #define MX 55555 #define INF 0x3f3f3f3f3f3f3f3f #define mem(x,y) memset(x,y,sizeof(x)) typedef long long LL; int n; int head[MX],cnt; struct Nod { int nxt,to; } E[2*MX]; void edge_init() { mem(head,-1); cnt=0; } void edge_add(int u,int v) { // cout<<u<<" "<<v<<endl; E[cnt].nxt=head[u]; E[cnt].to=v; head[u]=cnt++; } int bin[MX]; int _find(int x) { return x==bin[x]?x:bin[x]=_find(bin[x]); } LL dp[MX]; LL val[MX],mx[MX]; int tot; int dfs(int u) { dp[u]+=val[u]; for(int i=head[u]; ~i; i=E[i].nxt) { int v=E[i].to; if(v>tot) continue; dfs(v); bin[v]=u; dp[u]+=dp[v]; } while(dp[u]>mx[u]) { int fa=_find(tot); dp[fa]-=val[tot]; tot--; } } int main() { //freopen("input.txt","r",stdin); edge_init(); cin>>n; mx[0]=INF; val[0]=0; for(int i=1; i<=n; i++) { int p; scanf("%I64d%I64d%d",&mx[i],&val[i],&p); edge_add(p+1,i); } mem(dp,0); for(int i=0; i<=n; i++) bin[i]=i; tot=n; dfs(0); printf("%d\n",tot); return 0; }
