题目：http://acm.hdu.edu.cn/showproblem.php?pid=5909
点分治，每次的 rt 是必选的点；
考虑必须选根的一个连通块，可以DP，决策就是在每个子树中决定选不选子树根，如果不选就跳过这个子树；
于是可以转化成 dfs 序上的DP；
每次重新标记一遍 dfs 序，但不改动 siz (也许可以改动但T了?)，可能因为 siz 还和点分治的过程有关。
代码如下：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int const xn=1025,inf=1025,mod=1e9+7; int n,m,v[xn],hd[xn],ct,to[xn<<1],nxt[xn<<1],siz[xn],dfn[xn],g[xn],tim; int ans[xn],f[xn][xn],rt,mx,nt[xn]; bool vis[xn]; int rd() { int ret=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return f?ret:-ret; } void upt(int &x,int y){x+=y; while(x>=mod)x-=mod; while(x<0)x+=mod;} void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;} void getrt(int x,int fa,int sum) { int nmx=0; siz[x]=1; for(int i=hd[x],u;i;i=nxt[i]) { if((u=to[i])==fa||vis[u])continue; getrt(u,x,sum); siz[x]+=siz[u]; if(siz[u]>nmx)nmx=siz[u]; } nmx=max(nmx,sum-siz[x]); if(nmx<mx)mx=nmx,rt=x; } void dfs(int x,int fa) { dfn[x]=++tim; g[tim]=v[x]; for(int i=hd[x],u;i;i=nxt[i]) if((u=to[i])!=fa&&!vis[u])dfs(u,x); nt[dfn[x]]=tim+1; } void work(int x,int ss) { vis[x]=1; tim=0; dfs(x,0); for(int i=1;i<=ss+1;i++)memset(f[i],0,sizeof f[i]); f[2][g[1]]=1; for(int i=2;i<=ss;i++) for(int j=0;j<m;j++) if(f[i][j])upt(f[i+1][j^g[i]],f[i][j]),upt(f[nt[i]][j],f[i][j]); //printf("x=%d ss=%d ",x,ss); for(int j=0;j<m;j++)upt(ans[j],f[ss+1][j]); //,printf("f[%d][%d]=%d ",dfn[x]+siz[x],j,f[dfn[x]+siz[x]][j]); for(int i=hd[x],u;i;i=nxt[i]) if(!vis[u=to[i]]) { int ns=(siz[u]>siz[x]?ss-siz[x]:siz[u]); mx=inf; getrt(u,0,ns); work(rt,ns); } } int main() { int T=rd(); while(T--) { n=rd(); m=rd(); for(int i=1;i<=n;i++)v[i]=rd(); ct=0; tim=0; for(int i=1;i<=n;i++)hd[i]=0; for(int i=1,x,y;i<n;i++)x=rd(),y=rd(),add(x,y),add(y,x); for(int j=0;j<m;j++)ans[j]=0; for(int i=1;i<=n;i++)vis[i]=0; mx=inf; getrt(1,0,n); work(rt,n); for(int j=0;j<m;j++)printf("%d%c",ans[j],j==m-1?' ':' '); } return 0; }