「Ynoi2006」rldcot

    「Ynoi2006」rldcot

    Luogu P7880

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

    定义 depx\mathrm{dep}_x 表示节点 xx 到根的简单路径上的边权和。

    有 QQ 次查询,每次查询给出两个参数 l,rl, r,对于所有满足 l≤i,j≤rl \leq i, j \leq r 的二元组 (i,j)(i, j),你需要求出有多少种不同的 depLCA(i,j)\mathrm{dep}_{\mathrm{LCA}(i, j)}。

    数据范围:1≤n≤1051 \leq n \leq 10^5,1≤Q≤5×1051 \leq Q \leq 5 \times 10^5,−109≤w≤109-10^9 \leq w \leq 10^9,1≤l≤r≤n1 \leq l \leq r \leq n。

    时空限制:500500ms / 512512MiB。

    Solution

    一个简单的想法是:若 a<b<c<da < b < c < d 且 LCA(a,d)=LCA(b,c)=x\mathrm{LCA}(a, d) = \mathrm{LCA}(b, c) = x,那么 (b,c)(b, c) 是一定比 (a,d)(a, d) 更优秀的。

    对于树上的一个节点 uu,我们想要求出一些但不多的二元组 (i,j)(i, j),满足 LCA(i,j)=u\mathrm{LCA}(i, j) = u 并且能覆盖到所有情况(查询时如果漏数了一个二元组,那么一定是有一个更优秀的二元组被数到)。

    首先 i,ji, j 必须来自 uu 的不同子树,这启发我们在树上进行启发式合并,使用 std::set 维护每棵子树的点集。每次合并两棵子树时,我们枚举较小子树的每一个点 xx,在较大子树的 std::set 中查询分别查询 xx 的前驱 pre\mathrm{pre} 后继 net\mathrm{net},将 (pre,x),(x,suf)(\mathrm{pre}, x), (x, \mathrm{suf}) 加入 uu 所拥有的二元组。

    这样我们就将二元组个数从 O(n2)O(n^2) 降到了 O(nlog⁡n)O(n \log n)!

    By the Way:也可以使用 LCT 的 access 操作,求出 O(nlog⁡n)O(n \log n) 个二元组。详见 LOJ 6041 的算法三。

    剩余的部分就是很朴素的扫描线了,不过多赘述。

    时间复杂度 O(nlog⁡2n+mlog⁡n)\mathcal{O}(n \log^2 n + m \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 = 100100, MaxQ = 500100;
    
    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;
    
    s64 dist[N];
    int id[N];
    
    int len;
    s64 mapval[N];
    
    int turn(s64 x) {
        return std::lower_bound(mapval + 1, mapval + 1 + len, x) - mapval;
    }
    
    void dfs_init(int u, int fu) {
        for (auto [v, w] : G.table[u]) {
            if (v == fu) continue;
            dist[v] = dist[u] + w;
            dfs_init(v, u);
        }
    }
    
    std::set<int> g[N];
    
    std::vector< std::pair<int, int> > scan[N];
    
    std::vector< std::pair<int, int> > qry[N];
    int ans[MaxQ];
    
    int lst[N];
    
    namespace BIT {
        int c[N];
    
        void add(int x, int y) {
            for (; x <= n; x += x & -x) {
                c[x] += y;
            }
        }
    
        int ask(int x) {
            int ans = 0;
            for (; x; x -= x & -x) {
                ans += c[x];
            }
            return ans;
        }
    }
    
    void dfs(int u, int fu) {
        g[u].insert(u);
        scan[u].push_back({u, id[u]});
    
        for (auto [v, _] : G.table[u]) {
            if (v == fu) continue;
    
            dfs(v, u);
    
            if (g[u].size() < g[v].size()) {
                std::swap(g[u], g[v]);
            }
    
            for (int x : g[v]) {
                auto it = g[u].lower_bound(x);
                if (it != g[u].end()) {
                    scan[*it].push_back({x, id[u]});
                }
                if (it != g[u].begin()) {
                    it --;
                    scan[x].push_back({*it, id[u]});
                }
            }
            for (int x : g[v]) {
                g[u].insert(x);
            }
            // g[v].clear();
        }
    }
    
    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 ++) mapval[++ len] = dist[i];
        std::sort(mapval + 1, mapval + 1 + len);
        len = std::unique(mapval + 1, mapval + 1 + len) - mapval - 1;
        for (int i = 1; i <= n; i ++) id[i] = turn(dist[i]);
    
        dfs(1, 0);
    
        for (int i = 1; i <= Q; i ++) {
            int l, r;
            std::cin >> l >> r;
    
            qry[r].push_back({l, i});
        }
    
        for (int i = 1; i <= n; i ++) {
            for (auto [l, v] : scan[i]) {
                if (l > lst[v]) {
                    if (lst[v]) BIT::add(lst[v], -1);
                    BIT::add(l, +1);
                    lst[v] = l;
                }
            }
            for (auto [l, id] : qry[i]) {
                ans[id] = BIT::ask(i) - BIT::ask(l - 1);
            }
        }
    
        for (int i = 1; i <= Q; i ++) {
            std::cout << ans[i] << '\n';
        }
    
        return 0;
    }
    
    /**
     *  心中无女人
     *  比赛自然神
     *  模板第一页
     *  忘掉心上人
    **/
    
    /*
    10 1
    9 1 -4
    9 8 2
    8 10 5
    9 7 -3
    1 4 2
    10 2 5
    10 5 -1
    7 3 -3
    10 6 5
    1 2
    */