hdu 5909 Tree Cutting [树形DP fwt]

男娘i 2022-03-27 13:48 152阅读 0赞

# [hdu 5909 Tree Cutting][] #

题意：一颗无根树，每个点有权值，连通子树的权值为异或和，求异或和为\[0,m)的方案数

--------------------

\\(f\[i\]\[j\]\\)表示子树i中经过i的连通子树异或和为j的方案数

转移类似背包，可以用fwt加速

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    const int N = (1<<10) + 5, P = 1e9+7, inv2 = (P+1)/2;
    inline int read() {
        char c=getchar(); int x=0,f=1;
        while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}
        while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}
        return x*f;
    }
    
    int n, m, val[N];
    struct edge{int v, ne;} e[N<<1];
    int cnt, h[N];
    inline void ins(int u, int v) {
        e[++cnt] = (edge){v, h[u]}; h[u] = cnt;
        e[++cnt] = (edge){u, h[v]}; h[v] = cnt;
    }
    int f[N][N], ans[N];
    
    void fwt(int *a, int n, int flag) {
        for(int l=2; l<=n; l<<=1) {
            int m = l>>1;
            for(int *p = a; p != a+n; p += l) 
                for(int k=0; k<m; k++) {
                    int x = p[k], y = p[k+m];
                    if(flag == 1) p[k] = (x + y) %P, p[k+m] = (x - y + P) %P;
                    else p[k] = (ll) (x + y) * inv2 %P, p[k+m] = (ll) (x - y + P) * inv2 %P;
                }
        }
    }
    
    int t[N];
    void dp(int u, int fa) {
        int *a = f[u]; a[val[u]] = 1; //fwt(a, m, 1);
        for(int i=h[u];i;i=e[i].ne) {
            int v = e[i].v;
            if(v == fa) continue;
            dp(v, u); int *b = f[v];
            for(int i=0; i<m; i++) t[i] = a[i];
            fwt(t, m, 1); fwt(b, m, 1);
            for(int i=0; i<m; i++) t[i] = (ll) t[i] * b[i] %P;
            fwt(t, m, -1); 
            for(int i=0; i<m; i++) a[i] = (a[i] + t[i]) %P;
        }
        for(int i=0; i<m; i++) ans[i] = (ans[i] + a[i]) %P;
    }
    
    int main() {
        freopen("in", "r", stdin);
        int T = read();
        while(T--) {
            n = read(); m = read();
            for(int i=1; i<=n; i++) val[i] = read();
            cnt = 0; memset(h, 0, sizeof(h));
            for(int i=1; i<n; i++) ins(read(), read());
            memset(f, 0, sizeof(f)); memset(ans, 0, sizeof(ans));
            dp(1, 0);
            for(int i=0; i<m; i++) printf("%d%c", ans[i], i==m-1 ? '\n' : ' ');
        }
    }

[hdu 5909 Tree Cutting]: http://acm.hdu.edu.cn/showproblem.php?pid=5909