Home STD Contest Notification Clarification Problems Ranklist Status Print Sign Out
1006的数据已经更新,提交已重判,请各位查看。More...

The Hanged Man

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 2    Accepted Submission(s): 1


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

  • 1 ≤ n ≤ 50

  • 1 ≤ m ≤ 5000

  • 1 ≤ $a_i$ ≤ m

  • 1 ≤ $b_i$ ≤ $10^6$

  • 1 ≤ $u_i$, $v_i$ ≤ $n$
  •  

    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
    3 3 2 1 1 1 1 1 1 1 2 1 3 4 5 1 1 2 2 3 2 2 1 1 2 2 3 3 4 5 10 3 1 2 2 4 4 7 8 5 16 1 2 1 3 2 4 2 5
     

    Sample Output
    Case 1: 3 1 Case 2: 1 1 2 2 0 Case 3: 0 1 1 1 1 1 1 1 1 1
     

    Source
    642ccpc吉林
     

    Statistic | Submit | Clarifications | Back