$Prufer$ 序列

$Prufer$ 序列可以將一棵 $n$ 個點的有編號無根樹 轉化成一個長度為 $n?2$，值域在 $[1,n]$ 的序列。也可以將 任意一個 長度為 $n?2$，值域在 $[1,n]$ 的序列轉化成一棵 有編號無根樹。可以理解成有標號完全圖的生成樹與數列之間的雙射，常用于對樹計數的問題。

對樹建立 $Prufer$ 序列

建立過程：
每次找到編號最小的葉子，往序列末尾加入它所連接的節點編號，然后刪掉這個葉子。重復 $n?2$ 次后只剩下兩個節點結束。

實現方式：
考慮維護指針 $p$ 指向當前最小的葉子編號，每次刪掉 $p$ 后判斷 $p$ 相連的點是否變成了葉子并且編號小于 $p$，如果滿足這兩個條件那么接著刪掉這個點。重復這個過程直到當前葉子相連的點不滿足上述條件，然后令 $p$ 不斷自增直到找到下一個葉子。

正確性說明：

• 每次刪掉一個葉子后最多只會增加一個葉子，并且如果增加了葉子那么一定是當前葉子所連的點。
• 設當前葉子為 $p$，刪掉 $p$ 后新增葉子 $q$。
• 若 $q<p$，那么 $q$ 一定比其它葉子更小，刪 $q$ 是正確的。
• 若 $q>p$，那么后面 $p$ 自增時一定能枚舉到，因此不用管。

這樣指針只會移動 $O(n)$ 次，每個點只會被刪除一次，復雜度 $O(n)$。

代碼：

inline void TP() { // 樹 -> prufer序列for(int i = 1; i < n; i ++ ) deg[fa[i]] ++;int p = 1;for(int i = 1; i <= n - 2; ) {int j = i;while(deg[p]) p ++; pf[j ++] = fa[p]; deg[fa[p]] --;int tp = p;while(j <= n - 2 && !deg[fa[p]] && fa[p] < tp) p = fa[p], pf[j ++] = fa[p], deg[fa[p]] --;i = j; p = ++ tp;}
}

$Prufer$ 序列的性質：

• 構造完 $Prufer$ 序列后原樹會剩下兩個節點，其中一定有一個為 $n$。
• 原樹中的每個點一定在 $Prufer$ 序列中出現 $deg?1$ 次，沒有出現過的就是葉子節點。

從上述建立過程可以看出來：
任意一棵 $n$ 個點有編號無根樹都可以建立出唯一的 $Prufer$ 序列，并且本質不同的樹對應的 $Prufer$ 序列一定不同。
這就完成了 從樹到 $Prufer$ 序列 的單射。

對 $Prufer$ 序列重建樹

建立過程：
對于給定的長為 $n?2$，值域在 $[1,n]$ 的 $prufer$ 序列，我們可以統計每個點的出現次數來求出每個點的度數。考慮每次找到編號最小的葉子來確定與它相連的點，顯然這個相連點應該是當前 $Prufer$ 序列的第一個數。然后把這個葉子刪掉，令相連點的度數減一，然后把 $Prufer$ 序列的第一個數刪掉，重復這個過程 $n?2$ 次。剩下兩個葉子，把它們之間連一條邊即可。

實現方式：
注意到最后剩下的兩個葉子也一定有一個是 $n$，我們將 $Prufer$ 序列的末尾補上一個 $n$，然后重復上述過程 $n?1$ 次就可以連出 $n?1$ 條邊。

與建立 $Prufer$ 序列的過程類似，考慮維護指針 $p$ 表示當前編號最小的葉子，然后每次刪掉葉子后判斷新增葉子 $q$ 是否比 $p$ 小，如果是的話就接著去連 $q$ 的出邊，否則就不斷自增 $p$ 直到找到下一個葉子。可以看作對于當前葉子 $p$， $Prufer$ 序列的開頭就是以 $n$ 為根下 $p$ 的父親節點。

也不難看出 樹 $\to$ 序列 和 序列 $\to$ 樹 的過程是互逆的。一個 $Prufer$ 序列重建的樹對應的 $Prufer$ 序列也一定是這個 $Prufer$ 序列。

復雜度 $O(n)$。

代碼：

inline void PT() { // prufer序列 -> 樹pf[n - 1] = n;for(int i = 1; i <= n - 2; i ++ ) deg[pf[i]] ++;int p = 1;for(int i = 1; i <= n - 1;) {int j = i;while(deg[p]) p ++; fa[p] = pf[j ++], deg[fa[p]] --;int tp = p;while(j <= n - 1 && !deg[fa[p]] && fa[p] < tp) p = fa[p], fa[p] = pf[j ++], deg[fa[p]] --;i = j; p = ++ tp;}
}

