Prufer序列是一种神奇的东西，其可以实现无根树与序列间的双射，并且在计数题、DP题、找规律题等等问题中有着不俗的表现。
（另，大部分时候，Prufer及其误拼Purfer、Purfur、Prefer等奇奇怪怪的变体是被混用了的）
首先，一棵 \(n\) 个节点的树的Prufer序列，是一长度为 \(n-2\) 的序列。
实现树往Prufer序列的转化，步骤是不断找到当前所有叶子中编号最小的那一个，然后删除该叶子，并将该叶子所连接的节点加入序列。重复此操作，直到树中仅剩两个节点。
然后，实现Prufer序列往树的转化，步骤是顺次遍历Prufer序列，找到当前所有不在之后的Prufer序列里且尚未被选择的点中最小的那一个，并连接该点与当前点。
I.【模板】Prufer 序列
就是模板啦。两个算法都可以用一个指针维护当前所有合法点中最小的那一个，然后每做一次操作后，判断新产生的那个值是否比当前指针还要小，若是则采用新值即可。
时间复杂度均为 \(O(n)\)。
但是，上述算法在知道有关Prufer序列的一些性质后会更加易于实现：
-
一个数在Prufer序列里的出现次数是其度数减一——这可以通过构建序列的算法来看出。同时，因为总度数是 \(2n-2\)，故Prufer序列长度为 \((2n-2)-n=n-2\)。这也可以发现，叶节点并不会在序列中出现。
-
在树转序列的过程中，最终剩余的两个点中一定有一个是 \(n\)——因为无论何时，树中总有至少两个叶子，而 \(n\) 永远不会成为里面较小的一个，故永远不会被删去。
-
在序列转树的过程中，最终剩余两个点中还有一个是 \(n\)。
有了这些性质，算法会非常好写。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll calc(int *a,int n){
ll ret=0;
for(int i=1;i<=n;i++)ret^=1ll*a[i]*i;
return ret;
}
const int N=5e6+3;
int T,n;
namespace TreeToPrufer{
int fa[N],cnt,pru[N],sz[N];
ll func(){
for(int i=1;i<n;i++)scanf("%d",&fa[i]),sz[fa[i]]++,sz[i]++;
for(int i=1;i<n;i++){
while(i<n&&sz[i]!=1)i++;
if(i==n)break;
for(int j=i;sz[j]==1&&j<=i;pru[++cnt]=fa[j],sz[fa[j]]--,j=fa[j]);
}
return calc(pru,n-2);
}
}
namespace PruferToTree{
int pru[N],fa[N],cnt[N];
ll func(){
for(int i=1;i<=n-2;i++)scanf("%d",&pru[i]),cnt[pru[i]]++;
for(int i=1,j=1;j<=n-2;i++){
while(i<=n&&cnt[i])i++;
fa[i]=pru[j],cnt[pru[j]]--,j++;
for(;j<=n-2&&!cnt[pru[j-1]]&&pru[j-1]<i;j++)fa[pru[j-1]]=pru[j],cnt[pru[j]]--;
}
for(int i=1;i<n;i++)if(!fa[i])fa[i]=n;
return calc(fa,n-1);
}
}
int main(){
scanf("%d%d",&n,&T);
if(T==1)printf("%lld\n",TreeToPrufer::func());
else printf("%lld\n",PruferToTree::func());
return 0;
}
II.[HNOI2004]树的计数
可以被证明的是，任意一长度为 \(n-2\)，且所有元素均在 \([1,n]\) 内的序列，均是一合法的Prufer序列。同时，全部上述序列，就是全部合法的Prufer序列。因此，Prufer序列，即点数为 \(n\) 的树的数量，为 \(n^{n-2}\)。
那在这题中，因为我们前面已经发现一度数为 \(i\) 的点的出现次数为 \(i-1\)，而任何一种出现次数的排列均是一合法序列，故总方案数即为一多项式系数 \(\dbinom{n-2}{d_1-1,d_2-1,\dots,d_n-1}\)。
注意本题如果直接套多项式系数会爆炸，但是因为答案在 \(10^{17}\) 以内，故可以设两个模数 \(10^9+7,10^9+9\) 然后求出模意义下的结果然后用CRT并一起。复杂度 \(O(n)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
int inv(int x,int y){
int z=1,t=y-2;
for(;t;t>>=1,x=1ll*x*x%y)if(t&1)z=1ll*z*x%y;
return z;
}
const int m1=1e9+7,m2=1e9+9;
const int iv1=inv(m1,m2);
int n,r1,r2,f1[200],f2[200],i1[200],i2[200],tot;
int main(){
scanf("%d",&n);
f1[0]=f2[0]=1;for(int i=1;i<=n;i++)f1[i]=1ll*f1[i-1]*i%m1,f2[i]=1ll*f2[i-1]*i%m2;
i1[n]=inv(f1[n],m1),i2[n]=inv(f2[n],m2);
for(int i=n-1;i>=0;i--)i1[i]=1ll*i1[i+1]*(i+1)%m1,i2[i]=1ll*i2[i+1]*(i+1)%m2;
r1=f1[n-2],r2=f2[n-2];
for(int i=1,t;i<=n;i++)scanf("%d",&t),tot+=t,r1=1ll*r1*i1[t-1]%m1,r2=1ll*r2*i2[t-1]%m2;
if(tot!=2*n-2){puts("0");return 0;}
if(n==1){puts("1");return 0;}
printf("%lld\n",(1ll*(r2-r1+m2)%m2*iv1%m2*m1+r1)%(1ll*m1*m2));
return 0;
}
III.[清华集训2017]生成树计数
考虑令全体 \(d_i\) 减一，变成Prufer序列中每个块的出现次数。
先不考虑后面一大坨的 \(\sum\)，得到式子 \(\prod a_i\sum\limits_{\{d\}}\dfrac{(n-2)!}{\prod d_i!}\prod a_i^{d_i}(d_i+1)^m\)。
前面是常数可以忽略。中间那个多项式系数的形式一看就知道要用EGF。于是我们设 \(F_i(x)=\sum\dfrac{x^k}{k!}a_i^k(k+1)^m\)。则上式的EGF即为 \(\prod F_i(x)\)。
发现 \(x\) 与 \(a_i\) 有相同的次数。故若我们设 \(F(x)=\sum\dfrac{x^k}{k!}(k+1)^m\)，则 \(F_i(x)=F(a_ix)\)。则上式即为 \((\prod a_i)(n-2)!\Big([x^{n-2}]\prod F(a_ix)\Big)\)。
现在考虑 \(F'(x)=\sum\dfrac{x^k}{k!}w(k+1)\)，其中 \(w(x)\) 是任意关于 \(x\) 的多项式。明显其是 \(F\) 的推广（\(F\) 中的 \(w(x)=x^m\)），且上述关于 \(F\) 的推论仍然成立。
现在考虑让 \(\sum\) 回来，即为式子 \(\prod(d_i+1)^m\sum(d_i+1)^m\)。将 \(\sum\) 移到前面，就会发现其每次是令某个 \(i\) 不贡献 \(d_i^m\) 而变成 \(d_i^{2m}\)。于是我们令 \(w'(x)=x^{2m}\)，就得到了 \(F'(x)=\sum\dfrac{x^k}{k!}w'(k+1)\)。
于是我们要求的式子就是 \(\prod F(a_ix)\sum\dfrac{F'(a_ix)}{F(a_ix)}\)。
现在我们考虑将其拆作两半计算：\(\prod F(a_ix)\) 与 \(\sum\dfrac{F'(a_ix)}{F(a_ix)}\)。先来看前一半。
明显，求 \(\ln\) 后再 \(\exp\) 回去是其常规操作。于是问题变为 \(\sum\limits(\ln F)(a_ix)\) 的求解。
考虑若有个多项式 \(P\)，要求出 \(\sum P(a_ix)\)。若 \(P=\sum\limits p_ix^i\)，则即要求 \(\sum\limits_i\sum\limits_jp_ja_i^jx^j=\sum\limits_{j}\Big(p_j\sum\limits_{i}a_i^j\Big)x^j\)。则若我们对于每个 \(j\) 都算出 \(\sum\limits_{i}a_i^j\)，则将其与 \(p\) 逐位相乘即可。
考虑其生成函数 \(\sum\limits_{i}\sum\limits_{j}a_i^jx^j\)，其等于 \(\sum\limits_i\dfrac1{1-a_ix}\)。通分即得 \(\dfrac{\sum\limits_i\prod\limits_{j\neq i}(1-a_jx)}{\prod1-a_ix}\)。
分母上的式子（设为 \(Q\)）可以用分治+FFT（不是分治FFT）\(O(n\log^2n)\) 求出。分子上式子可以通过展开分子与分母上式子，瞪眼得到为 \(\sum\limits_{k=0}^{n-1}x^k(n-k)[x^k]Q(x)\)，也可以简单求出。故 \(\sum P(a_ix)\) 是可以求的；则 \(\sum\limits(\ln F)(a_ix)\) 亦可简单求；则 \(\prod F(a_ix)\) 求解完毕。
下面来看 \(\sum\dfrac{F'(a_ix)}{F(a_ix)}\) 这个函数。发现，只需要令 \(P=\dfrac{F'}{F}\) 即可如上一样求解。
总复杂度 \(O(n\log^2n)\)。
好久没写多项式题了，板子都要debug好久了，废了废了
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int G=3;
const int N=1<<17;
int ksm(int x,int y=mod-2){int z=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;return z;}
namespace Poly{
int A[N],B[N],rev[N],lim,invlim,C[N],D[N];
void NTT(int *a,int tp){
for(int i=0;i<lim;i++)if(rev[i]>i)swap(a[i],a[rev[i]]);
for(int md=1;md<lim;md<<=1){
int rt=ksm(G,(mod-1)/(md<<1));
if(tp==-1)rt=ksm(rt);
for(int stp=md<<1,pos=0;pos<lim;pos+=stp)for(int i=0,w=1;i<md;i++,w=1ll*w*rt%mod){
int x=a[pos+i],y=1ll*a[pos+md+i]*w%mod;
a[pos+i]=(x+y)%mod;
a[pos+md+i]=(x+mod-y)%mod;
}
}
if(tp==-1)for(int i=0;i<lim;i++)a[i]=1ll*a[i]*invlim%mod;
}
void mul(int*a,int*b,int*c,int LG){
lim=1<<LG,invlim=ksm(lim);
for(int i=0;i<lim;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(LG-1));
for(int i=0;i<lim;i++)A[i]=B[i]=0;
for(int i=0;i<(lim>>1);i++)A[i]=a[i],B[i]=b[i];
NTT(A,1),NTT(B,1);
for(int i=0;i<lim;i++)A[i]=1ll*A[i]*B[i]%mod;
NTT(A,-1);
// for(int i=0;i<(lim>>1);i++)printf("%d ",a[i]);printf("*");
// for(int i=0;i<(lim>>1);i++)printf("%d ",b[i]);printf("=");
for(int i=0;i<lim;i++)c[i]=A[i];
// for(int i=0;i<lim;i++)printf("%d ",c[i]);puts("");
}
void inv(int*a,int*b,int LG){
b[0]=ksm(a[0]);
for(int k=1;k<=LG+1;k++){
mul(b,a,C,k);
for(int i=0;i<(1<<k);i++)C[i]=(mod-C[i])%mod;
(C[0]+=2)%=mod;
mul(C,b,b,k);
}
}
void diff(int*a,int*b,int len){for(int i=0;i<len;i++)b[i]=1ll*a[i+1]*(i+1)%mod;b[len-1]=0;}
void inte(int*a,int*b,int len){for(int i=len-1;i;i--)b[i]=1ll*a[i-1]*ksm(i)%mod;b[0]=0;}
void ln(int*a,int*b,int LG){
inv(a,b,LG);
diff(a,C,1<<LG);
mul(b,C,b,LG+1);
inte(b,b,1<<LG);
}
void exp(int*a,int*b,int LG){
b[0]=1;
for(int k=1;k<=LG+1;k++){
ln(b,D,k-1);
for(int i=0;i<(1<<(k-1));i++)D[i]=(a[i]-D[i]+mod)%mod;
(++D[0])%=mod;
mul(b,D,b,k);
}
}
}using namespace Poly;
int a[N];
int f[N<<1],g[N<<1];
void solve(int l,int LG){
if(!LG){f[2*l]=1,f[2*l+1]=(mod-a[l])%mod;return;}
solve(l,LG-1),solve(l+(1<<(LG-1)),LG-1);
mul(f+2*l,f+2*l+(1<<LG),f+2*l,LG+1);
}
int n,m,LG;
void calc(){
solve(0,LG);
// for(int i=0;i<=n;i++)printf("%d ",f[i]);puts("");
inv(f,g,LG);
for(int i=0;i<=n;i++)f[i]=1ll*f[i]*(n-i)%mod;
mul(f,g,f,LG+1);
// for(int i=0;i<=n;i++)printf("%d ",f[i]);puts("");
}
void clac(int *p){for(int i=0;i<=n;i++)p[i]=1ll*p[i]*f[i]%mod;}
int fac[N],INV[N],p[N],q[N],r[N];
int main(){
scanf("%d%d",&n,&m);
while((1<<LG)<=n)LG++;
for(int i=0;i<n;i++)scanf("%d",&a[i]);
calc();
fac[0]=1;for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
INV[n]=ksm(fac[n]);for(int i=n;i;i--)INV[i-1]=1ll*INV[i]*i%mod;
for(int i=0;i<=n;i++)p[i]=1ll*ksm(i+1,m)*INV[i]%mod;
for(int i=0;i<=n;i++)q[i]=1ll*ksm(i+1,m<<1)*INV[i]%mod;
inv(p,r,LG),mul(q,r,q,LG+1),clac(q);
ln(p,r,LG),clac(r),exp(r,p,LG);
mul(p,q,r,LG+1);
int res=1ll*r[n-2]*fac[n-2]%mod;
for(int i=0;i<n;i++)res=1ll*res*a[i]%mod;
printf("%d\n",res);
return 0;
}