题意是给你一棵树 n个点 n-1条边 起点是1 每一个点都有权值 每次能从根节点走到叶子节点 经行k次游戏 每次都是从1開始 拿过的点的权值不能拿第二次 问最大权值和。
開始看到题时也没想到什么方法 就依照常规的来 结果超时了 试着优化了好多次 最后过了 百度题讲解是树链剖分 醉了 还没学！
。。
说说我的做法吧 map【i】=a表示i节点的跟节点为a节点 从全部叶子节点開始入队（有点队列里有三个变量 各自是节点编号 权值 深度 优先级看代码 里面有点贪心的意思） 每次走根节点 假设根节点没走过 则走它 并把该店权值变为0 否则直接跳到1这个节点（假设一个个跳可能会超时）再入队 当出队的编号为1时而且拿的个数小于游戏次数 则拿 否则结束 在跑深度的时候有个优化 開始没有超时了 假设该节点深度已知了 则以后的根节点就不用跑了。！
！
详细看代码吧
#include<stdio.h> #include<string.h> #include<queue> #include<iostream> using namespace std; int map[100010],mark[100010]; int Deep[100010]; __int64 num[100010]; struct node { __int64 value; int ii; int deep; bool operator < (const node& x) const { return deep<x.deep||(deep==x.deep&&value<x.value); } }a; int main() { int T,i,j,n,k,r=1; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&k); for(i=1;i<=n;i++) { scanf("%I64d",&num[i]); } memset(mark,0,sizeof(mark)); for(i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); mark[x]=1; map[y]=x; } priority_queue<node>Q; memset(Deep,0,sizeof(Deep)); for(i=1;i<=n;i++) { if(mark[i]==0) { int x=map[i]; int d=1; while(x!=1) { if(Deep[x]>0) {d+=Deep[x];break;} x=map[x]; d++; } x=i; while(x!=1) { if(Deep[x]>0) break; Deep[x]=d; x=map[x]; d--; } a.deep=Deep[i]; a.value=num[i]; a.ii=i; Q.push(a); } } //for(i=1;i<=n;i++) //printf("%d ^^^ %d ",i,Deep[i]); __int64 sum=0; int cont=0; while(!Q.empty()) { a=Q.top(); Q.pop(); int x=map[a.ii]; /*while(num[x]==0&&x!=1) { x=map[x]; }*/ if(a.ii==1) { a.value+=num[1]; num[1]=0; sum+=a.value; cont++; if(cont>=k) break; } else { if(num[x]==0) { a.ii=1; a.deep=0; } else { a.ii=x; a.deep=Deep[x]; a.value+=num[x]; num[x]=0; } Q.push(a); } } printf("Case #%d: %I64d ",r++,sum); } return 0; }