对于100%的数据，n<=200000，1<=场景价值<=2^31-1
【题解】：//主要是为了练pb_ds
每次一定是选取一个点，将它子树内权值和最大的链取走，以后就不会再选取链上的点
那么用堆维护这一过程，取最大值，删去链的所有点
复杂度都为nlogn
#include<cstdio> #include<iostream> #include<ext/pb_ds/priority_queue.hpp> using namespace std; 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*10+ch-‘0‘;ch=getchar();} return x*f; } typedef long long ll; typedef pair<ll,int> pa; typedef __gnu_pbds::priority_queue<pa > heap; const int N=2e5+7; struct node{ int to,next; }e[N];int cnt,head[N]; heap q; heap::point_iterator id[N]; int n,K,v[N]; ll ans,mx[N]; void add(int x,int y){ e[++cnt].to=y;e[cnt].next=head[x];head[x]=cnt; } void dp(int x){ for(int i=head[x];i;i=e[i].next){ dp(e[i].to); mx[x]=max(mx[x],mx[e[i].to]); } mx[x]+=v[x]; id[x]=q.push(make_pair(mx[x],x)); } void del(int x){ q.erase(id[x]); for(int i=head[x];i;i=e[i].next){ if(mx[e[i].to]==mx[x]-v[x]){ del(e[i].to); break; } } } int main(){ n=read();K=read(); for(int i=1;i<=n;i++) v[i]=read(); for(int i=1,x,y;i<n;i++) x=read(),y=read(),add(x,y); dp(1); for(int i=1;i<=K&&!q.empty();i++){ pa t=q.top(); ans+=t.first; del(t.second); } printf("%lld",ans); return 0; }
原文：http://www.cnblogs.com/shenben/p/6291206.html