All Tracks Algorithms Dynamic Programming Problem

Shubham and Tree-2
Tag(s):

Algorithms, Dynamic Programming, Medium-Hard, Tree

Problem
Editorial
Analytics

You are given a tree consisting of n nodes and rooted at node 1. Each node of the tree is colored either black or white and also has a certain joy value associated with it. Your task is to find a connected subgraph of this tree containing exactly i black nodes and having maximum joy value for each i ranging from 1 to n .

Some definitions:
A subgraph of the tree is a graph whose vertex set(S) is a subset of the nodes of the original tree and consists of exactly those edges of the original tree whose both end points are present in S.
Joy value of a subgraph is the sum of joy values of all nodes present in the subgraph.

Input format
First line: n denoting the number of tree nodes
Next n-1 lines, each contain 2 integers representing a tree edge.
Next line contains n integers denoting the color of the nodes. Black color is denoted by 1 and white color by 0.
Next line contains n integers denoting the joy values of the nodes.

Output format
Output the maximum joy value of a connected subgraph containing exactly i nodes for each i from 1 to n, each on a new line.
If for some i, there is no connected subgraph consisting of exactly i black nodes, output "Not Found"(without quotes) instead.

Constraints
\(1\le n\le 5000\)
\(-10^9\le Joy Value\le 10^9\)

SAMPLE INPUT
4
1 2
1 3
3 4
1 1 0 1
-2 -1 1 2

SAMPLE OUTPUT
3
1
0
Not Found
Explanation

Nodes in subgraph containing exactly 1 black node and having maximum joy value: {3,4}
Nodes in subgraph containing exactly 2 black node and having maximum joy value: {1,3,4}
Nodes in subgraph containing exactly 3 black node and having maximum joy value: {1,2,3,4}
Nodes in subgraph containing exactly 4 black node and having maximum joy value: No such subgraph

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

January Easy '18

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?