题目大意
有一棵树a，树b是在a的基础上多加一个叶子，且打乱了编号顺序，现在要求b上多出的那个节点是哪个（可能有多个）
暴力
枚举一个节点作为根节点，然后用各种奇怪的依据（例如儿子个数，节点度数，最大子树大小等）来匹配，逐个逐个下去找，大概时间复杂度O(有点玄学)
正解
树的hash
因为是匹配，所以我们可以想到hash，那么对于树的hash我们可以怎样做呢？
很直观的可以用最小表示法，例如求一棵子树的hash，设树根为x，其儿子为a[1..n]，以i节点为根的子树的hash值为v[i]，那么将其儿子的hash值从小到大排序，弄个素数hash一下，注意最好加上一个依据，不然可能挂掉，时间复杂度是O(n log n)
思路
对于a的每个节点，求出其子树hash值，然后求出作为树根的hash值和其向父亲方向的树的hash值，将每个点作为树根的hash值扔进一个set里，枚举b的一个叶子，用类似的方法求出删掉它之后的树的hash值
code
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<set>#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)using namespace std;typedef long long LL;const int N = 100010;
const int mo = 1e+9+9;
const int pri = 12589;LL tim[N],q[N];
int k;
struct node{int x;LL v;
}u[N];
bool cmp(node x,node y){return x.v<y.v;
}struct tree{struct edge{int x,next;}e[N*2];int tot,n;int h[N],r[N],fa[N],s[N];LL v[N],rt[N],f[N];LL suf[N],pre[N];void inse(int x,int y){e[++tot].x=y;e[tot].next=h[x];h[x]=tot;}void init(){tot=0;fo(i,1,n)h[i]=r[i]=v[i]=f[i]=fa[i]=rt[i]=0;fo(i,1,n-1){int x,y;scanf("%d%d",&x,&y);inse(x,y);inse(y,x);r[x]++;r[y]++;}}void dfs1(int x){s[x]=1;for(int p=h[x];p;p=e[p].next)if (e[p].x!=fa[x]){fa[e[p].x]=x;dfs1(e[p].x);s[x]+=s[e[p].x];}k=0;for(int p=h[x];p;p=e[p].next)if (fa[e[p].x]==x)q[++k]=v[e[p].x];sort(q+1,q+1+k);v[x]=0;fo(i,1,k)v[x]=(v[x]*pri%mo+q[i])%mo;v[x]=(v[x]*pri%mo+s[x])%mo;}void dfs2(int x){k=0;if (x>1)u[++k].v=f[x],u[k].x=fa[x];for(int p=h[x];p;p=e[p].next)if (fa[e[p].x]==x){u[++k].x=e[p].x;u[k].v=v[e[p].x];}std::sort(u+1,u+1+k,cmp);fo(i,1,k)pre[i]=(pre[i-1]*pri%mo+u[i].v)%mo;suf[k+1]=0;fd(i,k,1)suf[i]=(suf[i+1]+u[i].v*tim[k-i]%mo)%mo;fo(i,1,k)if (u[i].x!=fa[x]){f[u[i].x]=(pre[i-1]*tim[k-i]%mo+suf[i+1])%mo;f[u[i].x]=(f[u[i].x]*pri%mo+n-s[u[i].x])%mo;}for(int p=h[x];p;p=e[p].next)if (fa[e[p].x]==x)dfs2(e[p].x);}void calc(){dfs1(1);dfs2(1);fo(i,1,n){k=0;for(int p=h[i];p;p=e[p].next)if (fa[e[p].x]==i)q[++k]=v[e[p].x];if (fa[i])q[++k]=f[i];sort(q+1,q+1+k);rt[i]=0;fo(j,1,k)rt[i]=(rt[i]*pri%mo+q[j])%mo;rt[i]=(rt[i]*pri%mo+n)%mo;}}
}a,b;
set<LL> s;
int m;int main(){freopen("leaf.in","r",stdin);freopen("leaf.out","w",stdout);tim[0]=1;s.clear();scanf("%d",&m);fo(i,1,m+2)tim[i]=tim[i-1]*pri%mo;a.n=m;a.init();b.n=m+1;b.init();a.calc();b.calc();fo(i,1,m)s.insert(a.rt[i]);fo(i,1,m+1)if (b.r[i]==1&&((i!=1&&s.find(b.f[i])!=s.end())||(i==1&&s.find(b.v[b.e[b.h[i]].x])!=s.end()))){printf("%d\n",i);break;}fclose(stdin);fclose(stdout);return 0;
}一开始用的模数太小挂掉了啊！！！