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.

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


上一篇: 记NOIP2018

下一篇: 洛谷P3222 [HNOI2012]射箭

568 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航