由上述重構過程可以看出：
任意一個長度為 $n?2$，值域在 $[1,n]$ 的序列，都能作為一個 $Prufer$ 序列唯一的構造出一棵樹。并且任意兩個不同 $Prufer$ 序列構造的樹都是不同的。

這樣就完成了從 $Prufer$ 序列到樹 的單射。結合上邊，就得到了：

$n$ 個點編號為 $1～n$ 的無根樹與長度為 $n?2$，值域為 $[1,n]$ 的序列雙射。

應用

Cayley 公式

$n$ 個點有編號的完全圖生成樹個數為 $n^{n?2}$。

證明：雙射即可。

[HNOI2004] 樹的計數

題意：
給定 $n$ 個點的度數 $d_1,\dots d_n$，任意兩個點之間可以連邊，問有多少個滿足度數數組的生成樹。

$1\le n\le 150$。

分析：
特判 $n=1$ 的邊界情況。那么任意一個點的度數不能為 $0$，并且所有點的度數和應為 $2n?2$。
一個點只要在 $Prufer$ 序列中出現 $d_i?1$ 即滿足構造出來的樹中度數為 $d_i$。這就是多重集的全排列。

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N = 155;
typedef long long LL;
int n, deg[N], all;
LL res = 1, C[N][N];
int main() {scanf("%d", &n); int all = n - 2;for(int i = 0; i <= n; i ++ ) for(int j = 0; j <= i; j ++ ) if(!j) C[i][j] = 1;else C[i][j] = C[i - 1][j - 1] + C[i - 1][j];for(int i = 1; i <= n; i ++ ) {scanf("%d", &deg[i]);if(deg[i] == 0) {if(n == 1) {puts("1"); return 0;}else {puts("0"); return 0;}}res = res * C[all][deg[i] - 1];all -= deg[i] - 1;}if(all != 0) puts("0");else cout << res << endl;return 0;
}

「雅禮集訓 2017 Day8」共

題意：
給定 $n,k$。 你需要求出有多少個編號為 $1～n$，以 $1$ 為根的無向樹，滿足深度為奇數的點恰好有 $k$ 個。$1$ 的深度認為是 $1$。

$1\le k<n\le 5\times 10^5$。

分析：
顯然可以將點按照深度的奇偶性分成兩類，這將樹變成了一張二分圖。
將 $1$ 劃分到左部點中，那么需要從剩下的 $n?1$ 個編號里選出 $k?1$ 個分到左部點。答案就是 $\left(\genfrac{}{}{0ex}{}{n?1}{k?1}\right)\times S(k,n?k)$。
其中 $S(a,b)$ 表示一張左部點有 $a$ 個，右部點有 $b$ 個的有標號完全二分圖的生成樹個數。
答案是 $a^{b?1}{b}^{a?1}$。
證明：
對于這樣二分圖的生成樹，$Prufer$ 序列構造過程的末尾一定剩下一個左部點和一個右部點。因此它的 $Prufer$ 序列一定有 $b?1$ 個左部點和 $a?1$ 個右部點。
對于這兩部分的構成的子序列內部，如果確定了編號和順序。那么兩部分之間在 $Prufer$ 序列上的順序就定下來了。因此總方案數就是 $a^{b?1}{b}^{a?1}$。

CODE：

// 這種雙射還真是秒啊
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
typedef long long LL;
int n, k, p;
inline LL Pow(LL x, LL y) {LL res = 1, k = x;while(y) {if(y & 1) res = res * k % p;y >>= 1;k = k * k % p;}return res;
}
LL fac[N], inv[N];
int main() {cin >> n >> k >> p;fac[0] = 1; for(int i = 1; i < N; i ++ ) fac[i] = fac[i - 1] * i % p;inv[N - 1] = Pow(fac[N - 1], p - 2); for(int i = N - 2; i >= 0; i -- ) inv[i] = inv[i + 1] * (i + 1) % p;int L = k, R = n - k; LL res = fac[n - 1] * inv[k - 1] % p * inv[n - k] % p * Pow(L, R - 1) % p * Pow(R, L - 1) % p;cout << res << endl;return 0;
}

[THUPC 2018] 城市地鐵規劃

題意：

給定一個 $n,k,mod$，然后給你一個 $k$ 次多項式 $f(x)$ 的每一項系數 $a_0,\dots ,a_k$。對于一個度數為 $d$ 的點，它的貢獻為 $f(d)(\mathrm{mod}mod)$。你可以給編號為 $1～n$ 的點之間任意連邊，求所有生成樹中所有點貢獻和最大的方案，輸出最大貢獻和以及一組構造。

