「2022 ICPC 沈阳站」G. Meet in the Middle

发表于 分类于 本文字数： 1.3k 阅读时长 ≈ 5 分钟

Description

Link：gym104160 G

给出两棵大小均为 nn 的树，节点编号均为 1∼n1 \sim n，边带正权。

有 QQ 次询问，每次询问给出两个正整数 a,ba, b (1≤a,b≤n1 \leq a, b \leq n)，你需要找到一个节点 xx，使得 xx 在第一棵树上到 aa 的距离加上 xx 在第二棵树上到 bb 的距离之和最大，你只需要求出这个最大值即可。

数据范围：1≤n≤1051 \leq n \leq 10^5，1≤q≤5×1051 \leq q \leq 5 \times 10^5，1≤w≤1091 \leq w \leq 10^9。

时空限制：55s / 512512MiB。

Solution

考虑离线处理询问。在第一棵树上 dfs 询问点 aa，假设在第二棵树上的每个点 xx 下面都挂一个新点 x′x' 且边权为 dist1(a,x)\mathrm{dist}_1(a, x)，那么问题就转化为了查询新树上关于 bb 的最远点。最远点必定是新树直径的两个端点之一，问题就转化成了动态维护新树的直径。

对第一棵树的 dfs 序建线段树，线段树上的每个节点都维护了第一棵树上的 dfs 序在该区间内的所有点，对应到第二棵树上的点集直径（只需要维护直径的两个端点，以及对应的 dist1(a,x)\mathrm{dist}_1(a, x) 即可）。两个点集直径的合并是经典套路。

当 aa 在第一棵树上移动时（例如走向某个子树 vv），子树 vv 内的所有点的 dist1(a,x)\mathrm{dist}_1(a, x) 都会全体减去边长 ww，子树 vv 外的所有点都会全体加上边长 ww。对应到线段树上就是区间加，我们只需在线段树上走的同时触发区间点集直径的更新即可，那些未触发更新的区间只是整体加减一个值，并不改变直径的端点，只需打上懒标记即可。

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

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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
#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 = 100100, MaxQ = 500100;

int n, Q;
std::vector<std::vector< std::pair<int, int> >> G1, G2;

i64 dist1[N];

int dfsClock, dfn[N], idx[N];
int sze[N];

void dfs1_init(int u, int fu) {
    dfsClock ++;
    dfn[u] = dfsClock, idx[dfsClock] = u;

    sze[u] = 1;
    for (auto [v, w] : G1[u]) {
        if (v == fu) {
            continue;
        }
        dist1[v] = dist1[u] + w;
        dfs1_init(v, u);
        sze[u] += sze[v];
    }
}

int dep2[N];
i64 dist2[N];

int Fir[N];
std::vector<int> eul;

void dfs2_init(int u, int fu) {
    dep2[u] = dep2[fu] + 1;
    Fir[u] = eul.size(), eul.push_back(u);
    for (auto [v, w] : G2[u]) {
        if (v == fu) {
            continue;
        }
        dist2[v] = dist2[u] + w;
        dfs2_init(v, u);
        eul.push_back(u);
    }
}

namespace eulST {
    int n, t;
    std::vector<std::vector<int>> f;

    inline int op(int x, int y) {
        return dep2[x] < dep2[y] ? x : y;
    }

