自动搬运

查看原文

来自洛谷，原作者为

	Genius_Star 跟你爆了

搬运于2025-08-24 23:08:57，当前版本为作者最后更新于2025-01-27 20:46:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路：

容易发现在树上，必须经过点 $t$ 的最短路径长度 $\operatorname{dist}(u, v) = \operatorname{dis}(u, t) + \operatorname{dis}(v, t)$。

故有：

$$\begin{aligned} \sum_{u = 1}^n \sum_{v = 1}^n \operatorname{dist}(u, v) &= \sum_{u = 1}^n \sum_{v = 1}^n \operatorname{dis}(u, t) + \operatorname{dis}(v, t) \\ &= 2n \sum_{u = 1}^n \operatorname{dis}(u, t) \end{aligned} $$

故我们只需要最大化：

$$\sum_{u = 1}^n \operatorname{dis}(u, t)$$

钦定 $t$ 为跟，则原式化为：

$$\sum_{u = 1}^n dep_t$$

容易预处理出 $cnt_i$ 表示 $i$ 这条边被经过的次数，设 $w_i$ 表示边权，则要最大化：

$$\sum_{i = 1}^{n - 1} cnt_i w_i$$

由于 $w$ 是一个排列，故考虑贪心即可，按照 $cnt$ 的值从大到小分配 $(n - 1) \to 1$。

这样就可以做到 $O(N^2)$。

考虑 $cnt_i$ 本质是什么？设 $i$ 这条边为 $(u, v)$，且以 $t$ 为根时 $v$ 较深一些，故有：

$$cnt_i = siz_v$$

故有式子为：

$$\sum_{i = 1}^{n - 1} siz_{v_i} w_i$$

由于我们需要枚举 $t$，故考虑换根 dp。

设从 $fa_u$ 换到 $u$，发现修改了 $siz$ 的点很少，只有 $u, fa_u$ 这两个点；其中 $siz_{fa_u} \gets siz_{fa_u} - siz_u, siz_u \gets n$。

即相当于在原来 $\{siz_i\}$ 集合中删除 $siz_u$，加入新的 $siz'_{fa_u}$。

故我们现在只需要做单点修改，全局下面式子的最大值：

$$\sum_{i = 1}^{n - 1} siz_{v_i} w_i$$

考虑维护值域线段树 $[1, n]$，对于每个区间 $[l, r]$ 维护有多少个 $siz_i$ 在这里面（设有 $cnt$ 个），以及这些 $siz$ 的和 $sum$，以及考虑 $w$ 是 $1 \sim cnt$ 的 排列时的最大值。

合并两个区间 $cnt_l, sum_l, ans_l, cnt_r, sum_r, ans_r$ 时，显然有：

$$cnt = cnt_l + cnt_r$$ $$sum = sum_l + sum_r$$

对于右区间的 $w$，显然要由 $1 \sim cnt_r$ 的排列变为 $cnt_l + 1 \sim cnt_l + cnt_r + 1$ 的排列，即 $w$ 整体添加了 $cnt_l$，故：

$$ans = ans_l + ans_r + cnt_l sum_r$$

时间复杂度为 $O(N \log N)$。

总体认为下位紫，最后我认为并不好想到值域线段树的做法，比较显然的应该是楼下老哥的平衡树做法。

完整代码：

#include<bits/stdc++.h>
#define lowbit(x) x & (-x)
#define pi pair<ll, ll>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e5 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	if(x > 9)
	  write(x / 10);
	putchar(x % 10 + '0');
}
struct St{
	int data;
	int id;
	inline bool operator<(const St&rhs)const{
		if(data ^ rhs.data)
		  return data > rhs.data;
		return id > rhs.id;
	}
}A[N];
struct Node{
	int l, r;
	int cnt;
	ll sum, ans;
}X[N << 2];
ll ans;
int n, id;
int siz[N], p[N], w[N];
vector<pair<int, int>> E[N];
inline void add(int u, int v, int id){
	E[u].push_back({v, id});
	E[v].push_back({u, id});
}
inline void pushup(int k){
	X[k].cnt = X[k << 1].cnt + X[k << 1 | 1].cnt;
	X[k].sum = X[k << 1].sum + X[k << 1 | 1].sum;
	X[k].ans = X[k << 1].ans + X[k << 1 | 1].ans + 1ll * X[k << 1].cnt * X[k << 1 | 1].sum;
}
inline void build(int k, int l, int r){
	X[k].l = l, X[k].r = r;
	if(l == r)
	  return ;
	int mid = (l + r) >> 1;
	build(k << 1, l, mid);
	build(k << 1 | 1, mid + 1, r);
}
inline void update(int k, int i, int v){
	if(X[k].l == i && i == X[k].r){
		X[k].cnt += v;
		X[k].sum += v * i;
		if(v == 1)
		  X[k].ans += 1ll * X[k].cnt * i;
		else
		  X[k].ans -= 1ll * (X[k].cnt + 1) * i;
		return ;
	}
	int mid = (X[k].l + X[k].r) >> 1;
	if(i <= mid)
	  update(k << 1, i, v);
	else
	  update(k << 1 | 1, i, v);
	pushup(k);
}
inline void dfs1(int u, int fa){
	siz[u] = 1;
	for(auto t : E[u]){
		int v = t.fi, w = t.se;
		if(v == fa)
		  continue;
		p[v] = w;
		dfs1(v, u);
		siz[u] += siz[v];
	}
}
inline void dfs2(int u, int fa){
	for(auto t : E[u]){
		int v = t.fi;
		if(v == fa)
		  continue;
		int pre = siz[v];
		update(1, siz[v], -1);
		update(1, n - siz[v], 1);
		siz[u] -= siz[v];
		siz[v] = n;
		if(X[1].ans > ans){
			ans = X[1].ans;
			id = v;
		}
		else if(X[1].ans == ans)
		  id = min(id, v);
		dfs2(v, u);
		siz[v] = pre;
		siz[u] = n;
		update(1, n - siz[v], -1);
		update(1, siz[v], 1);
	}
}
int main(){
	n = read();
	for(int u, v, i = 1; i < n; ++i){
		u = read(), v = read();
		add(u, v, i);
	}
	build(1, 1, n);
	dfs1(1, 1);
	for(int i = 2; i <= n; ++i)
	  update(1, siz[i], 1);
	ans = X[1].ans;
	dfs2(1, 1);
	write(2ll * n * ans);
	putchar('\n');
	write(id);
	putchar('\n');
	dfs1(id, id);
	int l = 0;
	for(int i = 1; i <= n; ++i){
		if(i == id)
		  continue;
		A[++l] = {siz[i], p[i]};
	}
	sort(A + 1, A + n);
	for(int i = 1; i < n; ++i)
	  w[A[i].id] = n - i;
	for(int i = 1; i < n; ++i){
		write(w[i]);
		putchar(' ');
	}
	return 0;
}