自动搬运

查看原文

来自洛谷，原作者为

	Elma_ blog：https://www.cnblogs.com/came11ia

搬运于2025-08-24 22:45:37，当前版本为作者最后更新于2023-03-18 21:33:55，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

先考虑 $T=0$ 时怎么做。显然，最优的遍历顺序是树的某个 DFS 序，对于 $n$ 个点的树遍历的步数是 $2n-2$。我们只需要对于每个节点 $u$，决定其儿子的遍历顺序。

设 $f_u$ 为 $u$ 子树内的答案，$sz_u$ 为 $u$ 子树的大小，$sum_u$ 为 $u$ 子树内 $a_i$ 的和。假设我们现在在 $u$，先进入了别的子树，经过 $T$ 时间后再进入 $v$，我们把每个节点的贡献拆开，可以得到 $v$ 对 $f_u$ 的贡献是 $sum_v \times T + f_v$。而当我们确定顺序后，遍历某个子树 $v$ 之前的子树所需的时间是确定的，相当于有 $k$ 个二元组 $(a_i,b_i)$，其中 $a_i = sum_{v_i},b_i = 2 \times sz_{v_i}$，求一个排列 $p$ 使得 $\sum \limits_{i = 1}^k \left( a_{p_i} \times \big( \sum \limits_{j=1}^{j<i} b_{p_j} + 1 \big) + f_{p_i} \right)$ 最小。

式子中和 $f$ 有关的项都是确定的，我们要最小化的其实是 $\sum \limits_{i = 1}^k a_{p_i} \times \sum \limits_{j=1}^{j<i} b_{p_j}$。这是个经典 exchange argument，考虑序列中相邻的两个位置 $i,i+1$，显然交换他们不会影响其他项的贡献。设 $i$ 之前的 $b_i$ 和为 $S$，如果交换后答案变得更优，那么有 $a_i \times S + a_{i+1} \times (S + b_i) > a_{i+1} \times S + a_{i} \times (S + b_{i+1})$，即 $\frac{a_{i+1}}{b_{i+1}} > \frac{a_i}{b_i}$。这个条件也是充要的，也就是说，如果序列中存在相邻两个位置满足这个条件，那么交换后答案一定更优。

那么最优的顺序一定按照 $\frac{a_i}{b_i}$ 降序排列，据此容易计算答案，总时间复杂度 $\mathcal{O}(n \log n)$。

对于 $T = 1$ 有相似的结论，如果我们停留在深度为 $d$ 的节点，那么遍历的最小步数为 $(2n - 2) - d$。所以我们最后一定会停留在深度最大的节点。

设最大深度为 $D$。同样，我们还是需要为每个节点决定其儿子的遍历顺序，但与之前不同的是，我们需要选择一个儿子 $v$ 满足其子树内存在深度为 $D$ 的节点，把 $v$ 留到最后进入。我们可以先预处理出哪些节点可以作为这样的 $v$，而对于剩余的儿子节点，和 $T=1$ 时一样，按照 $\frac{a_i}{b_i}$ 排序即可。

当然，我们不可能对于每个可能的 $v$ 都排一遍序。一个简单的优化方式是，由于每次确定 $v$ 后其余的节点都是按照 $\frac{a_i}{b_i}$ 排序，因此这和 $T=0$ 时的结果只会有一项不同，我们可以先算出 $T=0$ 时的答案，枚举 $v$ 时扣掉 $v$ 的贡献，然后加上把 $v$ 放在最后的贡献。这可以通过一些简单的预处理做到单次 $\mathcal{O}(1)$。总时间复杂度 $\mathcal{O}(n \log n)$。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 5;
const LL inf = 2e18;
int n, t, mxd, a[N], sz[N], dep[N]; LL sum[N], f[N], g[N], suf[N];
bool mark[N];
vector <int> e[N];
struct dat {
	LL a, b; int v;
} d[N];
void dfs0(int u) {
	for (auto v : e[u]) dfs0(v), dep[u] = max(dep[u], dep[v] + 1);
}
void ptag(int u, int d) {
	if (d + dep[u] == mxd) mark[u] = 1;
	for (auto v : e[u]) ptag(v, d + 1);
}
void dfs(int u) {
	sz[u] = 1, sum[u] = a[u];
	int m = 0;
	for (auto v : e[u]) {
		dfs(v);
		sz[u] += sz[v], sum[u] += sum[v];
		f[u] += f[v];
	}
	for (auto v : e[u]) {
		d[++m] = (dat){ sum[v], 2 * sz[v], v };
	}
	sort(d + 1, d + m + 1, [&](dat i, dat j) { return j.a * i.b < i.a * j.b; });
	LL val = 0, sb = 1;
	for (int i = 1; i <= m; i++) {
		val += d[i].a * sb, sb += d[i].b;
	}
	suf[m + 1] = 0;
	for (int i = m; i >= 1; i--) suf[i] = suf[i + 1] + d[i].a;
	LL ret = inf, pre = 1;
	for (int i = 1; i <= m; i++) {
		int v = d[i].v;
		if (mark[v]) ret = min(ret, f[u] - f[v] + g[v] + val - d[i].b * suf[i + 1] - d[i].a * pre + d[i].a * (sb - d[i].b));	
		pre += d[i].b;	
	}
	f[u] += val, g[u] = ret;
	if (m == 0) g[u] = 0;
}
int main() { 
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> t;
    for (int i = 2, ff; i <= n; i++) {
		cin >> ff >> a[i];
		e[ff].push_back(i);
	}
	dfs0(1), mxd = 0;
	for (int i = 1; i <= n; i++) mxd = max(mxd, dep[i]);
	ptag(1, 0), dfs(1);
	if (t == 0) cout << 2 * (n - 1) << " " << f[1] << "\n";
	else cout << 2 * (n - 1) - mxd << " " << g[1] << "\n";
    return 0;
}