Counting Maximum Weighted Independent Set Distributions on a Tree

A tree with n vertices and a positive integer k is given. For each vertex, a weight is assigned uniformly and independently from the set {1, 2, …, k}. For each weight assignment, one can compute the value of the maximum weighted independent set of the tree. (Recall that an independent set of a graph is a set of vertices no two of which are adjacent.)

The maximum weighted independent set value is computed by the following recurrence on a tree rooted at 1. For every vertex u, let

\[\textstyle dp[u]_1 = w(u) + \sum_{v \in child(u)} dp[v]_0,\quad dp[u]_0 = \sum_{v \in child(u)} f(v),\quad f(u) = \max\{dp[u]_1,\,dp[u]_0\} \]

where w(u) is the weight of vertex u and the children of u are taken in some arbitrary rooted tree order. Note that since w(u) is chosen from \(\{1,2,\dots,k\}\) (so \(w(u)\ge1\)) and because the tree has at least one vertex, the final answer satisfies

\[ 1 \le f(1) \le n\,k. \]

Your task is to count, over all \(k^n\) possible weight assignments, how many assignments yield each possible answer between 1 and \(n\,k\) (inclusive). That is, for each integer s with \(1\le s\le n\,k\), compute the number of weight assignments for which the answer (i.e. the maximum weighted independent set sum) equals \(s\).

Note: In the dynamic programming recurrence the decision at each vertex is made automatically by the maximum function. However, in the generation of assignments every vertex gets a weight (even if it is not used in the optimal solution). Therefore, even though one might think of the recurrence as having two "branches" (choosing or not choosing a vertex), the final answer is computed by taking

\[ f(u) = \max\Bigl\{\,\sum_{v\in child(u)} f(v),\,\bigl(w(u)+\sum_{v\in child(u)} dp[v]_0\bigr)\Bigr\}. \]
When combining the contributions from the children, note that the sums used in the above recurrence come from the same assignment on the children, so the two parts are not independent.

It is recommended to use a joint dynamic programming approach that computes for each subtree a pair of numbers \( (f, A) \) where f is the final answer in the subtree and A is the value \(dp[u]_0 = \sum_{v \in child(u)} f(v)\) (which is used in the parent's recurrence). Using a careful convolution over the children and then processing the contribution of the current vertex (taking into account its weight) will lead to a solution.

Input Format:
The first line contains two integers n and k (n is the number of vertices, and k is the upper bound for vertex weights). Then n-1 lines follow, each containing two integers u and v representing an edge between vertices u and v. The tree is rooted at vertex 1.

inputFormat

The first line contains two integers n and k (1 ≤ n, k ≤ ... depending on the constraints).
Each of the next n-1 lines contains two integers u and v indicating there is an edge between vertices u and v.

outputFormat

Output n*k space‐separated integers. The i^th number (1 ≤ i ≤ n*k) should be the count of weight assignments that yield a maximum weighted independent set sum equal to i. If none yield a certain value, output 0 for that value.

sample

1 3

1 1 1