Cerinta completa

A tree, , has vertices numbered from to and is rooted at vertex . Each vertex has an integer weight, , associated with it, and ‘s total weight is the sum of the weights of its nodes. A single remove operation removes the subtree rooted at some arbitrary vertex from tree .

Given , perform up to remove operations so that the total weight of the remaining vertices in is maximal. Then print ‘s maximal total weight on a new line.

Note: If ‘s total weight is already maximal, you may opt to remove nodes.

Input Format

The first line contains two space-separated integers, and , respectively.
The second line contains space-separated integers describing the respective weights for each node in the tree, where the integer is the weight of the vertex.
Each of the subsequent lines contains a pair of space-separated integers, and , describing an edge connecting vertex to vertex .

Constraints

Output Format

Print a single integer denoting the largest total weight of ‘s remaining vertices.

Sample Input

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

Sample Output

2

Explanation

We perform remove operations:

  1. Remove the subtree rooted at node . Losing this subtree’s weight increases the tree’s total weight by .
  2. Remove the subtree rooted at node . Losing this subtree’s weight increases the tree’s total weight by .

The sum of our remaining positively-weighted nodes is , so we print on a new line.

tree-pruning

Limbajul de programare folosit: cpp14

Cod:

#include<stdio.h>
#include<stdlib.h>
typedef struct _node
{
    int x;
    struct _node *next;
}node;
int a[100000], b[100000], size[100000], trace[100000] = {0}, NN = 0;
long long dp[100001][201];
node *table[100000] = {0};
void insert_edge(int x, int y)
{
    node *t;
    t = (node*)malloc(sizeof(node));
    t -> x = y;
    t -> next = table[x];
    table[x] = t;
    t = (node*)malloc(sizeof(node));
    t -> x = x;
    t -> next = table[y];
    table[y] = t;
    return;
}
void dfs(int x)
{
    node *t;
    int i = NN;
    trace[x] = 1;
    b[NN++] = a[x];
    for( t = table[x] ; t ; t = t -> next )
    {
        if(!trace[t -> x])
        {
            dfs(t -> x);
        }
    }
    size[i] = NN - i;
    return;
}
long long max(long long x, long long y)
{
  return ( x > y ) ? x : y;
}
int main()
{
    int N, K, x, y, i, j;
    long long sum;
    scanf("%d%d", &N, &K);
    for( i = 0 ; i < N ; i++ )
    {
        scanf("%d", a + i);
    }
    for( i = 0 ; i < N - 1 ; i++ )
    {
        scanf("%d%d", &x, &y);
        insert_edge(x-1, y-1);
    }
    dfs(0);
    for( i = 0 ; i <= K ; i++ )
        dp[0][i] = 0;
    for( i = 1, sum = 0 ; i <= N ; i++ )
    {
        sum += b[i-1];
        for( j = 0 ; j <= K ; j++ )
        {
            dp[i][j] = sum;
        }
    }
    for( i = 1, sum = 0 ; i <= N ; i++ )
    {
        for( j = 0 ; j <= K ; j++ )
        {
            if( j != K )
            {
                dp[i+size[i-1]-1][j+1] = max(dp[i+size[i-1]-1][j+1], dp[i-1][j]);
            }
            dp[i][j] = max(dp[i][j], dp[i-1][j] + b[i-1]);
        }
    }
    printf("%lld", dp[N][K]);
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464647744

Link challenge: https://www.hackerrank.com/challenges/tree-pruning/problem

Tree Pruning