最长公共子序列

问题描述：

对一棵有根树执行一次DFS，可以得到一个前序遍历和一个后序遍历，
设它们的最长公共子序列长度和方案数分别是 f,g 。
DFS时可以任意调整子树顺序，不同顺序的DFS会得到不同的前序和后序遍历。
设最长公共子序列长度的最大值是 F ，方案总数是 G 。
即 F=max所有DFS顺序(f) ， G=∑所有DFS顺序(g) 。

给你一棵无根树，请你求出将每个节点 u 被设为根时的 Fu,Gu 。 Gu 可能很大所以 mod 998244353 。

对于 100% 的数据， n≤500000 。

 分析:

　　可以树形dp+换根，但kzsn没写对，只写了40分。

　　以下为大佬qfxl的分析，已得到qfxl的许可，于是，kzsn小菜鸡，便不用写了！

　　对于以 x 为根的树（如下图，其中 a , b , c 代表以其为根的子树）

　　ta的前序遍历是： x , a , b , c ；后序遍历是： a , b , c , x 。

　　我们可以得出结论：一棵有根树的最长公共子序列长度为其叶子节点个数。

　　那么，F 就解决了，只需要求出叶子节点个数，再记一下它是不是叶子。

　　然后来讨论 G ：

　　　　对于上图，不难发现：对于一个红圈而言，任选一个点并不会影响答案，将它命名为“叶链”，即从叶子开始，到第一个度数为3的点之前为止；

　　　　对一个非叶链上的点 a ，其答案为：∏（In [ x ] - 1 ) !  ∏ ( Size [ y ] ) * In [ a ] （其中，x为非叶链上点，y为叶链上点，In [ ] 为度数，Size [ ] 为叶链大小）；

　　　　对一个叶链上的点 a ，其答案为：∏（In [ x ] - 1 ) !  ∏ ( Size [ y ] ) * Len [ a ] / Size [ a ] * In [ a ] （其中，x为非叶链上点，y为叶链上点，In [ ] 为度数，Len [ ] 为点到叶子距离，Size [ ] 为叶链大小）；

　　　　由于前面有大量重复项，可以把  ∏（In [ x ] - 1 ) !  ∏ ( Size [ y ] )  提出来计算。

　　但要注意，n == 1 和 图为一条链 的情况要特判一下

#include
using namespace std;
#define re register int
#define LL long long
static char buf[1<<20], *p1=buf, *p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<20, stdin), p1==p2)?EOF:*p1++
inline int read()
{
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while('0'<=c&&c<='9')x=x*10+c-48,c=getchar();
    return x;
}
const int N=7e5+5, mo=998244353;
inline LL inv(LL x)
{
    int y=mo-2;
    x=x%mo;
    LL ret=1;
    while(y)
    {
        if(y&1) ret=ret*x%mo;
        x=x*x%mo;
        y>>=1;
    }
    return ret;
}
vector<int>G[N];
int root, n;
LL sum=1, fac[N];

int vis[N], in[N], com[N], bel[N], edge;
void dfs(int x, int y)
{
    vis[x]++;
    bel[x]=y;
    com[y]=vis[x];
    int flag=0;
    for(re v:G[x])
    if(!vis[v]&&in[v]==2)
    {
        flag=1;
        vis[v]=vis[x];
        dfs(v, y);
    }
    if(!flag)sum=1ll*sum*com[y]%mo;
}

LL f[N], g[N];
void DD(int x, int fa, int cnt)
{
    if(in[x]==1)f[x]=1, g[x]=n;
    else f[x]=2, g[x]=2ll*cnt*(n-cnt-1)%mo;
    for(re v:G[x])if(v!=fa)DD(v, x, cnt+1);
}
int main()
{
    n=read();
    fac[0]=1;for(re i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mo;
    
    int judge=0;
    for(re i=1;ii)
    {
        int x=read(), y=read();
        G[x].push_back(y);
        G[y].push_back(x);
        in[x]++;
        in[y]++;
        judge=max(judge, max(in[x], in[y]));
    }
    
    if(n==1)return puts("1 1"),0;
    if(judge<=2)
    {
        for(re i=1;i<=n;++i)if(in[i]==1){DD(i, 0, 0);break;}
        for(re i=1;i<=n;++i)
        printf("%lld %lld\n", f[i], g[i]);
        return 0;        
    }
    
    for(re i=1;i<=n;++i)if(in[i]==1)dfs(i,++edge),root++;
    for(re i=1;i<=n;++i)if(!vis[i])sum=sum*fac[in[i]-1]%mo;
    
    for(re i=1;i<=n;++i)
    {
        int A1=0;
        LL A2=1;
        if(!vis[i])
        {
            A1=root;
            A2=sum*in[i] % mo;
        }
        else
        {
            A1=root-(vis[i]==1);
            A2=1ll * sum * inv(com[bel[i]]) % mo * max(1, vis[i]-1) % mo * in[i] % mo;
        }
        printf("%d %lld\n", A1, A2);
    }
    return 0;
}