2021icpc Shanghai h.life is a game Kruskal reconstruction tree

H.Life is a Game Kruskal Refactoring tree

Topic analysis

Given a sheet $n$ A little bit $m$ Undirected graph of strip and edge , as well as $q$ A asked . For each inquiry , Given initial point and initial empirical value , Passing through an edge requires the current experience value to be greater than the edge weight , After a point, the point weight is accumulated to the empirical value . Seek the greatest experience you can get .

First, it's easy to prove , For the final answer , The minimum value of the maximum edge weight on all simple paths between two points = The maximum value on the simple path between two points on the minimum spanning tree = $Kruska$l Refactoring between two points on the tree $LCA$ A weight

It's so easy to think of building the original drawing $Kruskal$ Refactoring tree , You might as well build a tree for the example first ：

Red numbers indicate $Kruskal$ Point weight of reconstruction tree , That is, the minimum value of the maximum edge weight of the original graph . All leaf nodes are nodes of the original drawing , Black numbers represent empirical values , Due to the convenience of later calculation , Sum the empirical values from the leaf node to the root node .

So we have a question , Just from The corresponding leaf node starts to jump up to the ancestor node , Until I can't jump ( Experience value is less than point weight ( Red numbers )), At the same time, we deal with the experience value that can be obtained when reaching each parent node ( Black numbers ), In this way, you only need to jump up all the way to check whether the experience value is greater than $Kruskal$ Just reconstruct the point weight of the tree .

Code

#include <bits/stdc++.h>
#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 <= n; i++) par[i] = i; }
    int find(int x){
     return x == par[x] ? x : (par[x] = find(par[x])); }
    void merge(int u, int v){
    
        int fau = find(u), fav = find(v);
        if(fau != fav) par[fav] = fau;
    }
    int ismerge(int u, int v){
     return find(u) == find(v); }
};

vector<int> g[N];

namespace KR{
    
    struct edge{
    
        int u, v ,w;
        const bool operator< (const edge &x) const {
     return w < x.w; }
    }edges[N];

    inline void add_edge(int i, int u, int v, int w){
     edges[i] = {
    u ,v, w}; }

    int kruskal(){
    
        int tot = n, cnt = 0;
        unionfind uf(n + 20);
        sort(edges + 1, edges + 1 + m);
        for(int i = 1; i <= m; i++){
    
            int nu = edges[i].u, nv = edges[i].v, nw = edges[i].w;
            int fau = uf.find(nu), fav = uf.find(nv);
            if(fau != fav){
    
                val[++tot] = edges[i].w;
                uf.par[tot] = uf.par[fau] = uf.par[fav] = tot;
                g[fau].emplace_back(tot), g[fav].emplace_back(tot);
                g[tot].emplace_back(fau), g[tot].emplace_back(fav);
                cnt++;
            }
            if(cnt == n - 1) break;
        }
        return tot;
    }
}

int fa[N][20];

void dfs0(int u, int ufa){
    
    fa[u][0] = ufa;
    for(int i = 1; i < 20; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(auto v : g[u]){
    
        if(v == ufa) continue;
        dfs0(v, u);
        pnt[u] += pnt[v];
    }
}

using KR::add_edge;
using KR::kruskal;

inline void solve(){
    
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++) cin >> pnt[i];
    for(int i = 1; i <= m; i++){
    
        int u, v, w; cin >> 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]] <= ans) u = fa[u][i];
            if(t == u) break;
            ans = pnt[u] + s;
        }
        cout << ans << endl;
    }
}  

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    solve();
    return 0;
}