$1\le n\le 3000,0\le k\le 10,mod=59393$。

分析：
首先預處理出 $i\in [1,n]$ 的所有 $w_i=f(i)$。
注意到任意一個 $Prufer$ 序列都能構造出一棵樹，并且在這棵樹上一個點的度數為它在序列中的出現次數加一。因此有一個暴力的 $dp$：
設 $f_{i,j}$ 表示考慮了編號為 $1～i$ 的點， 這些點在 $Prufer$ 序列的出現總次數為 $j$ 的最大代價。轉移枚舉 $i+1$ 的出現次數 $k$ 即可。最后的答案就是 $f_{n,n?2}$。
但是這樣 $dp$ 的復雜度為 $O(n^3)$，考慮優化：
注意到我們不關心每個點的出現次數，只關心 每種出現次數有幾個點。 所以可以以出現次數為階段 $dp$：
設 $f_{i,j}$ 表示考慮了 $1～i$ 這些出現次數，當前總出現次數為 $j$ 的最大代價。
那么轉移是：$f_{i,j}=\underset{k=0}{\overset{?\frac{j}{i}?}{\max }}(f_{i?1,j?i\times k}+k\times w_{i+1})$。

現在轉移復雜度就變成$O(n\ln n)$，總復雜度 $O(n^2\ln n)$。
但是好像有個問題，我們沒有計算度數為 $1$ 的點的貢獻，并且記錄的出現次數也沒辦法體現有多少個點的度數不是 $1$。
肯定不能多加一維來記錄。我們考慮初始令 $f_{0,0}=n\times w_1$，然后每次轉移除了 $+k\times w_i$ 還要 $?k\times w_1$ 表示把這 $k$ 個點的代價換掉。
這樣就對了。構造只需要對每個狀態記錄前驅，然后任意拿一些編號構造 $prufer$ 序列即可。

復雜度 $O(n^2\ln n)$。
CODE：

// prufer 序列與有標號無根樹雙射的好處：任意 prufer 序列都能構造出一棵樹。因此只需要考慮 prufer 序列最優即可
// 對每個點去 dp 它在 prufer 序列出現多少次，復雜度 n^3 優化不了。
// 但是我們只關心每種次數有多少個。 對每個次數 dp 復雜度就降到了 n^2 ln n
#include<bits/stdc++.h>
using namespace std;
const int N = 4010;
const int mod = 59393;
int n, k, a[N];
int val[N], f[N][N], pre[N][N]; // f[i][j] 表示考慮了前 1~i 這些次數， 當前用的總次數為 j 的最優值
int fa[N], prufer[N], tot, p, deg[N];
inline void get_prufer(int x, int y) {if(!x) return ;if(pre[x][y] < y) {for(int i = 1; i <= (y - pre[x][y]) / x; i ++ ) {for(int j = 1; j <= x; j ++ ) prufer[++ tot] = p;p ++;}}get_prufer(x - 1, pre[x][y]);
}
inline void PT() {prufer[n - 1] = n;for(int i = 1; i <= n - 1; i ++ ) deg[prufer[i]] ++;int p = 1;for(int i = 1; i <= n - 1;) {int j = i;while(deg[p]) p ++; fa[p] = prufer[j ++], deg[fa[p]] --;int tp = p;while(j <= n - 1 && !deg[fa[tp]] && fa[tp] < p) tp = fa[tp], fa[tp] = prufer[j ++], deg[fa[tp]] --;i = j; p ++;}
}
int main() {scanf("%d%d", &n, &k);for(int i = 0; i <= k; i ++ ) scanf("%d", &a[i]);for(int i = 0; i <= n; i ++ ) {int v = 1;for(int j = 0; j <= k; j ++ ) {val[i] = (val[i] + v * a[j] % mod) % mod;v = v * i % mod;}}if(n == 1) {printf("0 %d\n", val[0]); return 0;}memset(f, 0xcf, sizeof f); f[0][0] = n * val[1]; // 初始所有度數都是 1for(int i = 1; i <= n - 2; i ++ ) {for(int j = 0; j <= n - 2; j ++ ) {for(int k = 0; k * i <= j; k ++ ) {if(f[i - 1][j - k * i] + k * val[i + 1] - k * val[1] > f[i][j]) {f[i][j] = f[i - 1][j - k * i] + k * val[i + 1] - k * val[1];pre[i][j] = j - k * i;}}}}printf("%d %d\n", n - 1, f[n - 2][n - 2]);p = 1;get_prufer(n - 2, n - 2);PT();for(int i = 1; i < n; i ++ ) printf("%d %d\n", i, fa[i]);return 0;
}

