本文共 4982 字，大约阅读时间需要 16 分钟。

题目

题目概要
求一个序列 { p i } \{p_i\} { pi​} ，使得 ${\sum }_{i=1}^n\mathtt{d}\mathtt{i}\mathtt{s}\mathtt{t}(i,p_i)$ 最小。输出字典序最小的解。

数据范围与约定
边权 $w\le 10^5$，$n\le 10^5$ 。

思路

用 $d(i)$ 表示点 $i$ 的深度，以此来去掉 $\mathtt{d}\mathtt{i}\mathtt{s}\mathtt{t}$ 函数。写出式子

$$\begin{array}{rl}ans& =\sum _{i=1}^n[d(i)+d(p_i)-2\cdot d(lca)]\\ & =2\sum _{i=1}^{n}d(i)-2\sum _{i=1}^{n}d[lca(i,p_i)]\end{array}$$

注意这一点：树根不影响树上距离，所以说 树根只需要随便确定一个即可。不想清楚这一点，就会对后面确定树根的操作感到疑惑——确定树根的目的只是构造解，树根不影响答案。

任意取一个树根 $root$ ，答案的上界是 $lca$ 始终为 $root$ 。也就是说，$i$ 和 $p_i$ 不是同一个儿子的子树，或者其中一个是根（甚至两个都是根）。

说明：接下来的叙述中，“子树”代表的是根节点的某个儿子的子树，并将根单独视为一棵子树。如果不特殊说明，则 $\sum sth$ 均视作 ${\sum }_{i\in son(root)}sth$ 。

将 $⟨i,p_i⟩$ 视为一条树上路径，那么我们用 $f(x)$ 表示子树内未匹配的出度数量，用 $g(x)$ 表示子树内未匹配的入度数量。此时，$lca$ 能够始终为 $root$ 的充要条件是：对于任意一棵不是根的子树 $t$ ，因为其出度都不得不与子树外的入度匹配，所以 $f(t)\le {\sum }_{i\ne t}g(i)$ ，也即，

$$f(t)+g(t)\le \sum g(i)$$

在任意时刻，$\sum f(i)=\sum g(i)$ 。所以说，能够满足 $f(t)+g(t)=\sum g(i)$ 的 $t$ 至多有两个（如果有两个，则只有这两个子树满足 $f(i{)}^2+g(i{)}^2\ne 0$ ，也就是说，其他的子树都“用光”了）。

如果满足这个条件，我们每次找到使 $f(t)+g(t)$ 最大的一个 $t$ ，并将子树内一点与另一棵子树内一个点匹配。这样一来，$f(t)+g(t)$ 减小了一，而 $\sum g(i)$ 也减小了一，所以一定可行。

怎么确定这个 $root$ 呢？答案是重心。在最初的时候，$\sum g(i)=2n$ ，且 $f(i)+g(i)=2\times size$ ，所以目的就是 $size\le \lfloor \frac{n}{2}\rfloor$ 总成立。这就是重心的充要条件啊！

由于能够取到上界，所以 $root$ 为重心时，可以用此方法构造出一个答案最大的情况。

接下来的目的是找到字典序最小的一个。考虑一个一个的确定 $p$ 。

如果其中一个子树 $t$ 满足 $f(t)+g(t)=\sum g(i)$ ，并且 $i$ 不属于子树 $t$ ，那么 $p_i$ 必须属于子树 $t$ 。其他情况下，只需要满足 $p_i$ 与 $i$ 不在同一棵子树中。

这可以用 $\mathtt{s}\mathtt{e}\mathtt{t}$ 很简单的维护，毕竟 $\sum g(i)=n-($ 已经匹配的数量 $)$ 。时间复杂度 $\mathcal{O}(n\log n)$ 。

代码

#include <cstdio>#include <iostream>#include <vector>#include <set>#include <queue>using namespace std;inline int readint(){   	int a = 0; char c = getchar(), f = 1;	for(; c<'0'||c>'9'; c=getchar())		if(c == '-') f = -f;	for(; '0'<=c&&c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}const int MaxN = 100005;struct Edge{   	int to, nxt, val;	Edge(int T=0,int N=0,int V=0){   		to = T, nxt = N, val = V;	}};Edge edge[MaxN<<1];int head[MaxN], n, cntEdge;void addEdge(int a,int b,int c){   	edge[cntEdge] = Edge(b,head[a],c);	head[a] = cntEdge ++;	edge[cntEdge] = Edge(a,head[b],c);	head[b] = cntEdge ++;}void input(){   	n = readint();	for(int i=1; i<=n; ++i)		head[i] = -1;	for(int i=1,a,b; i<n; ++i){   		a = readint(), b = readint();		addEdge(a,b,readint());	}}int bel[MaxN]; // 每个点属于哪个儿子子树 int siz[MaxN], root;long long ans;/** @brief 三合一：求答案、赋值bel、找重心 */void dfs(int x,int pre,long long depth,int b){   	ans += depth<<1, bel[x] = b, siz[x] = 1;	for(int i=head[x]; ~i; i=edge[i].nxt)		if(edge[i].to != pre){   			dfs(edge[i].to,x,depth+edge[i].val,b);			siz[x] += siz[edge[i].to];		}	if(root == 0){    // 确定重心		int mx = n-siz[x];		for(int i=head[x]; ~i; i=edge[i].nxt)			if(edge[i].to != pre)				mx = max(mx,siz[edge[i].to]);		if(mx <= (n>>1)) root = x;	}}set< pair<int,int> > pq; // 找 f+g 的最大值set<int> tree[MaxN]; // 每个儿子子树中的所有点set<int> all; // 每颗子树的最小值（用以构造字典序小的解）int deg[MaxN];void solve(){   	dfs(1,-1,0,-1); // 找重心 	ans = 0, dfs(root,-1,0,-1); // 算答案 	printf("%lld\n",ans);	for(int i=head[root]; ~i; i=edge[i].nxt)		dfs(edge[i].to,root,0,edge[i].to); // 赋值bel 	bel[root] = root; // 自成一棵子树 	for(int i=1; i<=n; ++i)		tree[bel[i]].insert(i);	all.insert(root); // "根子树" 	for(int i=head[root]; ~i; i=edge[i].nxt){   		int x = edge[i].to;		deg[x] = tree[x].size()<<1;		pq.insert(make_pair(deg[x],x));		all.insert(*tree[x].begin());	}	for(int i=1,match; i<=n; ++i){   		auto it = pq.end(); if(not pq.empty()) -- it;		/* 箭在弦上（f+g=n-已匹配 且 i不属于该子树），不得不发 */		if(not pq.empty() and it->first == n-i+1 and it->second != bel[i])			match = *tree[it->second].begin();		else{    // 构造字典序最小			auto j = all.begin();			if(bel[*j] == bel[i] and i != root and *j != root)				++ j; // invalid			match = *j;		}		printf("%d ",match);		tree[bel[match]].erase(match);		all.erase(match);		pq.erase(make_pair(deg[bel[i]],bel[i]));		pq.insert(make_pair(--deg[bel[i]],bel[i]));		pq.erase(make_pair(deg[bel[match]],bel[match]));		pq.insert(make_pair(--deg[bel[match]],bel[match]));		if(not tree[bel[match]].empty())			all.insert(*tree[bel[match]].begin());	}	puts("");}int main(){   	input(), solve();	return 0;}