- 题意：在一棵树上dfs，求前序遍历和后序遍历的最长公共子序列，及其方案数（当然有多种dfs序，每种都有多种公共子序列方案）
- 思路：
我是sb.
1.考场上想的是子段。
2.思维不够灵活，考后做题思考的时候没有从子段转化成子序列。认定了叶子就不会认可其它的可能（还是老毛病了）
3.特判的时候思考不够仔细全面
然后有两种做法第一种是换根dp。
当然还有一种简单的方法
1.找到叶子，往上dfs，点的度数不能超过2。其中一叶子往上找到的叶子暂且定义为叶链。
2.定义公共答案res为每个叶链长度的乘积，再乘上每个点度数减一的阶乘。（阶乘求dfs序方案数,叶链求每个dfs序每个叶链取不同值的方案数）
3.然后du大于2的中间节点为根，输出该点乘上它的du,补全阶乘
4.其余叶链上的节点为根要除去它所在叶链的长度，乘上它为根分割后的新长度。（ps.这里逆元先O(n)先行处理，这道题真的卡常）
！！特判：1.n=1; 2.链（这个简单，但我wa了5次）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
ll mod=998244353,inv[N],g[N],f[N],jc[N],bl[N],sz[N],gp;
int mx,l[N],du[N],nxt[N],to[N],head[N],ecnt;
void add_edge(int u,int v) {nxt[++ecnt]=head[u];to[ecnt]=v;head[u]=ecnt;}
void dfs(int u,int fa) {
bl[u]=gp;
for(int i=head[u];i;i=nxt[i]) {
int v=to[i];
if(v==fa||du[v]>2) continue;
l[v]=l[u]+1;
mx=max(mx,l[v]);
dfs(v,u);
}
}
int main() {
bool flag=0;
int n;
scanf("%d",&n);
if(n==1) {printf("1 1");return 0;}
for(int i=1;i<n;i++) {
int u,v;
scanf("%d%d",&u,&v);
du[u]++,du[v]++;
if(du[u]>2||du[v]>2) flag=1;
add_edge(u,v),add_edge(v,u);
}
ll res=1;
jc[0]=1;
for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;
for(int i=1;i<=n;i++) {
if(du[i]==1&&!l[i]) {
gp++;
mx=l[i]=1;
dfs(i,0);
sz[gp]=mx;
res=res*mx%mod;
}
}
if(!flag) {
for(int i=1;i<=n;i++) {
if(du[i]==1) {
g[i]=1; f[i]=n;
}
else {
g[i]=2; f[i]=1ll*(n-l[i])*(l[i]-1)%mod*2%mod;
}
printf("%lld %lld\n",g[i],f[i]%mod);
}
return 0;
}
inv[1]=1;
for(int i=2;i<=n;i++) {
inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
}
for(int i=1;i<=n;i++) res=res*jc[du[i]-1]%mod;
for(int i=1;i<=n;i++) {
if(!l[i]) f[i]=res*du[i]%mod,g[i]=gp;
else {
g[i]=gp-(du[i]==1);
f[i]=1ll*res*inv[sz[bl[i]]]%mod*max(l[i]-1,1)%mod*du[i]%mod;
}
printf("%lld %lld\n",g[i],f[i]%mod);
}
return 0;
}