Harvesting apples and pears from k tree nodes

A tree $T$ has $n$ nodes and $n-1$ edges. The nodes are numbered from 0 to $n-1$, and node 0 is the root. The edges have no weights. Each node in $T$ has one apple, has one pear, or has neither. Starting from the root, you visit neighboring nodes to harvest apples and pears. When you visit at most $k$ nodes, output the number of apples and the number of pears that maximize (number of apples) $\times$ (number of pears). If several pairs give the maximum product, output the pair with more apples. If several pairs have the same maximum product and the same number of apples, output the pair with more pears. A node visited more than once counts as visited once. The root counts as visited. Even if you visit a node with an apple or a pear several times, you can harvest only one apple or pear from it, on the first visit.

The first line contains the number of nodes $n$ and the integer $k$, separated by a space.

The next $n-1$ lines each contain one edge. Each edge is given as a parent node number $p$ and a child node number $c$, separated by a space.

The next line contains $n$ integers, separated by spaces. The $i$-th integer gives the information of node $i-1$, for nodes 0 to $n-1$. A value of 0 means the node has neither an apple nor a pear. A value of 1 means the node has one apple only. A value of 2 means the node has one pear only.

On the first line, print the number of apples and the number of pears that satisfy the conditions of the problem, separated by a space.

• $1 \le k \le n \le 17$
• $0 \le p, c \le n-1$, $p \neq c$
• The graph formed by the edges is a tree.
• The information of each node is 0, 1, or 2.