很想许多 agc 那种观察充要条件然后简单计数的题目，然后记录一下我的思考过程。
考虑找一些必要条件。首先每条边操作后，相当于 “独立” 两个部分，于是可以考虑将 \(i \to a_i\) 这条链上的边 \(+1\)，显然每条边的每个方向各被覆盖一次。这显然不充分，因为有 \(a_i=i\) 就错了，于是加一个 \(a_i=i\) 的条件？发现也不充分，于是可以考虑 \(fa_i=(0,1,2,3,2,5),a_i=(2,1,6,3,4,5)\)。
这里有个对于仅加入 \(a_i \not=i\) 的伪证：考虑从叶子出发，找到第一个 \(i\) 往下指的点，将其与儿子交换。但是为什么不对？因为交换 \((u,v)\) 后可能出现 \(a_u=v/a_v=u\)，但是我们发现当 \((a_1,a_2,\cdots,a_n)\) 仅形成一个置换环的时候就不会出现这种情况！而显然，置换环是必要的，所以充要条件就找到了：
- 覆盖 \(2\) 次；
- \((a_1,a_2,\cdots,a_n)\) 组成一个置换环。
于是自低向上计数即可，笔者有点菜所以写了 \(O(n \log n)\)。
const int N=5e5+10;
const int mod=1e9+7;vi e[N];
int n,L[N],R[N];
int tim,df[N],lw[N],Id[N];
int cnt,dfp[N],fr[N],bk[N];void dfspr(int u, int fa) {df[u]=++tim; Id[tim]=u;for(auto v:e[u]) if(v!=fa) dfspr(v,u); lw[u]=tim;
}int ans=1;
void dfs(int u, int fa) {for(auto v:e[u]) if(v!=fa) dfs(v,u);dfp[cnt=1]=df[u];for(auto v:e[u]) if(v!=fa) dfp[++cnt]=df[v];rep(i,1,cnt+1) fr[i]=bk[i]=0;auto get=[&](int x) {if(df[u]<=x&&x<=lw[u])return (int)(upper_bound(dfp+1,dfp+1+cnt,x)-dfp)-1;return cnt+1;};auto add=[&](int x, int y) {
// cout<<u<<" add:: "<<x<<" "<<y<<"\n"; if(bk[x]&&bk[x]!=y) ans=0;if(fr[y]&&fr[y]!=x) ans=0;bk[x]=y;fr[y]=x;return ; };auto chk=[&]() {int cc=0,c=cnt+(fa!=0);rep(i,1,c) {if(!fr[i]) {int u=i;while(u) ++cc,u=bk[u];}}if(cc==0) {int u=bk[1]; ++cc;while(u!=1) ++cc,u=bk[u];}if(cc!=c) ans=0;};
// cout<<u<<" "<<L[u]<<" "<<R[u]<<"\n";if(L[u]) add(get(L[u]),1); if(R[u]) add(1,get(R[u]));for(auto v:e[u]) if(v!=fa) {if(L[v]) add(get(L[v]),get(df[v]));if(R[v]) add(get(df[v]),get(R[v]));}if(!ans) return ;int s=0;rep(i,1,cnt+(fa!=0)) s+=(fr[i]==0);chk();rep(i,1,s-1) ans=1ll*ans*i%mod;if(fr[cnt+1]) R[u]=R[Id[dfp[fr[cnt+1]]]]; else R[u]=0;if(bk[cnt+1]) L[u]=L[Id[dfp[bk[cnt+1]]]]; else L[u]=0;
// cout<<u<<" "<<L[u]<<" "<<R[u]<<" "<<ans<<"\n";
}void Mainsolve() {cin>>n;int u,v;rep(i,1,n-1) cin>>u>>v,e[u].pb(v),e[v].pb(u);dfspr(1,0);rep(i,1,n) cin>>R[i],L[R[i]]=i;rep(i,1,n) L[i]=df[L[i]],R[i]=df[R[i]];dfs(1,0);cout<<ans<<"\n";
}