题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2197
写完替罪羊树、splay这种东西之后再回来水usaco真【】爽
首先一定要满足子树中的节点，然后如果不够，就取子树中时间最短的挂到够
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<bits/stdc++.h> #define MAXN 100010 typedef long long ll; using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*y; } vector<int>v[MAXN]; ll ans,sz[MAXN]; int n,c[MAXN],t[MAXN]; int dfs(int x){ sz[x]=0; int Min=t[x]; for(int i=0; i<v[x].size(); i++){ int to=v[x][i]; Min=min(Min,dfs(to)); sz[x]+=sz[to]; } if(sz[x]<c[x])ans+=Min*(c[x]-sz[x]),sz[x]=c[x]; return Min; } int main(){ n=rd(); for(int i=1; i<=n; i++){ int x=rd(); c[i]=rd(),t[i]=rd(); if(x!=-1)v[x].push_back(i); } dfs(1); printf("%lld\n",ans); return 0; } |
