[CF 468D] Tree

作法：

首先先觀察最佳解的排列會滿足什麼特性。現在等於是樹上有$n$條路徑，分別是$i$走到$p[i]$。如果兩條路徑$(i,p[i])$和$(j,p[j])$沒有公共點的話，那麼把$p[i],p[j]$交換會讓答案更大，因此就可以得到在最佳解時任兩條路徑都有公共點。接下來證明若在一棵樹上有很多條路徑，並且任兩條路徑都有公共點，那麼所有路徑有一個公共點。記這些路徑為$P_1,...,P_k$，考慮$P_1$和其他路徑的交集部份，他們都是由$P_1$上的某一段連續的點組成的（所以可以看成一個區間），並且易證明任兩個區間都有交集，否則原圖中會出現圈，矛盾。那麼這個命題就變得顯然了，因為這樣的$n$個區間必定會有一個公共點。

再來我們想知道有哪些點有資格被當作所有路徑都經過的點。對於某個點$P$來說，考慮$P$的最大的子樹，如果這棵子樹的大小$>\left \lfloor \frac{n}{2} \right \rfloor$，那麼顯然$P$不能被當作剛才所說的公共點，因為在那棵子樹裡的點都必須連向不在那棵子樹裡的點，但那棵子樹裡的點太多了，所以矛盾。因此我們得到了公共點必須滿足「把他拔掉後剩下的所有子樹大小都$\leq \left \lfloor \frac{n}{2} \right \rfloor$」。並且不難證明這是充要條件，任意構造一個就可以了，在這裡省略。有了這個條件後就不難想到取重心應該是對的，而事實上也只有重心會滿足這個條件，證明就補在這篇的最後面。

因此就可以得到第一個答案是所有點到重心的距離和的兩倍，麻煩的是要求出字典序最小的解。首先以重心為根建成有根樹，我們把題目轉成二分圖完美匹配來看，對於$i$指向$p[i]$，可以把他看成「$i$的出點」連向了「$p[i]$的入點」，所以如果把每個點都拆成出點和入點，並且若$i,j$在不同的重心的子樹裡，那麼在$i$的出點和$j$的入點之間連一條邊，這樣就變成了求這張圖的字典序最小的完美匹配了。首先考慮這樣的算法：當要決定$p[i]$為多少時，就從$1$開始往上枚舉，找出第一個「$i$的出點連了他的入點之後整張圖還存在完美匹配」的點，並且他還沒被別人選過，那麼$p[i]$就等於他。但問題是要知道存在完美匹配的條件，才能從剩餘的候選人裡選出值最小的拿來當$p[i]$。記重心的所有子樹們為$T_1,...,T_r$，對於某個瞬間來說，假設$T_i$的出點數量為$a_i$，入點數量則為$b_i$（因此在一開始$a_i=b_i=T_i$的大小），那麼可以列出一條蠻顯然的式子：$a_i\leq b_1+...+b_{i-1}+b_{i+1}+...+b_r$，因為$T_i$中的剩下的出點必須去找$T_i$以外的子樹的入點來連，所以顯然個數要比候選人少。而由 Hall 定理（二分圖存在完美匹配的充要條件）可以得到這件事就是充要條件了。將上式改寫成$a_i+b_i\leq b_1+...+b_r$，並且易知$b_1+...+b_r$等於還沒匹配的點的對數，也就是我們得到了在任一瞬間，對於所有的$i$都必須滿足$a_i+b_i\leq$還沒匹配的點的對數。因此就得到了這樣的算法：當要計算$p[i]$時，先看看有沒有哪棵子樹的$a+b$的值已經等於還沒匹配的點的對數了（這裡還沒匹配的點的對數其實就等於$n-i+1$），如果有的話那麼$p[i]$就必須要從那棵子樹裡取，那麼就取那棵子樹中值最小的點即可。如果沒有這樣的子樹的話，就可以取$i$所在的子樹以外的所有點，因此也取這些點中的最小的點即可。實作上可以對每棵子樹紀錄一個 set ，代表還有哪些入點還沒用，還有一個 set 裡面放了每棵子樹的入點的最小值，根一個 set<pair<int,int>> ，其中 pair 的第一個值為某棵子樹的$a+b$值，第二個則為這是第幾棵子樹，維護好這些東西就好了。另外還要特判根，也就是要記得判$i$是根的情形，還有有可能取的$p[i]$是根的情形。

最後，以下證明前面提到的「一個點是重心若且唯若可以被當作公共點」。

設$P$為重心，若$P$不可被當作公共點，設$T_1$是$P$的大小$> \left \lfloor \frac{n}{2} \right \rfloor$的子樹，其根為$Q$，那麼把$Q$拔掉的話，包含$P$的那棵子樹的大小就會$<n-\left \lfloor \frac{n}{2} \right \rfloor=\left \lceil \frac{n}{2} \right \rceil$$\leq  \left \lfloor \frac{n}{2} \right \rfloor+1\leq T_1$的大小，並且把$Q$拔掉後的其他子樹大小顯然都會小於$T_1$的大小，因此把$Q$拔掉會讓剩餘的最大子樹的大小比把$P$拔掉的還要小，則$P$不是重心，矛盾。因此重心可以被當作公共點。

