[AIZU2784]Similarity of Subtrees(树Hash)

发布于 2018-05-24  75 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[AIZU2784]Similarity of Subtrees(树Hash)

Description

Define the depth of a node in a rooted tree by applying the following rules recursively:

    The depth of a root node is 0.
    The depths of child nodes whose parents are with depth d are d+1

Let S(T,d) be the number of nodes of T with depth d. Two rooted trees T and T′ are similar if and only if S(T,d) equals S(T′,d) for all non-negative integer d
You are given a rooted tree Twith N nodes. The nodes of T are numbered from 1 to N. Node 1 is the root node of T. Let Ti be the rooted subtree of T whose root is node i. Your task is to write a program which calculates the number of pairs (i,j) such that Ti and Tj are similar and i<j.

Tag

树Hash

题目大意

给出一棵有根树,定义两棵树是同构的当且仅当每一层的节点数都相同,求同构的子树对数。

解决思路

根据题目对同构的树的定义,可以得到合适树$$Hash$$的函数,即对于$$u$$的儿子$$v$$,有
\[Hash[u]=\sum Hash[v]*base\]
求完$$hash$$之后,排一边序,找出相同的,统计答案。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

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

const int maxN=101000;
const int maxM=maxN*2;
const ull base=20729;
const int inf=2147483647;

int n;
int edgecnt=0,Head[maxN],Next[maxM],V[maxM];
ull W[maxN];

void dfs(int u);

int main()
{
    mem(Head,-1);
    scanf("%d",&n);
    for (int i=1;i<n;i++)
    {
        int a,b;scanf("%d%d",&a,&b);
        edgecnt++;Next[edgecnt]=Head[a];Head[a]=edgecnt;V[edgecnt]=b;
    }
    dfs(1);
    sort(&W[1],&W[n+1]);
    ll Ans=0;
    W[++n]=inf;
    for (int i=1,j=0;i<=n;i++) if (W[i]!=W[j]) Ans=Ans+1ll*(ll)(i-1-j+1)*(ll)(i-1-j)/2,j=i;
    printf("%lld\n",Ans);
    return 0;
}

void dfs(int u)
{
    W[u]=1;
    for (int i=Head[u];i!=-1;i=Next[i])
    {
        dfs(V[i]);
        W[u]=W[u]+W[V[i]]*base;
    }
    return;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[AIZU2784]Similarity of Subtrees(树Hash)


HNCJ OIer 一枚