PTA 数据结构与算法题目集（中文） 7-3 树的同构 (树哈希)
标签：round const ++ new mes long https col family
题目链接
树哈希直接套就完了
1 #include 2 using namespace std;
3 typedef unsigned long long ll;
4 const int N=1e5+10,M=19260817,inf=0x3f3f3f3f,mod=1e9+7;
5 struct E {int v,nxt;} e[N1];
6 int n,hd[N],ne,a[N],vis[N],rt,ans[2];
7 ll h[N];
8 void link(int u,int v) {e[ne]= {v,hd[u]},hd[u]=ne++;}
9 ll H2(ll x) {x^=x12; x^=x>>7; return x^=x13;}
10 ll H(ll x) {return H2(H2(H2(x)));}
11 void dfs(int u,int f) {
12 h[u]=a[u];
13 for(int i=hd[u]; ~i; i=e[i].nxt) {
14 int v=e[i].v;
15 if(v==f)continue;
16 dfs(v,u);
17 h[u]+=H(h[v]);
18 }
19 }
20 int main() {
21 for(int t=0; t2; ++t) {
22 memset(hd,-1,sizeof hd),ne=0;
23 memset(vis,0,sizeof vis);
24 scanf("%d",&n);
25 for(int u=0; uu) {
26 char c,l,r;
27 scanf(" %c %c %c",&c,&l,&r);
28 a[u]=c;
29 if(l!=‘-‘)l-=‘0‘,link(u,l),link(l,u),vis[l]=1;
30 if(r!=‘-‘)r-=‘0‘,link(u,r),link(r,u),vis[r]=1;
31 }
32 for(int u=0; uif(!vis[u])rt=u;
33 dfs(rt,-1);
34 ans[t]=h[rt];
35 }
36 puts(ans[0]==ans[1]?"Yes":"No");
37 return 0;
38 }
PTA 数据结构与算法题目集（中文） 7-3 树的同构 (树哈希)
标签：round const ++ new mes long https col family
原文地址：https://www.cnblogs.com/asdfsag/p/13371103.html
评论