P12692 BZOJ3784 树上的路径 题解

namespace lowspeed_song {

inline void init() {
}

vector<pair<int, int>> adj[N];
int st[20][N], dep[N], dis[N], dfn[N], timestamp, lg[N];
inline int get(int x, int y) { return dfn[x] < dfn[y] ? x : y; }
inline void dfs(int u, int fa) {
    st[0][dfn[u] = ++timestamp] = fa, dep[u] = dep[fa] + 1;
    for (auto &[v, w] : adj[u]) if (v != fa) dis[v] = dis[u] + w, dfs(v, u); 
}
inline int lca(int u, int v) {
    if (u == v) return u;
    u = dfn[u], v = dfn[v];
    if (u > v) swap(u, v);
    int lgx = lg[v - u++];
    return get(st[lgx][u], st[lgx][v - (1 << lgx) + 1]);
}
inline int dist(int a, int b) { return dis[a] + dis[b] - 2 * dis[lca(a, b)]; }
struct Info {
    // i --> [l, r]  分治点是 e  代价为 val
    int i, e, l, r, val;
    inline bool operator<(const Info &r) const {
        return val < r.val;
    }
};

struct Node {
    int l, r, u, v;
    inline void init(int p) { l = r = u = v = p; }
} tree[N << 2];

inline Node operator+(const Node &l, const Node &r) {
    Node res;
    res.l = l.l, res.r = r.r;
    int v1 = dist(l.u, l.v), v2 = dist(r.u, r.v);
    int v3 = dist(l.u, r.u), v4 = dist(l.u, r.v);
    int v5 = dist(l.v, r.u), v6 = dist(l.v, r.v);
    int mx = max({v1, v2, v3, v4, v5, v6});
    if (mx == v1) res.u = l.u, res.v = l.v;
    else if (mx == v2) res.u = r.u, res.v = r.v;
    else if (mx == v3) res.u = l.u, res.v = r.u;
    else if (mx == v4) res.u = l.u, res.v = r.v;
    else if (mx == v5) res.u = l.v, res.v = r.u;
    else res.u = l.v, res.v = r.v;
    return res;
}

inline void build(int l, int r, int rt) {
    if (l == r) return tree[rt].init(l);
    int mid = l + r >> 1;
    build(l, mid, rt << 1), build(mid + 1, r, rt << 1 | 1);
    tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

inline Node qry(int rt, int ll, int rr) {
    int &l = tree[rt].l, &r = tree[rt].r;
    if (ll <= l && r <= rr) return tree[rt];
    int mid = l + r >> 1;
    if (ll <= mid && mid < rr) return qry(rt << 1, ll, rr) + qry(rt << 1 | 1, ll, rr);
    if (ll <= mid) return qry(rt << 1, ll, rr);
    return qry(rt << 1 | 1, ll, rr);
}

inline int get(int u, int l, int r) {
    Node info = qry(1, l, r);
    int v1 = dist(u, info.u), v2 = dist(u, info.v);
    if (v1 > v2) return info.u;
    return info.v;
}

inline void sol([[maybe_unused]]int __testcase_id) {
    int n, m; cin >> n >> m;
    lg[0] = -1;
    for (int i = 1; i < N; ++i) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i < n; ++i) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].emplace_back(b, c), adj[b].emplace_back(a, c);
    } dfs(1, 0);
    for (int i = 1; i < 20; ++i)
        for (int j = 1; j <= n; ++j) st[i][j] = get(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    priority_queue<Info> q;
    build(1, n, 1);
    // cout << "LCA: ";
    // cout << lca(4, 5) << ' ' << lca(5, 3) << '\n';
    function<void(int, int, int)> ins = [&](int pos, int l, int r) {
        int e = get(pos, l, r);
        q.push({pos, e, l, r, dist(pos, e)});
    };
    for (int i = 1; i < n; ++i) ins(i, i + 1, n);
    while (m--) {
        auto [i, e, l, r, val] = q.top();
        q.pop();
        cout << val << '\n';
        if (l != e) ins(i, l, e - 1);
        if (r != e) ins(i, e + 1, r);
    }
}

} // namespace lowspeed_song