Link.
P.S.
It looks so halal. It looks so original. It looks so fresh. The Luogu score is just a purple. It's difficult to open.
woc *3100, fear, fear, claw, claw.
And@ Krimson A practice of Hu together.
Description.
There is a tree with no root and no edge.
The \ (\ {p_i \} \) weight of an array is defined as \ (\ sum\text{dist}(i,p_i) \).
Find the maximum value of the weight and the minimum arrangement to get the maximum value.
Solution.
First of all, the maximum value is obviously the original problem of ATcoder. It must be that each edge reaches \ (\ Max \ {sz_, sz_, V \} \).
Then the first question is finished, the proof is considered to take the center of gravity, and then jump repeatedly (AT must have the original problem).
The second question is to take the same center of gravity and divide the tree into several sub trees (the center of gravity itself can be treated as one tree for convenience)
Consider the transformation. Define the in degree of a tree to represent the points that have not been matched, and the out degree to represent the points that need to be matched.
The matching scheme must meet that each point can be matched, that is, the in degree of other points is greater than the out degree of the current point.
We maintain \ (d_i \) to indicate that the in degree of other points minus the out degree of the current point.
Each match is equivalent to keeping the \ (d_i \) of the matched subtree and the matched subtree unchanged, and subtracting one from the other global.
It is required that \ (- 1 \) does not appear after subtraction.
Consider that if a \ (d_i=0 \) appears, you must directly match the two.
However, there must be only two \ (d_i=0 \) globally at the same time, and if there are two \, the others have been matched.
Then, each time there is a \ (d_i=0 \) other than the current subtree, it can only match the target.
Otherwise, it is greedy to match the global minimum value, which will certainly not make \ (d_i \) a negative number.
As for the global \ (- 1 \), just maintain a tag directly.
Pay attention to the special judgment center of gravity, because the center of gravity can match itself and does not need to meet the limit of \ (d_i\ge 0 \).
Coding.
Click to view the code//Coded by leapfrog on 2021.10.28 {{{
//Yes, you are the ghost, so when you meet me, it's my turn to become a ghost
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
f?x=-x:x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
const int N=100005;set<int>nd[N],id;set<pair<int,int> >dd;int nid=0;
struct edge{int to,w,nxt;}e[N<<1];int et,head[N],d[N],p[N];
int n,sz[N],rt,dfn[N],nfd[N],dt,f[N],tag[N];ll rs=0;
inline void adde(int x,int y,int w) {e[++et]=(edge){y,w,head[x]},head[x]=et;}
inline void getrt(int x,int fa)
{
sz[x]=1;int mx=0;for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa)
getrt(e[i].to,x),sz[x]+=sz[e[i].to],mx=max(mx,sz[e[i].to]);
mx=max(mx,n-sz[x]);if(mx<=n/2) rt=x;
}
inline void dfs0(int x,int fa)
{
dfn[x]=++dt,nfd[dt]=x,sz[x]=1,f[x]=fa;
for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa)
dfs0(e[i].to,x),sz[x]+=sz[e[i].to],rs+=2ll*min(sz[e[i].to],n-sz[e[i].to])*e[i].w;
}
int main()
{
read(n);for(int i=1,x,y,w;i<n;i++) read(x,y,w),adde(x,y,w),adde(y,x,w);
if(n==1) return puts("0\n1\n"),0;else if(n==2) return printf("%lld\n2 1\n",2ll*e[head[1]].w),0;
getrt(1,0),dfs0(rt,0),printf("%lld\n",rs);
for(int i=head[rt],x;i;i=e[i].nxt)
{
++nid,x=e[i].to;for(int l=dfn[x];l<dfn[x]+sz[x];l++) nd[tag[nfd[l]]=nid].insert(nfd[l]);
id.insert(*nd[nid].begin()),dd.insert(make_pair(d[nid]=n-2*nd[nid].size(),nid));
}
nd[tag[rt]=++nid].insert(rt),dd.insert(make_pair(d[nid]=n-2,nid)),id.insert(rt);
int tg=0;for(int i=1;i<=n;i++)
{
int ps=tag[i],tw;dd.erase(make_pair(d[ps],ps));
if(dd.begin()->first+tg==0&&dd.begin()->second!=tag[rt]) tw=dd.begin()->second;
else if(tag[*id.begin()]==ps&&i!=rt) tw=tag[*++id.begin()];else tw=tag[*id.begin()];
int qw=*nd[tw].begin();p[i]=qw,tg--,dd.erase(make_pair(d[tw],tw));
id.erase(qw),nd[tw].erase(nd[tw].begin());if(!nd[tw].empty()) id.insert(*nd[tw].begin());
dd.insert(make_pair(++d[ps],ps)),dd.insert(make_pair(++d[tw],tw));
}
for(int i=1;i<=n;i++) printf("%d%c",p[i],i==n?'\n':' ');
return 0;
}