CF156D Clues

題意：
給定一張 $n$ 個點， $m$ 條邊的有標號無向圖，它有 $k$ 個連通塊，求添加 $k?1$ 條邊使得圖聯通的方案數。答案對 $p$ 取模。

$1\le n,m\le 10^5,1\le p\le 10^9$。

分析：
將連通塊縮成一個點，就轉換成了類似完全圖求生成樹的問題。
如果用連通塊的編號來構造 $Prufer$ 序列，那么答案就是 $k^{k?2}$。這顯然不對，原因在于一個連通塊編號實際上代表了 $size$ 個點。
如果對于每一種以連通塊編號構造的 $Prufer$ 序列，我們都把每個連通塊的編號換成任意連通塊內的點的編號。那么這實際上就等于將所有點的編號拿出來構造長為 $k?2$ 的 $Prufer$ 序列，方案數為 $n^{k?2}$。
這對不對呢？很遺憾，它也是不對的。
我們來嘗試理解這樣得到的 $Prufer$ 序列有什么實際含義：相當于每次取出度數為 $0$ 的編號最小的連通塊，然后把這個連通塊和 $Prufer$ 序列開頭編號的連通塊相連，并且根據 $Prufer$ 序列我們知道連向的點的編號就是序列開頭數字。
然后你就能發現問題所在了：我們不知道當前的 “葉子” 連出去的點編號是什么！！
因此開始的時候將答案乘上 $\prod siz{e}_i$ 表示先對每個連通塊欽定一個往外連出去的點的編號，然后再乘上 $n^{k?2}$ 就行。

最后答案就是 $n^{k?2}\prod siz{e}_i$。復雜度線性。

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int n, m, mod, sz[N], bin[N];
int Find(int x) {return x == bin[x] ? x : bin[x] = Find(bin[x]);}
inline void Merge(int u, int v) {int f1 = Find(u), f2 = Find(v);if(f1 != f2) sz[f2] += sz[f1], bin[f1] = f2;
}
inline LL Pow(LL x, LL y) {LL res = 1, k = x;while(y) {if(y & 1) res = res * k % mod;y >>= 1;k = k * k % mod;}return res;
}
int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m >> mod;for(int i = 1; i <= n; i ++ ) bin[i] = i, sz[i] = 1;for(int i = 1; i <= m; i ++ ) {int u, v; cin >> u >> v;Merge(u, v);}LL res = 1; int cnt = 0;for(int i = 1; i <= n; i ++ ) {if(Find(i) == i) res = res * sz[i] % mod, cnt ++;}if(cnt == 1) {cout << (1 % mod) << endl; return 0;}else {		res = res * Pow(n, cnt - 2) % mod;cout << res << endl;}return 0;
}

[ARC106F] Figures

題意：
有 $N$ 個點，每個點有 $d_i$ 個 互不相同、可被區分 的孔，每次可以選擇兩個不同點，連接兩個未被連接過的孔，有多少種方案使得最后形成一棵樹。合法方案中可以不把孔填滿。答案對 $998244353$。

$2\le N\le 2\times 10^5,1\le d_i<998244353$。

分析：
和上道題非常類似，只是一個聯通塊中的一個點只能被連接一次，上一道題是可以連接任意次。
一樣的思考方式，如果我們把所有孔的編號拿出來，有 $M=\sum d_i$ 個孔，用 $A_M^{N?2}$ 來生成 $Prufer$ 序列。
這樣還是不正確的，錯誤原因仍然是每個點作為葉子連出去時沒確定一個孔。
如果最后考慮這個孔是誰，我們還需要知道每個點有多少個孔在 $Prufer$ 序列出現，這不太好。
還是最開始就考慮這個孔是誰，先乘上 $\prod d_i$ 的系數，然后這些孔就不能用了，因此我們用 $A_{M?N}^{N?2}$ 來構建 $Prufer$ 序列。這樣就對了，答案就是 $A_{M?N}^{N?2}\prod d_i$。

復雜度線性。

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
const LL mod = 998244353;
int n, d[N];
LL res = 1;
inline LL A(LL n, LL m) {if(n < m) return 0;LL res = 1;for(LL i = n; i > n - m; i -- ) res = res * (i % mod) % mod;return res;
}
int main() {scanf("%d", &n); LL s = 0;for(int i = 1; i <= n; i ++ ) {scanf("%d", &d[i]); s += d[i] - 1;res = res * d[i] % mod;}res = res * A(s, n - 2) % mod; cout << res << endl;return 0;
}