Description

给定一颗 \(n\) 个点的树，带边权。

你可以选出一个包含 \(1\) 顶点的连通块，连通块的权值为连接块内这些点的边权和。

求一种选法，使得这个选法的权值是所有选法中第 \(k\) 小的。如果不存在第 \(k\) 小的那输出最大的。

答案对 \(998244353\) 取模。

Hint

• \(1\le n,k\le 10^5\)
• \(\text{边权} \in (0, 10^9]\)

Solution

考虑一个现有的选法，我们考虑如何得到一个新的 尽量小的更大的 选法。

• 将连通块边缘的一条边换下，用另一条与边缘边相邻的边替换。需要在保证新边的边权不小于旧的情况下，新边权最小。
• 在边缘新加入一条最小的边。

我们从初始的选法（只有顶点 \(1\)）开始，不断按上述策略拓展出新的选法。如果我们每次 优先拓展权值小的，那么在第 \(k\) 次拓展时我们就得到了答案。

那么现在的问题就是每次拓展如何选边。

我们考虑用一个 堆结构 将每个点所有可以拓展出去的边维护起来。

我们将选法视作一个个状态，每个状态都有一个堆维护 所有待拓展的边缘边。

那么上述两种策略可以转化为：

• 删去堆顶，然后换上新的堆顶。很显然就得到了一个次小选法。
• 选择堆顶对应边另一端的点，表示新拓展的顶点。将该顶点对应出边的边集 合并 到当前堆上。

这里设计到了堆的合并，又不得覆盖原来的信息，那么首选 可持久化左偏树 了。

最后复杂度 \(O((n+k)\log n + k\log k)\)。空间 \(O((n+k)\log n)\)。

Code

/*

 * Author : _Wallace_

 * Source : https://www.cnblogs.com/-Wallace-/

 * Problem : CH 弱省互测 Round #1 OVOO

 */

#include <algorithm>

#include <cstring>

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

const int N = 1e5 + 5;

const int mod = 998244353;

int n, k;

int f[N], v[N];

struct Edge {

    int to, nxt;

    int len;

} e[N];

int head[N], ecnt = 0;

inline void insert(int u, int v, int w) {

    e[ecnt] = Edge{v, head[u], w};

    head[u] = ecnt++;

}

namespace LefT {

    struct lef {

        int ch[2], dist;

        int end, val;

    } tr[N << 5];

    int total = 0;

    inline int create(int v, int e) {

        int x = ++total;

        tr[x] = lef{{0, 0}, 1, e, v};

        return x;

    }

    inline int copy(int x) {

        return tr[++total] = tr[x], total;

    }

    int merge(int x, int y) {

        if (!x || !y) return x | y;

        if (tr[x].val > tr[y].val) swap(x, y);

        int z = copy(x);

        tr[z].ch[1] = merge(tr[x].ch[1], y);

        if (tr[tr[z].ch[0]].dist < tr[tr[z].ch[1]].dist)

            swap(tr[z].ch[0], tr[z].ch[1]);

        tr[z].dist = tr[tr[z].ch[1]].dist + 1;

        return z;

    }

};

int root[N];

void prework(int x) {

    using namespace LefT;

    for (int i = head[x]; ~i; i = e[i].nxt) {

        int y = e[i].to, l = e[i].len;

        root[x] = merge(root[x], create(l, y));

        prework(y);

    }

}

struct statu {

    int x; long long v;

    inline bool operator < (const statu& rhs) const {

        return v > rhs.v;

    }

}; priority_queue<statu> pq;

signed main() {

    ios::sync_with_stdio(false);

    memset(head, -1, sizeof(head));

    cin >> n >> k;

    for (int i = 2; i <= n; i++) {

        cin >> f[i] >> v[i];

        insert(f[i], i, v[i]);

    }

    prework(1);

    using namespace LefT;

    long long ans = 0ll;

    pq.push(statu{root[1], tr[root[1]].val});

    for (--k; k && !pq.empty(); --k) {

        int x = pq.top().x;

        long long val = pq.top().v;

        pq.pop(), ans = val;

        int cur = merge(tr[x].ch[0], tr[x].ch[1]);

        if (cur) pq.push(statu{cur, val - tr[x].val + tr[cur].val});

        cur = merge(cur, root[tr[x].end]);

        if (cur) pq.push(statu{cur, val + tr[cur].val});

    }

    cout << ans % mod << endl;

}