「Ynoi2006」rldcot

发表于 分类于 本文字数： 965 阅读时长 ≈ 4 分钟

Description

Link：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)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#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
*/