    void init() {
        n = eul.size(), t = std::__lg(n);
        f.assign(t + 1, std::vector<int>(n, 0));

        for (int i = 0; i < n; i ++) {
            f[0][i] = eul[i];
        }
        for (int j = 1; j <= t; j ++) {
            for (int i = 0; i + (1 << j) - 1 < n; i ++) {
                f[j][i] = op(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 op(f[k][l], f[k][r - (1 << k) + 1]);
    }
}

int lca(int x, int y) {
    auto [l, r] = std::minmax(Fir[x], Fir[y]);
    return eulST::ask(l, r);
}
i64 distance2(int x, int y) {
    return dist2[x] + dist2[y] - 2 * dist2[lca(x, y)];
}

struct Info {
    int p, q;
    i64 a, b;
    
    Info() {}
    Info(int _p, int _q, i64 _a, i64 _b) : p(_p), q(_q), a(_a), b(_b) {}

    void mk_add(i64 x) {
        a += x, b += x;
    }

    friend Info operator + (Info lhs, Info rhs) {
        Info self;
        i64 mx = 0;

        auto upd = [&] (int p, int q, i64 a, i64 b) {
            i64 x = a + b + distance2(p, q);
            if (x > mx) {
                mx = x;
                self = Info(p, q, a, b);
            }
        };
        upd(lhs.p, lhs.q, lhs.a, lhs.b);
        upd(rhs.p, rhs.q, rhs.a, rhs.b);
        upd(lhs.p, rhs.p, lhs.a, rhs.a);
        upd(lhs.p, rhs.q, lhs.a, rhs.b);
        upd(lhs.q, rhs.p, lhs.b, rhs.a);
        upd(lhs.q, rhs.q, lhs.b, rhs.b);

        return self;
    }
};

namespace SGT {
    struct node {
        Info info;
        i64 add;
        void mk_add(i64 x) {
            info.mk_add(x);
            add += x;
        }
    } t[N * 4];

    void upd(int p) {
        t[p].info = t[p * 2].info + t[p * 2 + 1].info;
    }

    void spread(int p) {
        if (t[p].add) {
            t[p * 2].mk_add(t[p].add), t[p * 2 + 1].mk_add(t[p].add);
            t[p].add = 0;
        }
    }

    void build(int p, int l, int r) {
        if (l == r) {
            int u = idx[l];
            t[p].info = Info(u, u, dist1[u], dist1[u]);
            return;
        }
        int mid = (l + r) >> 1;
        build(p * 2, l, mid), build(p * 2 + 1, mid + 1, r);
        upd(p);
    }

    void change(int p, int l, int r, int s, int e, i64 x) {
        if (s <= l && r <= e) {
            t[p].mk_add(x);
            return;
        }
        spread(p);
        int mid = (l + r) >> 1;
        if (s <= mid) {
            change(p * 2, l, mid, s, e, x);
        }
        if (mid < e) {
            change(p * 2 + 1, mid + 1, r, s, e, x);
        }
        upd(p);
    }

    i64 ask(int x) {
        auto [p, q, a, b] = t[1].info;
        i64 mx = 0;
        chmax(mx, a + distance2(x, p));
        chmax(mx, b + distance2(x, q));
        return mx;
    }
}

std::vector<std::pair<int, int>> lay[N];
i64 ans[MaxQ];

void solve(int u, int fu) {
    for (auto [p, id] : lay[u]) {
        ans[id] = SGT::ask(p);
    }

    for (auto [v, w] : G1[u]) {
        if (v == fu) {
            continue;
        }
        int l = dfn[v], r = dfn[v] + sze[v] - 1;

        SGT::change(1, 1, n, l, r, -w);
        if (l > 1) SGT::change(1, 1, n, 1, l - 1, +w);
        if (r < n) SGT::change(1, 1, n, r + 1, n, +w);

        solve(v, u);

        SGT::change(1, 1, n, l, r, +w);
        if (l > 1) SGT::change(1, 1, n, 1, l - 1, -w);
        if (r < n) SGT::change(1, 1, n, r + 1, n, -w);
    }
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    std::cin >> n >> Q;

    G1.assign(n + 1, {}), G2.assign(n + 1, {});
    for (int i = 1; i < n; i ++) {
        int x, y, z;
        std::cin >> x >> y >> z;
        G1[x].push_back({y, z}), G1[y].push_back({x, z});
    }
    for (int i = 1; i < n; i ++) {
        int x, y, z;
        std::cin >> x >> y >> z;
        G2[x].push_back({y, z}), G2[y].push_back({x, z});
    }

    dfs1_init(1, 0);
    dfs2_init(1, 0);
    eulST::init();

    SGT::build(1, 1, n);

    for (int i = 1; i <= Q; i ++) {
        int a, b;
        std::cin >> a >> b;
        lay[a].push_back({b, i});
    }

    solve(1, 0);

    for (int i = 1; i <= Q; i ++) {
        std::cout << ans[i] << '\n';
    }

    return 0;
}