Game

　　题目大意：一个游戏有n个场景形成了棵有根树，根节点是1，每个场景都有它的权值。然后一个人可以选择其中K个分支来走，而每个场景的权重只算一遍，问最大的权值和。

　　一开始想叉了，觉得是树形dp加背包，然后好麻烦就不懂写了，但其实根本没有那么难。就是用到了个树链的思想，把整棵树分成一条条链，这样就没有了重复部分，然后就是从中取k条权值和最大的链。

　　具体操作类似于树链剖分的分链处理(想起来树链剖分拖了很久没更，这两天更上）。如果不知道重链和重儿子是什么，可以先去学一下。在原来的定义里，重儿子是儿子节点中子树节点个数最多的节点，而我们这题就定义为儿子节点中拥有链权值和最大的那个节点。比如在样例1中

　　

　　2的重儿子就是3，而1的重儿子是2，这样就有1到3一条重链，加上4到4,5到5，3条链。然后我们把不是链顶部的节点权值清空（在上图中就是2和3）,最后把所有节点权值，挑选k个最大的。

1 #include
      
        2 #include
       
         3 using namespace std; 4 typedef long long ll; 5 const int N=101108; 6 struct Side{ 7     int v,ne; 8 }S[N]; 9 ll val[N];10 int sn,head[N],son[N];11 void init(int n)12 {13     sn=0;14     for(int i=0;i<=n;i++)15     {16         head[i]=-1;17         son[i]=0;18     }19 }20 void add(int u,int v)21 {22     S[sn].v=v;23     S[sn].ne=head[u];24     head[u]=sn++;25 }26 void dfs1(int u)27 {28     for(int i=head[u];i!=-1;i=S[i].ne)29     {30         int v=S[i].v;31         dfs1(v);//题目是单向边，不用在判断v是不是u的父亲32         if(val[v]>val[son[u]])33             son[u]=v; 34     }35     val[u]+=val[son[u]];//把它重儿子的权值算到它这里 36 }37 void dfs2(int u,int tf)38 {39     if(u!=tf)40         val[u]=0;//不是链的顶端，权值清空 41     if(!son[u])42         return ;43     dfs2(son[u],tf);44     for(int i=head[u];i!=-1;i=S[i].ne)45     {46         int v=S[i].v;47         if(v!=son[u])48             dfs2(v,v);49     }50 } 51 int main()52 {53     int t=1,T,n,k,u,v;54     scanf("%d",&T);55     while(t<=T)56     {57         scanf("%d%d",&n,&k);58         init(n);59         for(int i=1;i<=n;i++)60             scanf("%lld",&val[i]);61         for(int i=0;i
        
         =1&&k;i--,k--)71         {72             if(!val[i])73                 break;74             ans+=val[i];75         }76         printf("Case #%d: %lld\n",t++,ans);77     }78     return 0;79 }