hdu5242 上海邀请赛优先队列+贪心

题意是给你一棵树 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
      ; }

hdu5242 上海邀请赛 优先队列+贪心