Shubham and Tree-2

4

1 votes
Tree, Dynamic Programming, Algorithms, Medium-Hard
Problem

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
1n5000
109JoyValue109

Time Limit: 2
Memory Limit: 256
Source Limit:
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

Editor Image

?