当前位置：首页 > news >正文

2024.9.23

news 2024/9/24 3:45:33

Prüfer 序列

Prüfer 序列将一个带标号 $n$ 个结点的树用 $[1, n]$ 中的 $n - 2$ 个整数表示。你也可以把它理解为完全图的生成树与数列之间的双射。

是双射的话，也就是一棵树一定对应一个序列，一个序列也只对相应一个树

我们需要重复进行以下操作，直至树中只剩下两个点：

树转序列

找到一个度数为1，且编号最小的点。（其中编号最小保证了后面将会提到的prufer序列的唯一对应性，同时也方便从prufer序列转化回无根树）
把这个点的父亲节点加入序列，然后把这个点从树中删除。

序列转树

取出prufer序列最前面的元素x。
取出在点集中的、且当前不在prufer序列中的最小元素y。（这恰好呼应了前面提到过的选取编号最小的节点）
在x,y之间连接一条边。（注意前面的取出相当于删除）

写了两道计数题

P2290 [HNOI2004] 树的计数

//2024.9.23
//by white_ice
//[HNOI2004] 树的计数 | P2290
#include<bits/stdc++.h>
//#include"../need.cpp"
using namespace std;
#define int long long 
#define itn long long 
constexpr itn oo = 200;
int n,st[oo];
int out = 1,c[oo][oo];
main(void){//fre();cin.tie(0)->sync_with_stdio(0);cin >> n;int sum = 0;if (n==1){cin >> out;cout<<(out?0:1)<<'\n';exit(0);}for (itn i=1;i<=n;i++){cin >> st[i];sum += st[i]-1;if(!st[i]){cout << 0 <<'\n';exit (0);}}if (sum!=n-2){cout << 0 << '\n';exit(0);}for (itn i=0;i<=n;i++)c[i][0] = 1;for (itn i=1;i<=n;i++)for (itn j=1;j<=i;j++)c[i][j] = c[i-1][j-1]+c[i-1][j];for (int i=1;i<=n;i++) out*=c[sum][st[i]-1],sum-=st[i]-1;cout << out << '\n' << flush;exit (0);
}

是一道Purfer序列的板题

P3255 [JLOI2013] 地形生成

//2024.9.22
//by white_ice
//[JLOI2013] 地形生成 | P3255
#include<bits/stdc++.h>
// #include"../need.cpp"
using namespace std;
constexpr int mod = 2011;
constexpr int oo = 1003;
int n,out1 = 1,out2 = 1;int f[oo];
struct nod{int h,d;
bool operator <(const nod& b)const{if(h==b.h)return d<b.d;return h>b.h;}
}st[oo];
main(void){// fre();cin.tie(0)->sync_with_stdio(0);cin >> n;for(int i=1;i<=n;i++)cin >> st[i].h >> st[i].d;sort(st+1,st+n+1);int num=0;for(int i=1;i<=n;i++){if(st[i].h!=st[num].h)num=i;(out1*=min(num,st[i].d)+i-num)%=mod;}cout << out1 << ' ';int pos;for(int i=1;i<=n;i++){pos=i;while(st[pos].h==st[i].h && pos<=n)pos++;pos--;memset(f,0,sizeof(f));f[0]=1;for(int j=i;j<=pos;j++)for(int k=1;k<=min(st[j].d,i)-1;k++)(f[k]=f[k-1]+f[k])%=mod;int sum=0;for(int j=0;j<=min(st[pos].d,i)-1;j++)(sum += f[j])%=mod;(out2*=sum)%=mod; i=pos;}cout << out2 << '\n' << flush;exit(0);
}