一、題目描述：
給你一顆 $n$ 個點的有根樹 $S$，你需要構造一顆 $n$ 個節點的有根樹 $T$，
使得 $T$ 的 $n$ 顆子樹中不與 $S$ 的任意一顆子樹同構的數量最大。
注意，這里是有根樹，旋轉樹之后的同構不算同構。輸出 $T$ 的所有邊。
數據范圍：$1\le n\le 1\times 10^6$。
二、解題思路：
樹同構，本能地想到樹哈希。而樹哈希推薦 $OI\ Wiki$ 上的寫法，不容易被卡。
容易發現，若一棵子樹不與 $S$ 中的任意一顆子樹同構，那么他的父親子樹也滿足條件。
所以我們只需要找到最小的一顆子樹使得它不與 $S$ 同構，然后往上不斷加鏈就行。
發現這顆最小的子樹一定會很小，因為 $S$ 一共只有 $n$ 顆子樹。
所以我們直接從小到大枚舉子樹就行。設這顆子樹的大小為 $V$，則時間復雜度 $O(n\times V)$ 。
那么這顆子樹最大有多大呢？考慮 $n$ 個點的子樹有多少種不同的形態。
注意到一顆多叉樹唯一對應一顆二叉樹（分左右兒子），而一顆二叉樹也唯一對應一顆多叉樹。
又注意到一顆二叉樹唯一對應一顆完全二叉樹，一顆完全二叉樹唯一對應一顆二叉樹。
所以就是求一顆 $n$ 個節點的完全二叉樹有多少種形態。而這是卡特蘭數經典題。
$Cat_{14}=2674440\ge 1\times 10^6$，所以樹的大小最大為 $14$。時間復雜度 $O(14n)$。
考慮怎么不重不漏的枚舉樹的形態。暴搜枚舉每一個點的父親節點。
但是這樣很明顯會枚舉到很多同構的樹，時間復雜度變為 $14!\times 14$。難以通過本題。
其實只需要做一個小剪枝就可以了，就是枚舉的父親節點順序單調不降。
想一下就想明白了，就像那個什么最小表示法一樣。于是時間復雜度 $O(14n)$。
三、完整代碼：
1 #include<bits/stdc++.h> 2 #define V e[i].v 3 #define N 1000010 4 #define rep(i,l,r) for(int i=l;i<=r;i++) 5 using namespace std; 6 map <int,bool> mp; 7 mt19937 m(time(0)); 8 int n,mask,ha[N],fa[N]; 9 struct EDGE{ 10 int v,nxt; 11 }e[N<<1]; 12 int head[N],cnt; 13 void add(int u,int v){ 14 e[++cnt].v=v; 15 e[cnt].nxt=head[u]; 16 head[u]=cnt; 17 } 18 int shift(int val){ 19 val^=mask; 20 val^=val<<13; 21 val^=val>>7; 22 val^=val<<17; 23 val^=mask; 24 return val; 25 } 26 void dfs(int u,int ff){ 27 ha[u]=1; for(int i=head[u];i!=-1;i=e[i].nxt) 28 if(V!=ff) dfs(V,u),ha[u]+=ha[V]; 29 ha[u]=shift(ha[u]); 30 } 31 void dfs2(int step,int lim,int num){ 32 if(step>num){ 33 rep(i,1,num) head[i]=-1; cnt=0; 34 rep(i,2,num) add(fa[i],i); dfs(1,0); 35 if(!mp[ha[1]]){ 36 int k=n-num; 37 rep(i,1,k) cout<<i<<" "<<i+1<<'\n'; 38 rep(i,2,num) cout<<i+k<<" "<<fa[i]+k<<'\n'; 39 exit(0); 40 } return ; 41 } 42 rep(i,lim,step-1) fa[step]=i,dfs2(step+1,i,num); 43 } 44 int main(){ 45 ios::sync_with_stdio(false); 46 cin.tie(0);cout.tie(0); 47 cin>>n; mask=m(); 48 rep(i,1,n) head[i]=-1; 49 rep(i,1,n-1){ 50 int u,v; cin>>u>>v; 51 add(u,v); add(v,u); 52 } 53 dfs(1,0); rep(i,1,n) mp[ha[i]]=1; 54 rep(i,1,n) dfs2(2,1,i); 55 rep(i,2,n) cout<<i-1<<" "<<i<<'\n'; 56 return 0; 57 }
四、寫題心得：
好，第二次寫樹哈希，收獲經驗如下：
$1、shift\ 還是要多練練，背下來。=> Exp++!$
$2、這個隨機數就很難被卡，以后取模也可以使用隨機模數=> Exp++!$
浙公網安備 33010602011771號