徐老师的奇偶树

文件读写

• 输入文件tree.in
• 输出文件tree.out

限制

• 1000ms
• 512MB

题目描述

徐老师有一棵树，树上包含 $n$ 个节点，第 $i$ 个节点的权值为 $a_i$

由于 $a_i$ 只有三种值：$0,1,2$，所以徐老师将这棵树称之为一棵 奇偶树

现在徐老师想在这棵树上断开一部分边，使得这棵树变成一个森林

现在徐老师想知道，如何断开边可以使得森林中存在尽可能多的权值和恰好为 $k$ 的树？

P.S. 本题的输入输出使用 $scanf,printf$ 会导致超时，请使用 $cin,cout$，并取消同步流，格式如下：

int main(){
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    输入使用 cin
    cin >> T;

    ......
    输出使用 cout，换行使用 "\n"
    cout << ans << "\n";
}

输入格式

输入第一行包含一个整数 $T$，表示测试数据数量

对于每组测试数据：

输入第一行包含两个整数 $n,k$ 含义如题

输入第二行包含 $n$ 个整数表示每个节点的权值 $a_i$

接下来 $n - 1$ 行，每行包含两个整数 $u,v$ 表示树上的一条边，连接了 $u,v$ 两个节点

输出格式

对于每组测试数据输出一个整数，表示断开一部分边后，这个森林里最多包含几个权值和恰好为 $k$ 的树

数据范围

对于 $30\%$ 的数据，$1 \leq \sum n_i \leq 200,1 \leq n \leq 20$。

对于 $60\%$ 的数据，$1 \leq \sum n_i \leq 10^4,1 \leq n \leq 1000$。

对于 $100\%$ 的数据，$1 \leq \sum n_i \leq 10^6,1 \leq k \leq 10^6$。

样例输入

4
7 5
1 2 1 2 2 1 2
1 2
2 3
3 4
3 5
5 6
5 7
2 2
1 0
1 2
1 1
1
1 2
1

样例输出

2
0
1
0

样例解释

对于第一组测试数据我们可以断开 $3-5$ 和 $1-2$ 两条边，这样最后会有两棵树的权值和恰好为 $5$