HDUOJ 5909 Tree Cutting

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=5909

题意:给定一棵树,每个节点有自己的权值w_i对于[1,m ]的每个数字统计有多少联通子图的异或和等于对应的数字。

思路:基本上跟HDUOJ6268一样,不过背包设初值的时候设错了找了好久...还是自己DP水平不行,这题据说还可以用FWT做,可是...我根本不会FWT...要找时间学了啊。

#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1000+10;
const int P=1e9+7;
int T,n,m,ans[2500],i,x,y,sum,root,tot,w[N],f[N],sz[N],sz2[N],id[N],dp[N][2500];
bool vis[N];
vector<int>G[N];
void getroot(int u,int fa){
    sz[u]=1,f[u]=0;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==fa || vis[v]) continue;
        getroot(v,u);
        sz[u]+=sz[v];
        f[u]=max(f[u],sz[v]);
    }
    f[u]=max(f[u],sum-sz[u]);
    if (f[u]<f[root]) root=u;
}
void dfs(int u,int fa){
    id[++tot]=u;
    sz2[u]=1;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==fa || vis[v]) continue;
        dfs(v,u);
        sz2[u]+=sz2[v];
    }
}
void up(int&a,int b){a+=b;if(a>=P)a-=P;}
void solve(int u){
    vis[u]=1,tot=0,dfs(u,0);
    int i,V;
    for(i=1;i<=tot+1;i++)for(V=0;V<=m;V++)dp[i][V]=0;
    for(i=1;i<=tot;i++)dp[i][w[id[i]]]=1;
    for (i=tot;i>=1;i--){
        int u=id[i];
        for (V=m-1;V>=0;V--){
            up(dp[i][V],dp[i+1][V^w[u]]);
            up(dp[i][V],dp[i+sz2[u]][V]);
        }
    }
    for (i=0;i<m;i++) up(ans[i],dp[1][i]);
    for (i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (vis[v]) continue;
        sum=sz[v],root=0;
        getroot(v,0);
        solve(root);
    }
}
int main(){
    for (read(T);T--;){
        read(n),read(m);
        for (i=1;i<=n;i++) G[i].clear(),vis[i]=0;
        for (i=0;i<m;i++) ans[i]=0;
        for (i=1;i<=n;i++) read(w[i]);
        for (i=1;i<n;i++){
            read(x),read(y);
            G[x].push_back(y);
            G[y].push_back(x);
        }
        sum=n,root=0,f[0]=n+1;
        getroot(1,0);
        solve(root);
        for (i=0;i<m;i++) printf("%d%c",ans[i],i==m-1?'\n':' ');
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注