一道比较好的树Hash的题目，提供一种不一样的Hash方法。
首先无根树的同构判断一般的做法只有树Hash，所以不会的同学可以做了Luogu P5043 【模板】树同构（[BJOI2015]树的同构）再来。
首先我们直接考虑一种朴素的想法，暴力求出\(A\)树中以每一个点为根时的Hash值
然后扔到一个set（你要再写个Hash也没事）里，再在\(B\)树中枚举叶子节点，判断去掉这个叶子节点后的Hash值是否在set里即可。
发现这样算法的复杂度瓶颈在求\(A\)树Hash值时的\(O(n^2)\)，那么考虑优化。
由于树Hash的原理就是不要让节点编号去影响Hash值，所以可行的Hash方式不止一种。
那么我们考虑一下用异或+子树大小的方式结合Hash的进制规则来做。
具体的说就是定义Hash值\(H_i=\bigoplus_{j\in son_i}H_j \times seed+size_j\)，其中\(\bigoplus\)表示异或和。
那么我们只要先求出以某个点为根时的Hash值，然后在递推到每一个点为根的情况即可，这个直接用异或的性质异或回去抵消即可。
那么问题解决，复杂度为\(O(n\log n)\)（别忘了set的复杂度），如果用Hash代替的花是\(O(n)\)的。
CODE
#include<cstdio>
#include<cctype>
#include<set>
#define RI register int
#define CI const int&
#define Tp template <typename T>
using namespace std;
typedef unsigned long long ull;
const int N=100005; const ull seed=1e9+7;
int n; set <ull> s;
class FileInputOutput
{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
char Fin[S],*A,*B;
public:
Tp inline void read(T& x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
}
#undef tc
}F;
inline ull updata(CI x,CI y)
{
return x*seed+y;
}
class Tree_Hash_Solver
{
private:
struct edge
{
int to,nxt;
}e[N<<1]; int head[N],cnt,deg[N],size[N],g[N],x,y;
public:
int n,f[N]; //g only in subtree,f include all tree
inline void add(CI x,CI y)
{
e[++cnt]=(edge){y,head[x]}; head[x]=cnt; ++deg[x];
}
inline void init(void)
{
for (RI i=1;i<n;++i) F.read(x),F.read(y),add(x,y),add(y,x);
}
#define to e[i].to
inline void DFS1(CI now,CI fa)
{
size[now]=g[now]=1; for (RI i=head[now];i;i=e[i].nxt)
if (to!=fa) DFS1(to,now),size[now]+=size[to],g[now]^=updata(g[to],size[to]);
}
inline void DFS2(CI now,CI fa)
{
if (!fa) f[now]=g[now]; else f[now]=g[now]^updata(f[fa]^updata(g[now],size[now]),n-size[now]);
for (RI i=head[now];i;i=e[i].nxt) if (to!=fa) DFS2(to,now);
}
#undef to
inline bool isleaf(CI now)
{
return deg[now]==1;
}
inline bool check(CI now)
{
return s.count(f[e[head[now]].to]^updata(g[now],1));
}
}A,B;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (F.read(n),A.n=n,A.init(),A.DFS1(1,0),A.DFS2(1,0),i=1;i<=n;++i) s.insert(A.f[i]);
for (B.n=n+1,B.init(),i=1;i<=B.n;++i) if (!B.isleaf(i)) { B.DFS1(i,0); B.DFS2(i,0); break; }
for (i=1;i<=B.n;++i) if (B.isleaf(i)&&B.check(i)) return printf("%d",i),0; return 0;
}