[HDU5909]Tree Cutting(点分治,计数动态规划)

发布于 2018-02-26  156 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU5909]Tree Cutting(点分治,计数动态规划)

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.

Http

HDU

Tag

点分治,计数动态规划

题目大意

给出一棵树,定义树中连通块的权为连通块中所有点的点权的异或和。分别求权为\([1,k]\)的连通块个数。

解决思路

点分治,要求当前重心必选,那么就往下选的话,要么一定选择父亲,此时直接把父亲的计数往儿子传,要么父亲不选,此时儿子也不选,这就是连通块到父亲就结束的答案。
如何统计答案呢?我们记\(F[i][j]\)表示当\(dfs\)搜索到\(i\)这个点时,它所在的连通块异或和为\(j\)的方案数。这里我们还要求,\(i\)的答案只能从\(i\)的子树以及在遍历\(i\)的子树之前遍历的其他以当前重心为根的子树转移,要求这样转移顺序的目的是保证不会出现不合法情况和避免重复计算。那么,每向下递归\(i\)的儿子时,把\(F[i][j]\)的\(j\)异或上儿子的点权向下传递,递归回来之后,再把儿子的答案累加回来。这样做同样保证了枚举顺序。

代码

#pragma comment(linker,"/STACK:102400000,102400000")
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=1010;
const int maxNum=1030;
const int maxM=maxN*2;
const int Mod=1e9+7;
const int inf=2147483647;

int n,m;
int nowsum,root;
int Size[maxN],mxSon[maxN];
int edgecnt=0,Head[maxN],Next[maxM],V[maxM];
int Node[maxN];
bool vis[maxN];
int F[maxN][maxNum],Ans[maxNum];

void Add_Edge(int u,int v);
void GetRoot(int u,int fa);
void Solve(int u);
void GetAns(int u,int fa);

int main()
{
    ios::sync_with_stdio(false);
    int T;cin>>T;
    while (T--)
    {
        edgecnt=0;mem(Head,-1);mem(vis,0);mem(Ans,0);
        cin>>n>>m;
        for (int i=1;i<=n;i++) cin>>Node[i];
        for (int i=1;i<n;i++)
        {
            int u,v;cin>>u>>v;
            Add_Edge(u,v);Add_Edge(v,u);
        }
        root=0;mxSon[0]=inf;nowsum=n;
        GetRoot(1,0);
        Solve(root);
        for (int i=0;i<m;i++){
            printf("%d",Ans[i]);
            if (i==m-1) printf("\n");
            else printf(" ");
        }
    }
    return 0;
}

void Add_Edge(int u,int v)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;
    return;
}

void GetRoot(int u,int fa)//得到重心
{
    Size[u]=1;mxSon[u]=0;
    for (int i=Head[u];i!=-1;i=Next[i])
        if ((vis[V[i]]==0)&&(V[i]!=fa))
        {
            GetRoot(V[i],u);Size[u]+=Size[V[i]];
            mxSon[u]=max(mxSon[u],Size[V[i]]);
        }
    mxSon[u]=max(mxSon[u],nowsum-Size[u]);
    if (mxSon[u]<mxSon[root]) root=u;
    return;
}

void Solve(int u)//分治
{
    for (int i=0;i<m;i++) F[u][i]=0;//清空
    F[u][Node[u]]=1;vis[u]=1;//初始化
    GetAns(u,0);//dfs递归
    for (int i=0;i<m;i++) Ans[i]=(Ans[i]+F[u][i])%Mod;
    for (int i=Head[u];i!=-1;i=Next[i])
        if (vis[V[i]]==0)
        {
            root=0;nowsum=Size[V[i]];
            GetRoot(V[i],0);
            Solve(root);
        }
    return;
}

void GetAns(int u,int fa)
{
    for (int i=Head[u];i!=-1;i=Next[i])
        if ((V[i]!=fa)&&(vis[V[i]]==0))
        {
            for (int j=0;j<m;j++) F[V[i]][j]=0;//子节点初始化
            for (int j=0;j<m;j++) F[V[i]][Node[V[i]]^j]=(F[V[i]][Node[V[i]]^j]+F[u][j])%Mod;//把值传给儿子
            GetAns(V[i],u);
            for (int j=0;j<m;j++) F[u][j]=(F[u][j]+F[V[i]][j])%Mod;//再从儿子更新回来
        }
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU5909]Tree Cutting(点分治,计数动态规划)


HNCJ OIer