|
||||||||||
The Hanged ManTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 537 Accepted Submission(s): 142 Problem Description The Hanged Man shows a man suspended from a t-shaped cross made out of living wood. The man is hanging upside-down, viewing the world from a completely different perspective. His facial expression is calm and serene, suggesting that he is in this hanging position by his own choice. Bobo has two arrays $a_1$, $a_2$, . . . , $a_n$ and $b_1$, $b_2$, . . . , $b_n$. For each set $S$ $\subseteq$ {1, 2, . . . , $n$}, he denotes $A(S)$ = $\sum\limits_{i \subseteq S}$ $a_i$ and $B(S)$ = $\sum\limits_{i \subseteq S}$ $b_i$. Bobo also has a tree of $n$ vertices conveniently labeled with 1, 2, . . . , $n$. A set $S$ $\subseteq$ {1, 2, . . . , $n$} is an independent set if and only if for any two vertices $u$ and $v$ connected directly on the tree, either $u$ $\notin$ $S$ or $v$ $\notin$ $S$ holds. For each $x$ $\subseteq$ {1, 2, . . . , $m$}, Bobo would like to find f(x) which is the number of independnt set S with $A(S)$ = $x$ and $B(S)$ maximized. Formally, f(x) = |{$S$ : $S$ $\subseteq$ $I$, $A(S)$ = $x$, $B(S)$ = $max^{A(T)=x}_{T \subseteq I}$ $B(T)$}| where $I$ stands for the family of the independent sets. Suppose there is no $A(S)$ = $x$ for some $i$, then $f(x)$ = 0. Find out the value of f(1), f(2), . . . , f(m). Input The first line of the input contains one integer $T$ ≤ 20, denoting the number of testcases. Then $T$ testcases follows, separated with no extra blank lines. The first line of each test case contains two integers $n$ and $m$. The i-th of the following n lines contains two integers $a_i$ and $b_i$. The i-th of the last (n - 1) lines contains two integers $u_i$ and $v_i$ which denotes an edge connected vertices $u_i$ and $v_i$. Output For each testcase, first print "Case $i$:" in one line ($i$ indicates the case number, starting from 1). In the line, print m integers which denote f(1), f(2), . . . , f(m). Sample Input
Sample Output
Source | ||||||||||
|