题目链接

题解

设\(f[i][j]\)表示以\(i\)为根的子树，\(i\)一定取，剩余节点必须联通，异或和为\(j\)的方案数

初始化\(f[i][val[i]] = 1\)

枚举儿子\(v\)转移

\[f[i][j] = f[i][j] + \sum\limits_{x \; xor \; y = j} f[i][x] \centerdot f[v][y]\]

发现是一个异或卷积的形式

前面相当于和\(1\)的卷积，后面是和\(f[v]\)的卷积

\(FWT\)即可优化到\(O(nlogn + nm)\)

我被卡常了QAQ，需要注意一些细节

单独一个\(1\)做\(FWT\)是全\(1\)，转移乘\(f[v][j]\)时\(+1\)即可

每个\(f[i]\)做完\(FWT\)后不立即\(IFWT\)，可以直接参与转移，全部做完后再\(IFWT\)

循环展开大法好

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #define LL long long int#define REP(i,n) for (register int i = 1; i <= (n); i++)#define Redge(u) for (register int k = h[u],to; k; k = ed[k].nxt)#define cls(s,v) memset(s,v,sizeof(s))#define mp(a,b) make_pair
             
              (a,b)#define cp pair
              
               using namespace std;const int maxn = 2050,maxm = 100005,INF = 0x3f3f3f3f;inline int read(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();} while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();} return flag ? out : -out;}const int P = 1000000007;int n,m,deg,val[maxn],A[maxn][maxn],B[maxn],inv2,fa[maxn];int h[maxn],ne = 1;struct EDGE{int to,nxt;}ed[maxn << 1];inline void build(int u,int v){ ed[++ne] = (EDGE){v,h[u]}; h[u] = ne; ed[++ne] = (EDGE){u,h[v]}; h[v] = ne;}inline int qpow(int a,int b){ int re = 1; for (; b; b >>= 1,a = 1ll * a * a % P) if (b & 1) re = 1ll * re * a % P; return re;}inline void fwt(int* a,int n,int f){ for (int i = 1; i < n; i <<= 1) for (int j = 0; j < n; j += (i << 1)) for (int k = 0; k < i; k++){ int x = a[j + k],y = a[j + k + i]; a[j + k] = (x + y) % P,a[j + k + i] = (x - y + P) % P; if (f == -1) a[j + k] = 1ll * a[j + k] * inv2 % P,a[j + k + i] = 1ll * a[j + k + i] * inv2 % P; }}void dfs(int u){ for (register int i = 0; i < deg; i += 4){ A[u][i] = 0; A[u][i + 1] = 0; A[u][i + 2] = 0; A[u][i + 3] = 0; } A[u][val[u]] = 1; fwt(A[u],deg,1); Redge(u) if ((to = ed[k].to) != fa[u]){ fa[to] = u; dfs(to); for (register int i = 0; i < deg; i++) A[u][i] = 1ll * A[u][i] * (A[to][i] + 1) % P; }}int main(){ int T = read(); inv2 = qpow(2,P - 2); while (T--){ n = read(); m = read(); deg = 1; ne = 1; REP(i,n) h[i] = 0; while (deg < m) deg <<= 1; REP(i,n) val[i] = read(); for (int i = 1; i < n; i++) build(read(),read()); dfs(1); REP(i,n) fwt(A[i],deg,-1); for (register int i = 0; i < m; i++){ int ans = 0; for (register int j = 1; j <= n; j++) ans = (ans + A[j][i]) % P; printf("%d",ans); if (i != m - 1) putchar(' '); } puts(""); } return 0;}