2021ICPC上海 H.Life is a Game （kruskal重构树、倍增）

题目链接：LifeisaGame
$n$ 个点，$m$ 条边的无向连通图。
每个点上有个能力值，经过点时可以获得该能力值 $ai$，但每个点只能获得一次。
每条边上有个能力值限制 $wi$，只有当能力值超过 $wi$ 时才能通过这条边。
有 $Q$ 次询问，每次询问给出初始位置 $x$ 和初始能力值 $k$，询问能获得的最大能力值是多少。
$n,m,q<=1e5,ai<=1e4,wi<=1e9$

qwq铁了赛上读了今天才补题 之前其实听过重构树但是觉得啊不用学的啦
题解：
$kruskal$重构树就是一颗二叉树 原先的点都是叶子节点
$LCA(u,v)$的权值是 原图 $u$ 到 $v$ 路径上最大/小边权的最小/大值(由建树时边权的排序方式决定)
因为这个我们可以找存能量值为边集，然后用链上所需要的能量值max来判断能不能取得这个能量值
q1e5所以要一个 $log$ 查询
因为是贪心的存一个虚拟的点再往上，所以只要能上去就能走到另一边

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n, m, q;
int a[N];
int fa[N];
int f[N][31], cost[N][31];
struct node {
    int u, v, w;
}e[N];
bool cmp(node a, node b) {
    return a.w<b.w;
}
int findf(int x) {
    if(fa[x]==x) return x;return fa[x]=findf(fa[x]);
}
int cnt;
void kruskal() {
    cnt=n;int tot=0;for(int i=1; i<=n+n; i++) fa[i]=i;for(int i=1; i<=m; i++) {
    int w=e[i].w;int u=findf(e[i].u);int v=findf(e[i].v);if(u!=v) {
    a[++cnt]=a[u]+a[v];fa[u]=fa[v]=f[u][0]=f[v][0]=cnt;cost[u][0]=w-a[u];cost[v][0]=w-a[v];++tot;}if(tot==n-1) break;}
}
signed main() {
    cin>>n>>m>>q;for(int i=1; i<=n; i++) cin>>a[i];for(int i=1; i<=m; i++) cin>>e[i].u>>e[i].v>>e[i].w;sort(e+1, e+1+m, cmp);kruskal();a[0]=a[cnt];//没懂没写上ggint lg=log2(cnt)+1;for(int j=1; j<=lg; j++) {
    for(int i=1; i<=cnt; i++) {
    f[i][j]=f[f[i][j-1]][j-1];cost[i][j]=max(cost[i][j-1], cost[f[i][j-1]][j-1]);//两半的max}}while(q--) {
    int x, k;cin>>x>>k;for(int i=lg; i>=0; i--) if(cost[x][i]<=k) x=f[x][i];cout<<a[x]+k<<endl;}return 0;
}

总结

提示：这里对文章进行总结：
例如：以上就是今天要讲的内容，本文仅仅简单介绍了pandas的使用，而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。