题意是给你一棵树 n个点 n-1条边 起点是1 每个点都有权值 每次能从根节点走到叶子节点 经行k次游戏 每次都是从1开始 拿过的点的权值不能拿第二次 问最大权值和；

开始看到题时也没想到什么方法 就按照常规的来 结果超时了 试着优化了好多次 最后过了 百度题解说是树链剖分 醉了 还没学！！！

?

说说我的做法吧 map【i】=a表示i节点的跟节点为a节点 从所有叶子节点开始入队（有点队列里有三个变量 分别是节点编号 权值 深度 优先级看代码 里面有点贪心的意思） 每次走根节点 如果根节点没走过 则走它 并把该店权值变为0 否则直接跳到1这个节点（如果一个个跳可能会超时）再入队 当出队的编号为1时并且拿的个数小于游戏次数 则拿 否则结束 在跑深度的时候有个优化 开始没有超时了 如果该节点深度已知了 则以后的根节点就不用跑了！！！ 具体看代码吧

?

?

#include
  
   
#include
   
     #include
    
      #include
      
      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\n",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\n"
      ,r
      ++,sum
      ); } return 0
      ; }
     
    
   
  

?

?