Given a tree with N vertices numbered from 1 to N. The vertex 1 is the root of the tree. Each vertex is assigned with an integer weight. A remove operation can remove sub-tree rooted at an arbitrary vertex u. You must use at most K remove operations (possibly zero) so that the total weight of the remaining vertices is largest.

Input Format
The first line contains two integers N,K.
The second line contains N integers, the ith integer is the weight of the ith vertex.
Each of the next N−1 lines contains a pair of integers u and v, which represents an edge from vertex u to vertex v.

Output Format
Print out a single integer which is the largest total weight of the remaining vertices.

Constraints
2≤N≤105
1≤K≤200
−109≤weight≤109

Sample Input

5 2
1 1 -1 -1 -1
1 2
2 3
4 1
4 5

Sample Output

2

Explanation
We use 2 remove operations: one for the sub-tree rooted at 3 and the other one for the sub-tree rooted at 4. There are only 2 remaining vertices which are 1 and 2. The total weight is 1+1=2.

Copyright (c) 2015 HackerRank.
All Rights Reserved
Suggest Edits

Choose a translation

157 hackers have submitted code

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define MAX 100000
long long int k[MAX][200];
    
    int visited[MAX];
int main() {
    long long int N,K,u,w[MAX],v,sum,j,i;
        scanf("%lld%lld",&N,&K);
        i=1;
        while(i<=N)
            {
            scanf("%lld",&w[i]);
            i++;
        }
        i=0;
        sum =   0;
    i=0;
       while(i<N)
            {
           if(i!=0)
               {
            scanf("%lld%lld",&u,&v);
            //if(visited[u] == 0 && visited[v] == 0)
                sum =   w[u] + w[v];
            //else if(visited[u] != 0 && visited[v] == 0)
                //sum  = w[v];
            //else
                //sum  = w[u];
                
            visited[u] =1;
            visited[v] =1;   
           }
            for(j=0;j<=K;j++)
                {
                if(i==0||j==0)
                    k[i][j] = 0;
                else
                    {                    
                    if((sum + k[i-1][j]) > k[i-1][j])
                        k[i][j] = sum + k[i-1][j];
                    /*else if((w[u] + k[i-1][j]) > k[i-1][j])
                        k[i][j] = w[u] + k[i-1][j];
                    else if((w[v] + k[i-1][j]) > k[i-1][j])
                        k[i][j] = w[v] + k[i-1][j];*/ 
                    else
                        k[i][j] =   k[i-1][j];
                }
            }
            i++;
        }
    /*for(i=0;i<N;i++)
        {
        for(j=0;j<=K;j++)
            {
            printf("%d ",k[i][j]);
        }
        printf("\n");
    }*/
        printf("%lld\n",k[N-1][K]);
    return 0;
}

Compile & Run : https://ideone.com/s9dXhs
Follow on : https://twitter.com/codeifucansolve