HDU5909 Tree Cutting
? 解题记录 ? ? HDU ? ? 动态规划 ? ? FMT|FWT ?    2018-11-25 17:13:36    568    0    0
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 v1v2...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(1T10), denoting the number of test cases.

In each test case, the first line of the input contains two integers n(n1000) and m(1m210), 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(0vi<m), denoting the value of each node.

Each of the following n1 lines contains two integers ai,bi, denoting an edge between vertices ai and bi(1ai,bin).

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.

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

## 显然这是个很生硬的集合异或卷积，使用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];
void adde(const int &u, const int &v) {
}

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)
++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));
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);
}
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;
}

568 人读过

0 条评论