「代码源挑战赛 R33F」最大边权

    「代码源挑战赛 R33F」最大边权

    daimayuan 203

    给出一棵包含 nn 个节点的树,边带权。

    有 QQ 次询问,每次询问给出 kk 个区间 [l1,r1],…,[lk,rk][l_1, r_1], \dots, [l_k, r_k],定义点集 VV 表示至少被一个区间包含的点构成的集合。

    考虑 VV 的所有无序点对 (u,v)(u, v),将树上 u,vu, v 之间的简单路径上所有边进行染色。你需要求出所有被染色边的最大边权。

    数据范围:1≤n,Q≤2×1051 \leq n, Q\leq 2 \times 10^5,1≤∑k≤2×1051 \leq \sum k \leq 2 \times 10^5,1≤li≤ri≤n1 \leq l_i \leq r_i \leq n。

    时空限制:22s / 512512MiB。

    Solution

    相当于是询问点集 VV 构成的虚树中,边权的最大值。

    一个区间的情况

    此时我们可以证明,区间 [l,r][l, r] 构成的虚树的边集,等价于所有 i,i+1i, i + 1(其中 l≤i<rl \leq i < r)之间简单路径边集的并。

    证明也很简单:对于一条虚树中的边,将其中一侧子树的点标记为 A 类点,另一侧子树的点标记为 B 类点。则区间 [l,r][l, r] 中必定有相邻的两个点来自不同的类。

    这样可以做到不漏但重复地统计,由于本题求的是最大值,所以不会有问题。

    于是记 aia_i 表示 i,i+1i, i + 1 之间简单路径上边权的最大值。查询只需查询 al,…,ar−1a_l, \dots, a_{r - 1} 的最大值即可。

    多个区间的情况

    现在考虑多个区间的情况,我们要考虑区间对区间的影响。如果我们将多个区间,顺次连接成一个区间,那么我们还是可以沿用刚刚查询相邻点贡献的最大值的思路。

    仔细思考可以发现也并不需要顺次连接:对于两个区间的情况,只需要从两个区间中各选一个点出来,查询即可。

    对于 kk 个区间的情况也是同理,先在第一个区间中任选一个点 pp,再在第 ii (2≤i≤k2 \leq i \leq k) 个区间中任选一个点出来和 pp 查询即可。

    显然这样也可以覆盖到所有虚树上的边。

    时间复杂度 O((n+∑k)log⁡n)\mathcal{O}((n + \sum k) \log n)。

    #include <bits/stdc++.h>
    
    #define debug(a) std::cout << #a << "=" << (a) << ' '
    
    using s64 = long long;
    using u64 = unsigned long long;
    
    /* 取 min */
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    /* 取 max */
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    /* ----- ----- ----- 正文 ----- ----- ----- */
    
    const int N = 200100;
    
    int n, Q;
    
    struct Graph {
        std::vector< std::vector< std::pair<int, int> > > table;
    
        void init(int _n) {
            table.assign(_n + 1, {});
        }
    
        void add_edge(int u, int v, int w) {
            table[u].push_back({v, w});
        }
    } G;
    
    int dep[N];
    int anc[18][N];
    int val[18][N];
    
    void dfs_init(int u, int fu) {
        dep[u] = dep[fu] + 1;
    
        anc[0][u] = fu;
        for (int i = 1; i <= 17; i ++) {
            anc[i][u] = anc[i - 1][anc[i - 1][u]];
            val[i][u] = std::max(val[i - 1][u], val[i - 1][anc[i - 1][u]]);
        }
    
        for (auto [v, w] : G.table[u]) {
            if (v == fu) {
                continue;
            }
            val[0][v] = w;
            dfs_init(v, u);
        }
    }
    
    int calc(int x, int y) {
        int ans = 0;
        if (dep[x] > dep[y]) std::swap(x, y);
        for (int i = 17; i >= 0; i --) {
            if (dep[x] <= dep[y] - (1 << i)) {
                chmax(ans, val[i][y]);
                y = anc[i][y];
            }
        }
        if (x == y) return ans;
        for (int i = 17; i >= 0; i --) {
            if (anc[i][x] ^ anc[i][y]) {
                chmax(ans, val[i][x]), chmax(ans, val[i][y]);
                x = anc[i][x], y = anc[i][y];
            }
        }
        chmax(ans, val[0][x]), chmax(ans, val[0][y]);
        return ans;
    }
    
    int a[N];
    
    namespace ST {
        int logn;
        std::vector< std::vector<int> > f;
    
        void init() {
            logn = std::__lg(n);
            f.assign(logn + 1, std::vector<int>(n + 1, 0));
            
            for (int i = 1; i <= n; i ++) {
                f[0][i] = a[i];
            }
            for (int j = 1; j <= logn; j ++) {
                for (int i = 1; i <= n - (1 << j) + 1; i ++) {
                    f[j][i] = std::max(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
                }
            }
        }
    
        int ask(int l, int r) {
            int k = std::__lg(r - l + 1);
            return std::max(f[k][l], f[k][r - (1 << k) + 1]);
        }
    }
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        std::cin >> n >> Q;
        
        G.init(n);
        for (int i = 1; i < n; i ++) {
            int x, y, z;
            std::cin >> x >> y >> z;
    
            G.add_edge(x, y, z), G.add_edge(y, x, z);
        }
    
        dfs_init(1, 0);
    
        for (int i = 1; i < n; i ++) {
            a[i] = calc(i, i + 1);
        }
    
        ST::init();
    
        while (Q --) {
            int k;
            std::cin >> k;
    
            int ans = 0;
            int p = -1;
            for (int i = 1; i <= k; i ++) {
                int l, r;
                std::cin >> l >> r;
    
                if (l < r) {
                    chmax(ans, ST::ask(l, r - 1));
                }
    
                if (p == -1) {
                    p = l;
                } else {
                    chmax(ans, calc(p, l));
                }
            }
    
            std::cout << ans << '\n';
        }
    
        return 0;
    }
    
    /**
     *  心中无女人
     *  比赛自然神
     *  模板第一页
     *  忘掉心上人
    **/