再來證明非重心的點不能被當作公共點，一樣設$P$為重心，並且$Q$不是重心，他落在$P$的$T_1$子樹中，那麼有$T_1$的大小$\leq \left \lfloor \frac{n}{2} \right \rfloor$，因此整棵樹扣掉$T_1$的大小$\geq \left \lceil \frac{n}{2} \right \rceil$，因此可以得到若$Q$想要當公共點，他就必須是$T_1$的根，並且滿足$T_1$的大小剛好是$\left \lfloor \frac{n}{2} \right \rfloor$，並且整棵樹扣掉$T_1$的大小要剛好是$\left \lceil \frac{n}{2} \right \rceil$，所以就可以得到$n$為偶數，$T_1$的大小為$\frac{n}{2}$，所以$Q$也是重心，矛盾。

code :

#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
const int maxn=100000+10 ;
 
struct P{int to,dis;};
vector<P> v[maxn] ;
int n ;
LL d[maxn] ;
int dfs(int x,int f,int &id,int &mi)
{
    int sz=1,maxs=0 ;
    for(auto i : v[x]) if(i.to!=f)
    {
        d[i.to]=d[x]+i.dis ;
        int tmp=dfs(i.to,x,id,mi) ;
        sz+=tmp ; maxs=max(maxs,tmp) ;
    }
    int val=max(maxs,n-sz) ;
    if(val<mi) mi=val , id=x ;
    return sz ;
}
void dfs(int x)
{
    int id,mi ;
    dfs(x,-1,id,mi) ; /// calculate dis
}
 
void dfs2(int x,int f,set<int> &s)
{
    s.insert(x) ;
    for(auto i : v[x]) if(i.to!=f)
        dfs2(i.to,x,s) ;
}
 
int cent ; /// centroid, also root of tree
set<int> st[maxn],st2 ;
set<pii> st0 ;
int id[maxn],sz,ioval[maxn] ; /// in + out number
bool ruse=0 ; /// whether root used as in point
inline void sub(int pos)
{
    st0.erase(pii(ioval[pos],pos)) ;
    ioval[pos]-- ;
    st0.insert(pii(ioval[pos],pos)) ;
}
 
int solve(int x)
{
    if(x!=cent) sub(id[x]) ;
    pii r=*st0.rbegin() ;
    if(r.F==n-x+1)
    {
        int pos=r.S , ret=*st[pos].begin() ;
        st2.erase(*st[pos].begin()) ;
        st[pos].erase(st[pos].begin()) ;
        if(!st[pos].empty()) st2.insert(*st[pos].begin()) ;
        sub(pos) ;
        return ret ;
    }
 
    int tmp=-1 ;
    if(x!=cent && !st[id[x]].empty()) st2.erase(tmp = *st[id[x]].begin()) ;
    int ret=st2.empty() ? cent : *st2.begin() ;
    if(!ruse && cent<ret) ruse=1 , ret=cent ;
    if(tmp!=-1) st2.insert(tmp) ;
 
    if(ret==cent) return ret ;
    int pos=id[ret] ;
    sub(pos) ;
    st2.erase(*st[pos].begin()) ;
    st[pos].erase(st[pos].begin()) ;
    if(!st[pos].empty()) st2.insert(*st[pos].begin()) ;
    return ret ;
}
 
main()
{
    scanf("%d",&n) ;
    for(int i=1;i<n;i++)
    {
        int x,y,dis ; scanf("%d%d%d",&x,&y,&dis) ;
        v[x].push_back((P){y,dis}) ;
        v[y].push_back((P){x,dis}) ;
    }
 
    int mi=n ;
    dfs(1,-1,cent,mi) ;
    d[cent]=0 ; dfs(cent) ;
 
    LL ans=0LL ;
    for(int i=1;i<=n;i++) ans+=d[i] ;
    printf("%I64d\n",2*ans) ;
    if(n==1){printf("1\n") ; return 0 ;}
    if(n==2){printf("2 1\n") ; return 0 ;}
 
    sz=v[cent].size() ;
    for(int i=0;i<sz;i++)
    {
        dfs2(v[cent][i].to,cent,st[i]) ;
        for(auto j : st[i]) id[j]=i ;
    }
    for(int i=0;i<sz;i++) st2.insert(*st[i].begin()) ;
    for(int i=0;i<sz;i++)
        st0.insert(pii(2*st[i].size(),i)) ,
        ioval[i]=2*st[i].size() ;
 
    for(int i=1;i<=n;i++) printf("%d%c",solve(i),i==n?'\n':' ') ;
}