题目链接
分析：
想了好久~~~还是得看题解...QwQ
首先因为是排列，所以我们猜想要把式子拆开来看， $ \sum dis(i,p[i])=\sum dep[i]+dep[p[i]]-2*dep[lca[i,p[i]]] $ ，定义 $ dep[i] $ 代表 $ i $ 到根节点的距离...
也就是说，其实我们只需要最小化$\sum dep[lca[i],p[i]]$...
我们如果考虑贪心的思想，那么显然$i$和$p[i]$不在一棵子树中的时候$lca$为$root$，那么$dep[lca]$为$0$，所以考虑能否找到一个合法的根节点，使得点两两配对并且不在一个子树中...
显然是可以的，这个优秀的根节点就是重心...
考虑重心的性质，去掉重心之后，每棵子树的大小都不会超多$\frac {n}{2}$，所以说一定存在合法的解...
那么考虑如何解决字典序最小的问题...
如果$u$和$v$匹配，但是$v$不一定和$u$匹配，所以我们把每个点拆成两个点，一个代表下标，一个代表排列，如果我们要找当前点匹配点，那么我们就去找到最大的子树，判断$size$是否刚好为当前点数的一半，如果是，那么我们就必须在这棵子树中找答案，否则就在非$u$的子树中找答案，然后在$u$的子树中删去$u$的下标点，在答案的子树中删去答案的排列点，然后用线段树维护子树内的标号最小值...
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
//by NeighThorn
#define inf 0x3f3f3f3f
#define Pa pair<int,int>
using namespace std; const int maxn=100000+5; int n,G,cnt,tim,w[maxn<<1],hd[maxn],to[maxn<<1],nxt[maxn<<1];
int be[maxn],en[maxn],siz[maxn],sub[maxn],maxsiz[maxn];
long long ans,dis[maxn]; set< pair<int,int> > s; set< pair<int,int> >::iterator it; struct M{
int l,r,Min;
}tree[maxn<<2]; inline void add(int x,int y,int s){
w[cnt]=s;to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++;
} inline void dfs(int x,int fa){
siz[x]=1;
for(int i=hd[x];i!=-1;i=nxt[i])
if(to[i]!=fa)
dfs(to[i],x),siz[x]+=siz[to[i]],maxsiz[x]=max(maxsiz[x],siz[to[i]]);
maxsiz[x]=max(maxsiz[x],n-siz[x]);
} inline void findG(void){
G=1;
for(int i=2;i<=n;i++)
if(maxsiz[G]>maxsiz[i]) G=i;
} inline void dfs(int x,int fa,int top){
sub[x]=top;siz[x]=1;be[x]=++tim;
for(int i=hd[x];i!=-1;i=nxt[i])
if(to[i]!=fa)
dis[to[i]]=dis[x]+w[i],dfs(to[i],x,top),siz[x]+=siz[to[i]];
en[x]=tim;
} inline void build(int l,int r,int tr){
tree[tr].l=l,tree[tr].r=r,tree[tr].Min=inf;
if(l==r) return;
int mid=(l+r)>>1;
build(l,mid,tr<<1),build(mid+1,r,tr<<1|1);
} inline void change(int x,int val,int tr){
if(tree[tr].l==tree[tr].r){
tree[tr].Min=val;return;
}
int mid=(tree[tr].l+tree[tr].r)>>1;
if(x<=mid)
change(x,val,tr<<1);
else
change(x,val,tr<<1|1);
tree[tr].Min=min(tree[tr<<1].Min,tree[tr<<1|1].Min);
} inline int query(int l,int r,int tr){
if(l>r) return inf;
if(tree[tr].l==l&&tree[tr].r==r)
return tree[tr].Min;
int mid=(tree[tr].l+tree[tr].r)>>1;
if(r<=mid)
return query(l,r,tr<<1);
else if(l>mid)
return query(l,r,tr<<1|1);
else
return min(query(l,mid,tr<<1),query(mid+1,r,tr<<1|1));
} inline void Minus(int x){
s.erase(s.find(Pa(siz[x],x)));
siz[x]--;
s.insert(Pa(siz[x],x));
} signed main(void){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
scanf("%d",&n);
memset(hd,-1,sizeof(hd));
for(int i=1,x,y,l;i<n;i++)
scanf("%d%d%d",&x,&y,&l),add(x,y,l),add(y,x,l);
dfs(1,0);findG();memset(siz,0,sizeof(siz));be[G]=++tim;
for(int i=hd[G];i!=-1;i=nxt[i]) dis[to[i]]=dis[G]+w[i],dfs(to[i],G,to[i]),siz[G]+=siz[to[i]],siz[to[i]]<<=1;siz[G]++;siz[G]<<=1;
for(int i=hd[G];i!=-1;i=nxt[i]) s.insert(Pa(siz[to[i]],to[i]));s.insert(Pa(siz[G],G));
build(1,n,1);en[G]=be[G];sub[G]=G;
for(int i=1;i<=n;i++) ans+=dis[i]<<1;
cout<<ans<<endl;
for(int i=1;i<=n;i++) change(be[i],i,1);
for(int i=1,x;i<=n;i++){
Minus(sub[i]);
it=s.lower_bound(Pa(n-i+1,0));
if(it!=s.end()&&it->first==n-i+1)
x=query(be[it->second],en[it->second],1);
else
x=min(query(1,be[sub[i]]-1,1),query(en[sub[i]]+1,n,1)),x=min(x,query(be[G],be[G],1));
printf("%d ",x);Minus(sub[x]);change(be[x],inf,1);
}
return 0;
}
By NeighThorn