https://www.lydsy.com/JudgeOnline/problem.php?id=4754
https://www.luogu.org/problemnew/show/P4323
JYY有两棵树A和B：树A有N个点，编号为1到N；树B有N+1个点，编号为1到N+1。JYY知道树B恰好是由树A加上一个叶节点，然后将节点的编号打乱后得到的。他想知道，这个多余的叶子到底是树B中的哪一个叶节点呢？
树同构问题基本都是树哈希做的。
参考+copycat：https://www.cnblogs.com/RabbitHu/p/9165770.html
这题也没啥方便的写法了，代码写起来有股重工业的气息，所以本题题解也就是归纳思路，拾人牙慧了。
有一个很简单的方法找到这个结点：枚举B的每个叶子，求这个树删掉这个叶子的哈希值，再与A所有哈希值匹配，如果匹配成功的话就说明这个叶子是合法解，复杂度O(nlogn)
但是很不幸，利用BZOJ4337：[BJOI2015]树的同构的方法求每个根的哈希值的话是O(n^2)的，所以我们需要将其优化到O(nlogn)
（注意，为了方便后期修改值，令f[u]表示u子树的哈希值，f[u]=size[u]*π(f[v]*B^k)和我原本做法不同还请注意。）
第一遍求以1为根的哈希显然不能变，关键就是动态换根了。
画一下图的话就能发现当根节点从fa[u]转到u的时候，只有f[u]和f[fa[u]]发生了变化，设g[u]=此时的f[fa[u]]。
可知g[u]就是f[fa[u]]加了一棵以fa[fa[u]]为根的子树，减了一棵以u为根的子树后的哈希值，我们大可以将所有的子树预处理出来，维护前缀乘积和后缀乘积，然后根据u的不同删掉子树id，则答案为前缀[id-1]*B^k+后缀[id+1]（k的值请读者自行讨论）。
这样我们二分查找id，复杂度变成了O(nlogn)可以通过本题。
#include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<cctype> #include<vector> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef unsigned long long ll; const int N=1e5+5; const ll B=666623333; inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } struct node{ int to,nxt; }e[N*2]; int n,cnt,head[N],sz[N],fa[N],ind[N]; ll f[N],g[N],qpow[N]; vector<ll>num[N],nl[N],nr[N]; set<ll>vis; inline void add(int u,int v){ e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt; } ll dfs1(int u){ f[u]=0;sz[u]=1; num[u].clear(); for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(v==fa[u])continue; fa[v]=u;num[u].push_back(dfs1(v));sz[u]+=sz[v]; } if(num[u].empty())return f[u]=1; sort(num[u].begin(),num[u].end()); for(int i=0;i<num[u].size();i++)f[u]=f[u]*B+num[u][i]; return f[u]*=sz[u]; } int ans; void dfs2(int u,int p){ if(fa[u]){ num[u].push_back(g[u]); sort(num[u].begin(),num[u].end()); } int numsz=num[u].size(); nl[u].resize(numsz),nr[u].resize(numsz); nl[u][0]=num[u][0];nr[u][numsz-1]=num[u][numsz-1]; for(int i=1;i<numsz;i++)nl[u][i]=nl[u][i-1]*B+num[u][i]; for(int i=numsz-2;i>=0;i--)nr[u][i]=nr[u][i+1]+num[u][i]*qpow[numsz-i-1]; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(v==fa[u])continue; if(numsz==1){g[v]=1;dfs2(v,p);break;} int id=lower_bound(num[u].begin(),num[u].end(),f[v])-num[u].begin(); g[v]=0; if(id+1<numsz)g[v]=nr[u][id+1]; if(id-1>=0)g[v]+=nl[u][id-1]*qpow[numsz-id-1]; g[v]*=(n-sz[v]); if(p&&ind[v]==1&&vis.find(g[v])!=vis.end())ans=min(ans,v); dfs2(v,p); } if(!p)vis.insert(nl[u][numsz-1]*n); } int main(){ n=read(); qpow[0]=1; for(int i=1;i<=n;i++)qpow[i]=qpow[i-1]*B; for(int i=1;i<n;i++){ int u=read(),v=read(); add(u,v);add(v,u); } dfs1(1);dfs2(1,0); cnt=0;memset(head,0,sizeof(head));n++; for(int i=1;i<n;i++){ int u=read(),v=read(); add(u,v);add(v,u);ind[u]++;ind[v]++; } dfs1(1); ans=N; if(ind[1]==1&&vis.find(f[e[head[1]].to])!=vis.end())ans=1; dfs2(1,1); printf("%d ",ans); return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++