自动搬运

查看原文

来自洛谷，原作者为

	zrzring あとどれくらいの距離を月へ歩いたら？あとどれくらいの寒い夜を重ねたら？あとどれくらいのさよならを流し？

搬运于2025-08-24 22:29:23，当前版本为作者最后更新于2021-02-20 21:59:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

更好的阅读体验

考虑贪心，按权值排序，对于枚举到的节点$i$，我们要尽量让这个点和小的点连边，考虑到我们要保证这棵树存在，所以留1的度数用来让这棵树能和剩下的点连起来，于是每次枚举的连通块都需要预留至少1度数和后面的点连边。

我们用一个指针$j$表示$[1, j]$已经变成了一个连通块，那么对于枚举到的$i$就从$j$往后开始连，所以任意时刻我们连出来的一定仅有一个连通块的，根据上面的结论，我们再维护这个连通块的度数使他保持有至少为1的度数即可。

我写题解一般都写的很少的，但这次是验题的工作，所以写一下详细证明。

若当前枚举到的$i$使得$[1, j]$连通块最后仅剩$i$这个点有$1$的度数，且$j + 1$的点度数为1，那么连这个点就会导致无法和后面的点连通，所以要找到后面第一个度数大于1的点$k$相连，然后再处理i到k之间的点直到$k$的度数为1或区间内的点被连完，如果这个区间还有剩下的点就继续寻找下一个$k$，直到$[1, k]$为一个连通块或者已经连到了$n$，由于题目保证树存在，所以连到$n$的时候已经不需要保证度数可以直接相连。

若已知$a > b > c > d$，在所有将他们分成两对分别求乘积的和的方案中，最大值为$ab + cd$。

所以对于上述过程，因为在任意时刻，全局最小的权值会和当前该权值能连边的最小权值相乘，所以最终结果一定是最大值。

可以反证，首先初始的边集为空集，肯定为最优解的子集，如果最小的权值$a$没有和它能连的最小权值$b$相连，而和$c$相连，那么一定会存在一个比$a$大的权值$d$和$b$相连，这违背了上述结论，所以这个解一定不是最优的，故上述结论构成的子集一定是最优解的子集，于是如果当前为最优解的子集，之后每步加的边都是最优解的子集。

这个过程具有对称性，所以对权值的排序从小到大和从大到小是等价的。

而我们保证了$[1, j]$为连通块，每次相连一定与$[j + 1, n]$的点相连，对于$k$来说，因为$i$到$k$路径上的点度数均为1，所以和$k$相连的点不可能与之前的连通块构成环，剩下的点与$[k + 1, n]$的点相连，这时可以理解为这些点已经不存在，并且后面的点度数改变，由于题目保证可以构成树，加上我们限制了每个点至少要保留1的度数，所以这个过程毫无影响正确性。

时间复杂度O(n)，这里为了复杂度对应用的桶排，实际上用sort可以在2s内通过所有数据。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

#define mp(x, y) make_pair(x, y)
#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout);

using namespace std;

const int N = 1e7 + 10;

inline int read() {
	bool sym = 0; int res = 0; char ch = getchar();
	while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return sym ? -res : res;
}

struct NODE {int d, val;} dat[N], t[N];

int n, m = 5e5, last, cnt[N];

long long ans;

namespace STD {
	unsigned seed;
	unsigned rnd(unsigned x) {
		x ^= x << 13; x ^= x >> 17; x ^= x << 5; return x;
	}
	int rad(int x, int y) {
		seed = rnd(seed); return seed % (y - x + 1) + x;
	}
	void init() {
		seed = read();
		for(int i = 1; i <= n; i++) t[i].d = 1, t[i].val = rad(1, 500000);
		for(int i = 1; i <= n - 2; i++) t[rad(1, n)].d++;
	}
}

void sort() {
	for (int i = 1; i <= n; i++) cnt[t[i].val]++;
	for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
	for (int i = 1; i <= n; i++) dat[cnt[t[i].val]--] = t[i];
}

int main() {
	int type = read(); n = read();
	if (type == 1) STD::init(); else {
		for (int i = 1; i <= n; i++) t[i].d = read();
		for (int i = 1; i <= n; i++) t[i].val = read();
	}
	sort(); last = 1;
	for (int i = 1, j = 2, k = 2; i <= n; i++, j = max(j, i + 1)) {
		while (dat[i].d == 0 && i <= n) i++; if (i > n) break;
		while (dat[i].d > 1) {
			while (dat[j].d == 0) j++; if (dat[j].d > 1) last = j;
			ans += 1ll * dat[i].val * dat[j].val; dat[i].d--; dat[j].d--; j++;
		}
		if (last == i) {
			k = max(j, k); while (dat[k].d <= 1 && k < n) k++;
			ans += 1ll * dat[i].val * dat[k].val; dat[i].d--; dat[k].d--; i = j;
			while (i < k && dat[k].d > 1) {
				ans += 1ll * dat[i].val * dat[k].val; dat[i].d--; dat[k].d--; i++;
			}
			if (dat[k].d == 1) last = i; else last = k; i--;
		} else {
			while (dat[j].d == 0 && j < n) j++; if (dat[j].d > 1) last = j;
			ans += 1ll * dat[i].val * dat[j].val; dat[i].d--; dat[j].d--; j++;
		}
	}
	printf("%lld", ans);
	return 0;
}