题目大意：太长不想说，自己看吧。
发现留守和死亡是没有区别的，那么把它们一起考虑。
考虑只有一个点的情况，那么这个点需要的人数就是max(a,b+c)，但是死亡的人数是b+c
那么我们先把需要的人数和死亡的人数做一个pair。
然后考虑枚举起点，算总的需要人数。
每个点的死亡人数就是它的死亡人数加上所有子树的死亡人数。
但是这个点的需要人数并不是这个。不难发现，当完成一个子树后，多余的人可以接着到别的地方继续战斗，而不多余的话就不需要。那么我们优先考虑需要人多的地方，并进行贪心，那么这个点的需要人数就是max(b+need[i])。b=已经死亡的人数。因为排序时我们要让need[i]从大到小，死亡人数从小到大，所以我把need[i]当做负值来存，就不用写cmp啦。
附代码：
#include<bits/stdc++.h> #define N 110 using namespace std; typedef pair<int,int> pii; int n,len; int nex[N<<1],to[N<<1],beg[N]; pii va[N]; inline void Add(int a,int b){ nex[++len]=beg[a],beg[a]=len,to[len]=b; nex[++len]=beg[b],beg[b]=len,to[len]=a; } pii dfs(int p,int fa){ vector<pii> tmp; for(int i=beg[p];i;i=nex[i]) if(to[i]!=fa) tmp.push_back(dfs(to[i],p)); int a=-va[p].first,b=va[p].second; sort(tmp.begin(),tmp.end()); for(int i=0;i<tmp.size();i++){ a=max(a,b-tmp[i].first); b+=tmp[i].second; } a=max(a,b); return pii(-a,b); } int main(){ int T=0; while(scanf("%d",&n),n){ len=0;memset(beg,0,sizeof(beg)); for(int i=1,a,b,c;i<=n;i++){ scanf("%d%d%d",&a,&b,&c); va[i]=pii(-max(a,b+c),b+c); } for(int i=1,a,b;i<n;i++){ scanf("%d%d",&a,&b); Add(a,b); } pii ans=dfs(1,-1); for(int i=2;i<=n;i++) ans=max(ans,dfs(i,-1)); printf("Case %d: %d\n",++T,-ans.first); } return 0; }
