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

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...

## This Problem was Asked in Challenge Name

January Easy '18

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Sorting
• Data Structures > Hash Tables
• Data Structures > Advanced Data Structures
• Algorithms > Dynamic Programming

?