rockdu
Problem Description
Byteasar has a tree T with n vertices conveniently labeled with 1,2,...,n. Each vertex of the tree has an integer value vi.
The value of a non-empty tree T is equal to v1⊕v2⊕...⊕vn, where ⊕ denotes bitwise-xor.
Now for every integer k from [0,m), please calculate the number of non-empty subtree of T which value are equal to k.
A subtree of T is a subgraph of T that is also a tree.
The value of a non-empty tree T is equal to v1⊕v2⊕...⊕vn, where ⊕ denotes bitwise-xor.
Now for every integer k from [0,m), please calculate the number of non-empty subtree of T which value are equal to k.
A subtree of T is a subgraph of T that is also a tree.
Input
The first line of the input contains an integer T(1≤T≤10), denoting the number of test cases.
In each test case, the first line of the input contains two integers n(n≤1000) and m(1≤m≤210), denoting the size of the tree T and the upper-bound of v.
The second line of the input contains n integers v1,v2,v3,...,vn(0≤vi<m), denoting the value of each node.
Each of the following n−1 lines contains two integers ai,bi, denoting an edge between vertices ai and bi(1≤ai,bi≤n).
It is guaranteed that m can be represent as 2k, where k is a non-negative integer.
In each test case, the first line of the input contains two integers n(n≤1000) and m(1≤m≤210), denoting the size of the tree T and the upper-bound of v.
The second line of the input contains n integers v1,v2,v3,...,vn(0≤vi<m), denoting the value of each node.
Each of the following n−1 lines contains two integers ai,bi, denoting an edge between vertices ai and bi(1≤ai,bi≤n).
It is guaranteed that m can be represent as 2k, where k is a non-negative integer.
Output
For each test case, print a line with m integers, the i-th number denotes the number of non-empty subtree of T which value are equal to i.
The answer is huge, so please module 109+7.
The answer is huge, so please module 109+7.
Sample Input
2 4 4 2 0 1 3 1 2 1 3 1 4 4 4 0 1 3 1 1 2 1 3 1 4
Sample Output
3 3 2 3 2 4 2 3
Source
题意：给你一棵树，每个点有点权，问异或和为k的连通块有多少个。
十分模板的FWT题目，先考虑树形dp，f(u,k)表示以点u为根向下延伸的连通块中异或值为k的有多少种。最后将每一个u延伸出去异或和为k的答案都加到总答案中就可以了。
显然这是个很生硬的集合异或卷积，使用FWT就可以通过此题。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 1e3 + 5;
const int mod = 1e9 + 7;
const int V = 1 << 10;
struct edge {
int v, next;
} e[maxn << 1];
int head[maxn], cnt;
void adde(const int &u, const int &v) {
e[++cnt] = (edge) {v, head[u]};
head[u] = cnt;
}
LL inv2;
LL fpow(LL a, int b) {
LL ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod, b >>= 1;
}
return ans;
}
void Add(int &x, const int &y) {
x += y; if(x >= mod) x -= mod;
}
int dp[maxn][V], tmp[V], ans[V], n, m, w[maxn], u, v;
void FWT(int *A, int n, int t) {
for(register int i = 1; i < 1 << n; i <<= 1)
for(register int p = i << 1, j = 0; j < 1 << n; j += p)
for(register int k = 0; k < i; ++k) {
int x = A[j + k], y = A[i + j + k];
A[j + k] = (x + y) % mod;
A[i + j + k] = (x - y + mod) % mod;
if(!t) {
A[j + k] = inv2 * A[j + k] % mod;
A[i + j + k] = inv2 * A[i + j + k] % mod;
}
}
}
void DP(int u, int p) {
memset(dp[u], 0, sizeof(dp[u]));
int flag = 0, leaf = 1;
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(v == p) continue;
DP(v, u), leaf = 0;
}
if(leaf) {
++dp[u][w[u]], ++dp[u][0];
return ++ans[w[u]], FWT(dp[u], 10, 1);
}
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(v == p) continue;
if(!flag) {
for(register int j = 0; j < V; ++j)
dp[u][j] = dp[v][j];
flag = 1;
} else {
for(register int j = 0; j < V; ++j)
dp[u][j] = 1ll * dp[v][j] * dp[u][j] % mod;
}
}
FWT(dp[u], 10, 0);
for(register int j = 0; j < V; ++j)
tmp[j] = dp[u][j ^ w[u]];
memcpy(dp[u], tmp, sizeof(tmp));
for(register int j = 0; j < V; ++j)
Add(ans[j], dp[u][j]);
++dp[u][0];
FWT(dp[u], 10, 1);
}
int t;
int main() {
scanf("%d", &t);
inv2 = fpow(2, mod - 2);
while(t--) {
memset(ans, 0, sizeof(ans));
memset(head, 0, sizeof(head));
scanf("%d%d", &n, &m), cnt = 0;
for(register int i = 1; i <= n; ++i)
scanf("%d", &w[i]);
for(register int i = 1; i < n; ++i) {
scanf("%d%d", &u, &v);
adde(u, v), adde(v, u);
}
DP(1, 0);
for(register int i = 0; i < m; ++i) {
if(i == 0) printf("%d", ans[i]);
else printf(" %d", ans[i]);
}
putchar('\n');
}
return 0;
}
没有帐号? 立即注册