Cowflix Subscription Optimization

Bessie loves watching shows on Cowflix but now the new subscription model forces her to choose a set of disjoint connected components on Farmer John’s farm (which is a tree) so that all the nodes where she watches Cowflix are covered. The tree has \(N\) nodes (with \(2 \le N \le 2 \cdot 10^5\)) and for each node, Bessie either watches Cowflix or she doesn’t. It is guaranteed that she watches Cowflix in at least one node.

The rules for the new subscription are as follows: you must choose a set of disjoint connected components \(c_1, c_2, \cdots, c_C\) such that every node where Bessie watches Cowflix is contained in at least one \(c_i\). For each chosen component \(c_i\), the cost is \(|c_i|+k\) moonies, where \(|c_i|\) is the number of nodes in that component and \(k\) is an integer parameter. The total cost is given by

[ \text{Cost} = \sum_{i=1}^{C}\bigl(|c_i|+k\bigr),. ]

Bessie is worried that these subscriptions may be too expensive. In order to help her decide whether to keep using Cowflix, she wants to know the minimum amount she would need to pay in order to cover all her viewing nodes. Since Cowflix has not yet announced the value of \(k\), you must answer the question for every integer value of \(k\) from 1 to \(N\).

Note: The time limit for this problem is 3 seconds (1.5× the default).

Problem Summary

• You are given a tree with \(N\) nodes.
• A binary indicator for each node tells whether Bessie watches Cowflix there.
• You may cover the watched nodes by choosing one or more connected components. The cost for a connected component is its size plus \(k\), and nodes that are not watched need not be covered.
• Output the minimum total cost for each \(k\) from 1 to \(N\).

inputFormat

The input is given as follows:

N
u1 v1
u2 v2
... (N-1 lines of edges)
watch[1] watch[2] ... watch[N]

Here:

• \(N\) denotes the number of nodes.
• Each of the next \(N-1\) lines contains two integers \(u\) and \(v\) indicating an edge between nodes \(u\) and \(v\).
• The last line contains \(N\) integers (each 0 or 1) where 1 means that Bessie watches Cowflix at that node.

It is guaranteed that at least one of these numbers is 1.

outputFormat

Output \(N\) space‐separated integers, where the \(i\)th integer is the minimum total cost to cover all nodes where Bessie watches Cowflix when \(k=i\).

sample

3
1 2
2 3
1 0 1

4 5 6