2021ICPC上海 H.Life is a Game Kruskal重构树

H.Life is a Game Kruskal重构树 题目分析

给定一张 n n n个点 m m m条边的无向图，以及 q q q个询问。对于每个询问，给定初始点和初始经验值，经过一条边要求当前经验值大于边权，经过一个点后点权累加至经验值。求能够获得的最大经验。

首先容易证明，对于最终的答案，两个点之间的所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = K r u s k a Kruska Kruskal 重构树上两点之间的 L C A LCA LCA 的权值

那么容易想到对原图建 K r u s k a l Kruskal Kruskal重构树，不妨先对样例建树：

红色数字表示 K r u s k a l Kruskal Kruskal重构树的点权，即为原图最大边权最小值。叶节点均为原图节点，黑色数字表示经验值，由于后期计算方便需要，将经验值自叶子节点向根节点求和。

那么我们对于某个询问，只需要从对应的叶节点开始往上跳到祖先节点，直至跳不过去(经验值小于点权(红色数字))，同时我们处理出了到达每个父节点能够获得的经验值(黑色数字)，这样只需要一路往上跳检查是否满足经验值大于 K r u s k a l Kruskal Kruskal重构树的点权值就可以了。

Code

#include 
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10;

int n, m, q;

int pnt[N], val[N];

struct unionfind{
    int par[N];
    unionfind(int n){ for(int i = 1; i > q;
    for(int i = 1; i > pnt[i];
    for(int i = 1; i > u >> v >> w;
        add_edge(i, u, v ,w);
    }
    n = kruskal();
    dfs0(n, 0);
    val[0] = 1e18;
    while(q--){
        int u, s; cin >> u >> s;
        int ans = pnt[u] + s;
        while(u != n){
            int t = u;
            for(int i = 19; i >= 0; i--)
                if(val[fa[u][i]]