树哈希直接套就完了
1 #include<bits/stdc++.h> 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[N<<1]; 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^=x<<12; x^=x>>7; return x^=x<<13;} 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; t<2; ++t) { 22 memset(hd,-1,sizeof hd),ne=0; 23 memset(vis,0,sizeof vis); 24 scanf("%d",&n); 25 for(int u=0; u<n; ++u) { 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; u<n; ++u)if(!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 }