「2026 CCPC 贵州邀请赛」J. AI模型的优化

    「2026 CCPC 贵州邀请赛」J. AI模型的优化

    https://codeforces.com/gym/695551/problem/J

    给出一棵包含 nn 个点的树。

    定义 f(l,r)f(l, r) 表示包含 l,…,rl, \dots, r 的最小连通块的大小,求 ∑1≤l≤r≤nf(l,r)\sum_{1 \leq l \leq r \leq n} f(l, r)。

    数据范围:1≤n≤1051 \leq n \leq 10^5。

    时空限制:11s / 512512MiB。

    Solution

    一开始往“支配对”上面想,属于是想歪了。因为很难处理出子树内对子树外的支配对。

    注意到树上连通块的点数,等于边数 +1+1。所以我们可以考虑计算边的贡献。

    算法一

    相当于是要求,有多少个区间既有子树内的点又有子树外的点。

    正难则反,可以用总区间数,减去“所有点都在子树内的区间个数”以及“所有点都在子树外的区间个数”。

    以“所有点都在子树内的区间个数”为例,如果一个点在子树内就将其标记成 11,否则标记成 00。则一个长度为 LL 的全 11 连续段,会产生 L(L+1)2\frac{L(L + 1)}{2} 的贡献。

    于是可以使用 DSU on tree 维护将子树内所有点全都标记成 11 的过程,使用 std::set 维护连续段。

    时间复杂度 O(nlog⁡2n)\mathcal{O}(n \log^2 n)。

    #include <bits/stdc++.h>
    
    using i64 = long long;
    
    #define debug(a) std::cout << #a << '=' << (a) << ' '
    
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    const int N = 200100;
    
    int n;
    std::vector<std::vector<int>> G;
    
    i64 calc(int x) {
        return 1ll * x * (x + 1) / 2;
    }
    
    struct segment {
        i64 sum;
        std::set<std::pair<int, int>> s;
    
        void all0() {
            sum = 0;
            s = {};
        }
        void all1() {
            sum = calc(n);
            s = {{1, n}};
        }
    
        void add(int x) {
            auto it = s.lower_bound({x, 0});
            int l = x, r = x;
            if (it != s.begin()) {
                auto itl = std::prev(it);
                auto [l1, r1] = *itl;
                if (r1 + 1 == x) {
                    sum -= calc(r1 - l1 + 1);
                    s.erase(itl);
                    l = l1;
                }
            }
            if (it != s.end()) {
                auto [l2, r2] = *it;
                if (l2 - 1 == x) {
                    sum -= calc(r2 - l2 + 1);
                    s.erase(it);
                    r = r2;
                }
            }
            sum += calc(r - l + 1);
            s.insert({l, r});
        }
    
        void dec(int x) {
            auto it = -- s.lower_bound({x + 1, 0});
            auto [l, r] = *it;
    
            sum -= calc(r - l + 1);
            s.erase(it);
            if (x > l) {
                sum += calc(x - l);
                s.insert({l, x - 1});
            }
            if (x < r) {
                sum += calc(r - x);
                s.insert({x + 1, r});
            }
        }
    } si, so;
    
    int sze[N], son[N];
    
    void dfs_init(int u, int fu) {
        sze[u] = 1, son[u] = 0;
        for (int v : G[u]) {
            if (v == fu) {
                continue;
            }
            dfs_init(v, u);
            sze[u] += sze[v];
            if (sze[v] > sze[son[u]]) {
                son[u] = v;
            }
        }
    }
    
    i64 ans;
    
    void add(int x) {
        si.add(x), so.dec(x);
    }
    void addTree(int u, int fu) {
        add(u);
        for (int v : G[u]) {
            if (v == fu) {
                continue;
            }
            addTree(v, u);
        }
    }
    
    void solve(int u, int fu, bool save) {
        for (int v : G[u]) {
            if (v == fu || v == son[u]) {
                continue;
            }
            solve(v, u, 0);
        }
        if (son[u]) {
            solve(son[u], u, 1);
        }
    
        for (int v : G[u]) {
            if (v == fu || v == son[u]) {
                continue;
            }
            addTree(v, u);
        }
        add(u);
    
        if (u > 1) {
            ans += 1ll * n * (n + 1) / 2 - si.sum - so.sum;
        }
    
        if (!save) {
            si.all0(), so.all1();
        }
    }
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        std::cin >> n;
    
        G.assign(n + 1, {});
        for (int i = 1; i < n; i ++) {
            int x, y;
            std::cin >> x >> y;
            G[x].push_back(y);
            G[y].push_back(x);
        }
    
        dfs_init(1, 0);
    
        ans = 1ll * n * (n + 1) / 2;
        si.all0(), so.all1();
        solve(1, 0, 1);
    
        std::cout << ans << '\n';
    
        return 0;
    }

    算法二

    还是计算边的贡献。对于某条边,如果点对 (i,i+1)(i, i + 1) 的其中一个点在子树内,另外一个点在子树外,那么称点对 (i,i+1)(i, i + 1) 是这条边的断点。

    那么一个区间既有子树内的点又有子树外的点,当且仅当这个区间内存在断点。

    注意到点对 (i,i+1)(i, i + 1),会对从 ii 到 i+1i + 1 的路径上的所有边 ee 都产生一个断点。设边 ee 的上一个断点位置为 lstelst_e,则新产生的贡献为 (i−lste)(n−i)(i - lst_e)(n - i)。

    相当于要支持路径 lstelst_e 求和与路径 lstelst_e 覆盖,使用重链剖分 + 线段树维护即可。

    时间复杂度 O(nlog⁡2n)\mathcal{O}(n \log^2 n)。