读书人

HDU 4275 Color the Tree 树的不反复染

发布时间: 2012-09-20 09:36:50 作者: rapoo

HDU 4275 Color the Tree 树的不重复染色 求树的中心+hash

题意:给定n(n<=50000)个点组成的树,用m(m<=100000)种颜色染色,问不重复(通过旋转)的染色方法数有多少种。

题解:这题完全是看人家的代码看懂的唉…

首先找到树的中心(不是重心),中心的定义是树的直径的中点,如果直径上节点个数是偶数,那么在中间建立一个新的节点。
然后从中心dfs,对于每一棵子树得到相应的hash值(hash方法:hash[i]= A * (hash[j1]*B)^hash[j2]*B.....^hash[jn]*C%D;(顺序执行)),
排序之后同构的子树一定是排列在相邻的位置,这样通过隔板法解x1+x2+……+xans[i] = cnt得到染当前形状子树的方法数,然后得到最后的答案。

下面简单说说取中点dfs的正确性:

定义性质x:以u节点为根节点fa为u的father节点时,任意hash[son]都不等于hash[fa](上方子树的hash值)。

如果取中点dfs那么对于dfs到的所有节点上面的性质都满足,定义longest[i]为以i为根节点到叶子节点的最大距离,l为树的直径。
因为longest[fa](上方子树 && fa != 中心)>=l/2,longest[i]< l/2,所以满足性质x,这样就能保证正确性,不会把同构的子树遗漏掉。

Sure原创,转载请注明出处。

#include <iostream>#include <cstdio>#include <memory.h>#include <algorithm>using namespace std;const int maxn = 50005;const int maxm = 100002;const int leaf = 9778972;const int yin = 10003;const int yy = 131237;const int mod = 1000000007;struct node{    int v;    int next;}edge[maxn << 1];struct H{    __int64 hash,ans;    bool operator < (const H &other) const    {        return hash < other.hash;    }}val[maxn];int head[maxn],down[maxn],longest[maxn];__int64 ans[maxn],hash[maxn],A[maxm];int m,n,bj,idx,root,path;void prepare(){    A[0] = A[1] = 1;    for(int i=2;i<maxm;i++)    {        A[i] = A[i-1] * i;        A[i] %= mod;    }    return;}void init(){    memset(head,-1,sizeof(head));    memset(down,-1,sizeof(down));    idx = path = 0;    bj = root = -1;    return;}void addedge(int u,int v){    edge[idx].v = v;    edge[idx].next = head[u];    head[u] = idx++;    edge[idx].v = u;    edge[idx].next = head[v];    head[v] = idx++;    return;}void read(){    int u,v;    for(int i=1;i<n;i++)    {        scanf("%d %d",&u,&v);        addedge(u,v);    }    return;}__int64 powmi(__int64 a,int x){    __int64 res = 1;    while(x)    {        if(x & 1)        {            res *= a;            res %= mod;        }        a *= a;        a %= mod;        x >>= 1;    }    return res;}__int64 C(__int64 n,int m){    if(n == 1LL * m) return 1LL;    __int64 res = 1;    for(int i=1;i<=m;i++)    {        res *= 1LL * (n - i + 1);        res %= mod;    }    res *= powmi(A[m] , mod-2);    return res % mod;}void DFS(int st,int pre){    int l = 0,ll = 0;    for(int i=head[st];i != -1;i=edge[i].next)    {        if(edge[i].v == pre) continue;        DFS(edge[i].v , st);        if(longest[edge[i].v] > l)        {            ll = l;            l = longest[edge[i].v];            down[st] = i;        }        else if(longest[edge[i].v] > ll) ll = longest[edge[i].v];    }    if(l + ll + 1 > path)    {        path = l + ll + 1;        root = st;    }    longest[st] = l + 1;    return;}void make(){    DFS(1,0);    if(path & 1)    {        while(longest[root] * 2 - 1 > path)        {            root = edge[down[root]].v;        }        ans[root] = 1LL * m;    }    else    {        while(longest[root] * 2 - 2 > path)        {            root = edge[down[root]].v;        }        addedge(root , ++n);        addedge(n , edge[down[root]].v);        bj = down[root];        root = n;        ans[root] = 1LL;    }    return;}void dfs(int st,int pre){    int num = 0;    for(int i=head[st];i != -1;i=edge[i].next)    {        if(edge[i].v == pre) continue;        if(bj != -1 && (i == bj || i == (bj ^ 1))) continue;        num++;        ans[edge[i].v] = 1LL * m;        dfs(edge[i].v , st);    }    if(num == 0)    {        hash[st] = leaf;        return;    }    int c = 0;    for(int i=head[st];i != -1;i=edge[i].next)    {        if(edge[i].v == pre) continue;        if(bj != -1 && (i == bj || i == (bj ^ 1))) continue;        val[c].hash = hash[edge[i].v];        val[c++].ans = ans[edge[i].v];    }    sort(val , val + num);    hash[st] = leaf;    for(int i=0;i<num;)    {        int j = i;        for(;j<num && val[i].hash == val[j].hash;j++)        {            hash[st] *= yin;            hash[st] ^= val[j].hash;            hash[st] %= mod;        }        hash[st] = hash[st] * yy % mod;        ans[st] *= C(val[i].ans + j - i - 1, j - i);        ans[st] %= mod;        i = j;    }    return;}int main(){    prepare();    while(~scanf("%d %d",&n,&m))    {        init();        read();        make();        dfs(root , 0);        printf("%I64d\n",ans[root]);    }    return 0;}


读书人网 >编程

热点推荐