CF评测机最近读入怎么这么慢啊，一样的算法，\(10^6\)的输入用scanf和关流cin都TLE飞，一定要用fread快读才能卡过可海星
这个题比赛的时候最后封榜后徐神和祁神就在一起冲这个题，给出的贪心的思路其实也是对的，但没有想到可以分奇偶性然后DP来验证
当然也和我占着机子写不出C红温有关，最后徐神想上去写结果没时间了
回到题目本身，首先我们有一个很自然的贪心想法，即任意指定一个点为根，然后考虑断开的都是指向父亲的边
很容易证明，如果当前\(x\)点以及它的子树中可以找出一个包含\(x\)点，且权值和为\(k\)的连通块的话，那么断开\(x\)与其父亲的边一定不会让答案变劣
（这里要注意这个连通块一定要钦定包含\(x\)，不然就会和我一样WA的飞起）
因此现在问题来到要如何验证某点所在的连通块能否凑出权值为\(k\)了，由于权值只有\(\{0,1,2\}\)，因此可以从奇偶性角度出发
考虑对于任一个权值和为\(y>2\)的连通块，显然我们可以删去它所有权值为\(0\)的叶子节点来保证权值和不变且不影响其它部分
那么我们可以发现这个连通块此时必然包含至少两个点权非\(0\)的叶子节点，我们讨论一下：
- 若存在一个点权为\(2\)的叶子节点，直接删去它就可以得到权值和为\(y-2\)的连通块
- 若不存在一个点权为\(2\)的叶子节点，说明至少存在两个点权为\(1\)的叶子节点，删去其中的两个也可以得到权值和为\(y-2\)的连通块
因此，我们发现如果权值和为\(y>2\)的连通块可以被表示，那么所有权值和为\(y,y-2,y-4,\cdots\)的连通块都可以被表示
因此我们只要记录权值和为奇数/偶数时，权值和的最大值即可，然后再注意下上面说的一定要包含自身这个限制即可
总复杂度\(O(n)\)
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1e6+5,INF=1e9;
int t,n,k,c[N],x,y,f[N][2],g[N][2],ans; vector <int> v[N];
#define Tp template <typename T>
class FileInputOutput
{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
#define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=Fout)++=ch))
char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[30];
public:
inline FileInputOutput(void) { Ftop=Fout; Fend=Fout+S; }
Tp inline void read(T& x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
}
Tp inline void write(T x,const char ch='\n')
{
RI ptop=0; while (pt[++ptop]=x%10,x/=10);
while (ptop) pc(pt[ptop--]+48); pc(ch);
}
inline void flush(void)
{
fwrite(Fout,1,Ftop-Fout,stdout);
}
#undef tc
#undef pc
}F;
inline void DFS(CI now=1,CI fa=0)
{
f[now][0]=f[now][1]=g[now][0]=g[now][1]=-INF;
for (auto to:v[now]) if (to!=fa)
{
DFS(to,now); int tmp[2]={f[now][0],f[now][1]};
for (RI p=0;p<2;++p)
{
tmp[p]=max(tmp[p],g[to][p]);
for (RI q=0;q<2;++q) tmp[p^q]=max(tmp[p^q],f[now][p]+g[to][q]);
}
f[now][0]=tmp[0]; f[now][1]=tmp[1];
}
int d=c[now]&1; g[now][d]=c[now];
for (RI i=0;i<2;++i) g[now][i]=max(g[now][i],f[now][i^d]+c[now]);
//printf("%d %d %d\n",now,g[now][0],g[now][1]);
if (g[now][k&1]>=k) ++ans,g[now][0]=g[now][1]=-INF;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (F.read(t);t;--t)
{
RI i; for (F.read(n),F.read(k),i=1;i<=n;++i) F.read(c[i]),v[i].clear();
for (i=1;i<n;++i) F.read(x),F.read(y),v[x].push_back(y),v[y].push_back(x);
ans=0; DFS(); F.write(ans);
}
return F.flush(),0;
}