第一问是简单的,\(2(n - 1) - [T = 1] \cdot \max\limits_{i = 1}^{n}\{dep_i\}\)。
对于第二问:
设 \(f(u)\) 表示要求起点和终点均为 \(u\) 的情况下从 \(1\) 时刻开始遍历完以 \(u\) 为根的子树的最小花费,\(g(u)\) 表示要求起点为 \(u\),重点深度最大的情况下从 \(1\) 时刻开始遍历完以 \(u\) 为根的子树的最小花费。
令 \(s(u)\) 表示以 \(u\) 为根的子树中的 \(a\) 的和,\(sz(u)\) 表示以 \(u\) 为根的子树大小。对于 \(u\) 的两个儿子 \(v_1, v_2\),若先遍历 \(v_1\) 再遍历 \(v_2\),则它们的贡献为:
\[f(u) \gets f(v_1) + f(v_2) + 2 \cdot sz(v_1) \cdot s(v_2) \]若交换遍历顺序,则又有:
\[f(u) \gets f(v_1) + f(v_2) + 2 \cdot sz(v_2) \cdot s(v_1) \]也就是说,\(v_1\) 先于 \(v_2\) 遍历当且仅当 \(sz(v_1) \cdot s(v_2) \le sz(v_2) \cdot s(v_1)\)。
于是排序更新即可,这部分的时间复杂度为 \(\mathcal O(n \log n)\)。
\(g\) 借助 \(f\) 更新即可。
也就是把符合条件的 \(f(v)\) 去掉,在最后加上 \(g(v)\),具体看代码吧。
总时间复杂度 \(\mathcal O(n \log n)\)。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 2e5 + 10;
int n, T, a[N], sz[N], maxd[N];
ll s[N], f[N], g[N];
vector<int> G[N];
bool cmp(const int &a, const int &b) {
return sz[a] * s[b] <= sz[b] * s[a];
}
void dfs(int u) {
sz[u] = 1, s[u] = a[u];
for (int v : G[u]) {
dfs(v);
maxd[u] = max(maxd[u], maxd[v] + 1), sz[u] += sz[v], s[u] += s[v];
}
sort(G[u].begin(), G[u].end(), cmp);
ll time = 1, sufs = 0;
for (int v : G[u]) f[u] += f[v] + time * s[v], time += 2 * sz[v], sufs += s[v];
if (G[u].empty()) return;
g[u] = 9e18;
for (int v : G[u]) {
time -= 2 * sz[v], sufs -= s[v];
if (maxd[u] == maxd[v] + 1) g[u] = min(g[u], f[u] - f[v] + g[v] - 2 * sz[v] * sufs + (time - 1) * s[v]);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> T;
for (int i = 2, fa; i <= n; i++) {
cin >> fa >> a[i];
G[fa].emplace_back(i);
}
dfs(1);
if (T == 0) cout << 2 * (n - 1) << ' ' << f[1];
else cout << 2 * (n - 1) - maxd[1] << ' ' << g[1];
return 0;
}
标签:sz,遍历,洛谷,cdot,Piling,int,子树,为根,P9129
From: https://www.cnblogs.com/chy12321/p/17831050.html