作法：
以起點當根轉換為有根樹，記起點為 st ，終點為 ed ，並且起點沿最短路走到終點的路徑為 x_0 = st -> x_1 -> ... -> x_r = ed 。所以我們的走法是：一開始在 x_0 時，必須要先把 x_0 的不包含 x_1 所在子樹的整個子樹都走一遍，最後停在 x_0 的某個非 x_1 的子節點 ( 若 x_0 沒有 x_1 以外的子節點則會停在 x_0 )，然後再進入 x_1 的子樹，先不走 x_2 所在的子樹，就這樣一直重複下去，最後到了 x_r 時則是變成先走完所有 x_r 的子孫，最後再停在 x_r。
由上述第一步的「先把 x_0 的不包含 x_1 所在子樹的整個子樹都走一遍，最後停在 x_0 的某個非 x_1 的子節點」，可以得到我們需要考慮這樣的一個子問題：現在在一個子樹的根 u ，是否有辦法走遍這個子樹，最後停在 u 的其中一個子節點。( 註：所以我先把連接 x_i 和 x_( i + 1 ) 的邊拔掉，這樣就可以讓DFS下去的子問題是正確的。 )
對於這個子問題，首先如果 u 有子節點是葉子的話，那可以先不理他，可以最後再一次把他們走完，所以只需要關心度 > 1 的子節點們。而我們可以先對每個節點的子節點按照其 degree 由大到小排序，這樣之後就會比較方便。如果 u 的度 > 1 的子節點數目 > 1 的話，可以發現這樣一定沒辦法達成目標，所以他至多有一個度 > 1 的子節點。如果沒有的話那就全部都是葉子，輕鬆把它處理完。如果有的話，設他叫作 v 好了，那麼這時候 u 踏出去的第一步一定是走到 v 的其中一個子節點，然後把 v 的子樹全部走完，最後停在 v 。
所以這樣就產生了第二種子問題：要從某一個子樹 u 的子節點開始走，走遍這棵子樹，最後停在 u 。一樣可以先不管 u 的葉子子節點，那麼類似的可以發現，如果 u 的度 > 1 的子節點數目 > 1 的話一樣沒辦法達成目標。沒有的話一樣很簡單，有的話就會再次把問題轉換為第一個子問題的情形。
但事實上還有一種情況要考慮，例如 x_0 只有 x_1 一個子節點時，這時候 x_1 可以變成從他的其中一個子節點開始走，但最後不一定要停留在 x_1 ，可以停留在 x_1 的另一個子節點，這樣也可以在走完 x_1 的子樹時下一步踏入 x_2 的領域。所以我們又多了另一個子問題( 或不如說是上述第二個子問題的要求較不嚴苛的版本 )，也就是允許最後停留的點是當前根節點的子節點。又因為多考慮了這件事，所以當走完 x_i 的子樹時我們必須還要知道目前到底是停在 x_i 還是 x_i 的其中一個子節點，這會影響到進入 x_( i + 1 ) 的子樹時的形式，所以必須在解決完一個子問題之後回傳最後是停在根還是停在根的某個子節點。
而關於第三個子問題的討論就比較麻煩了，大致上是如果 u 的度 > 1 的子節點數目 > 2 的話就沒辦法達成目標，沒有的話一樣簡單，如果有一個的話，也把他叫 v 好了，我們先試試看這棵子樹有沒有辦法從某個 u 的子節點開始把他全部走完，然後停在 u ，測試方法根前面第二個子問題一樣。如果沒辦法的話，就改成先踏上 u ，然後去試有沒有辦法從 v 的某個子節點開始走，走遍 v 的子樹，最後停在 v ，這樣就等於停在 u 的其中一個子節點了。
如果 u 的度 > 1 的子節點數目 = 2 ，把他們叫作 s1 和 s2 好了，那麼這時的走法就變成：先走到 s1 ，然後走遍 s1 的子樹，最後停在 s1 的某個子節點，然後走到 u ，再從 s2 的某個子節點開始走，最後停在 s2 。或是 s1 和 s2 可以交換地位。如果這兩種都不行就代表不存在要求的路徑。
最後，我在實作上還有先把每個點連往他父節點的(有向)邊都拔掉，不然每次還要判是不是父親很麻煩。這題真是蠻恐怖的討論題阿......各種好麻煩的東西QQ
code :
#include<bits/stdc++.h> using namespace std; const int maxn=500000+10 ; vector<int> v[maxn] ; int fa[maxn],nex[maxn] ; void del(int x,int y) { for(int i=0;i<v[x].size();i++) if(v[x][i]==y) { for(int j=i;j+1<v[x].size();j++) v[x][j]=v[x][j+1] ; v[x].resize((int)v[x].size()-1) ; break ; } } void dfs0(int x) { for(int i=0;i<v[x].size();i++) if(v[x][i]!=fa[x]) fa[v[x][i]]=x , dfs0(v[x][i]) ; } bool cmp(int a,int b){ return v[a].size()>v[b].size() ; } int cnt=0 , ans[maxn] ; int solve1(int x) ; int solve2(int x,int type) { if(v[v[x][0]].empty()) { for(int i=0;i<v[x].size();i++) ans[cnt++]=v[x][i] ; ans[cnt++]=x ; return 1 ; } int num=0 ; while(num<v[x].size() && !v[v[x][num]].empty()) num++ ; if(num>2) return 0 ; if(type==0) { if(num>1) return 0 ; for(int i=1;i<v[x].size();i++) ans[cnt++]=v[x][i] ; if(!solve1(v[x][0])) return 0 ; ans[cnt++]=x ; return 1 ; } if(num==1) { int tmp=cnt ; for(int i=1;i<v[x].size();i++) ans[cnt++]=v[x][i] ; if(!solve1(v[x][0])) { cnt=tmp ; ans[cnt++]=x ; if(!solve2(v[x][0],0)) return 0 ; for(int i=1;i<v[x].size();i++) ans[cnt++]=v[x][i] ; return 2 ; } else { ans[cnt++]=x ; return 1 ; } } else for(int i=0;i<2;i++) { int s1=v[x][i] , s2=v[x][(i+1)%2] ; int tmp=cnt ; for(int j=2;j<v[x].size();j++) ans[cnt++]=v[x][j] ; if(solve1(s1)) { ans[cnt++]=x ; if(solve2(s2,0)) return 2 ; } cnt=tmp ; } return 0 ; } int solve1(int x) { if(v[x].size()>=2 && !v[v[x][0]].empty() && !v[v[x][1]].empty()) return 0 ; ans[cnt++]=x ; if(v[x].empty()) return 1 ; if(!v[v[x][0]].empty()) { if(!solve2(v[x][0],0)) return 0 ; for(int i=1;i<v[x].size();i++) ans[cnt++]=v[x][i] ; } else for(int i=0;i<v[x].size();i++) ans[cnt++]=v[x][i] ; return 2 ; } main() { int n ; scanf("%d",&n) ; for(int i=1;i<n;i++) { int x,y ; scanf("%d%d",&x,&y) ; v[x].push_back(y) ; v[y].push_back(x) ; } fa[1]=1 ; dfs0(1) ; for(int x=n;x!=1;x=fa[x]) nex[fa[x]]=x , del(fa[x],x) ; for(int x=2;x<=n;x++) del(x,fa[x]) ; for(int i=1;i<=n;i++) sort(v[i].begin(),v[i].end(),cmp) ; int last=2 ; for(int i=1;i!=n;i=nex[i]) { if(last==1 && !v[i].empty()) last=solve2(i,1) ; else last=solve1(i) ; if(!last) { printf("BRAK\n") ; return 0 ; } } if(!v[n].empty() && last==2) { printf("BRAK\n") ; return 0 ; } if(v[n].empty()) ans[cnt++]=n ; else if(!solve2(n,0)) { printf("BRAK\n") ; return 0 ; } for(int i=0;i<n;i++) printf("%d\n",ans[i]) ; }
沒有留言:
張貼留言