计蒜客信息学 8 月提高组模拟赛

V_Melville精進録 / 2023-08-27 / 原文

T1：树节点的排序

\(N \leqslant 8\)：

枚举排列即可

\(N \leqslant 15\)：

状压dp
dp[i][s] 表示深度为 \(i\)，排列中选了 \(s\) 里所有点进行状态转移

树为一条链：

左边与右边配对即可

\(N \leqslant 5000\)：

树形dp
dp[i][j] 表示在以点 \(i\) 为根的子树中，选的点深度最大为 \(j\) 进行状态转移

\(N \leqslant 10^6\)：

之前那个树形dp可以用长链剖分优化
也可以用另一种方法
分别考虑每条边对答案的贡献
每条边两端连接的连通块大小不妨记为 \(x\) 和 \(y\)
那么这条边对答案最多贡献 \(2\min(x, y)\) 次
即其中一个连通块的 \(\min(x, y)\) 个点穿过这条边跑到另一个连通块
实际上每条边是可以同时分别取到这个最大值的
那么一次 \(\operatorname{dfs}\) 过程就能统计出来，只需要额外记录子树大小
时间复杂度：\(\mathcal{O}(n)\)

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    
    int n;
    cin >> n;
    
    vector<vector<P>> g(n);
    rep(i, n-1) {
        int a, b, c;
        cin >> a >> b >> c;
        --a; --b;
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }
    
    ll ans = 0;
    vector<int> t(n, 1);
    auto dfs = [&](auto f, int v, int p=-1) -> void {
        for (auto [u, w] : g[v]) {
            if (u == p) continue;
            f(f, u, v);
            t[v] += t[u];
            ans += 2ll*min(t[u], n-t[u])*w;
        }
    };
    dfs(dfs, 0);
    
    cout << ans << '\n';
    
    return 0;
}