传送门

倍增做
f[u][k]表示从u开始跳2的k次方到哪个节点
mx[u][k]表示从u开始跳2的k次方最少需要多少权值

#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int N=2e5+10;
int f[N][21],ma[N][21],a[N],b[N],n,m,q,u,k,p[N];
struct node{
    int u,vv,w;
    bool operator<(const node&t){
        return w<t.w;
    }
};
vector<node>v;
vector<int>g[N];
int find(int x){
    if(p[x]==x)return p[x];
    return p[x]=find(p[x]);
}
void dfs(int u,int fa=0){
    f[u][0]=fa;
    for(int i=1;i<=20;i++)f[u][i]=f[f[u][i-1]][i-1];
    for(auto j:g[u]){
        dfs(j,u);
        a[u]+=a[j];
    }
}
void dfs2(int u,int fa=0){
    ma[u][0]=b[fa]-a[u];
    for(int i=1;i<=20;i++){
        ma[u][i]=max(ma[u][i-1],ma[f[u][i-1]][i-1]);
    }
    for(auto j:g[u]){
        dfs2(j,u);
    }
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=n+m;i++)p[i]=i;
    for(int i=1;i<=n;i++)cin>>a[i];
    while(m--){
        int u,vv,w;
        cin>>u>>vv>>w;
        v.push_back({u,vv,w});
    }
    sort(v.begin(),v.end());
    for(auto t:v){
        int u=t.u;
        int v=t.vv;
        int w=t.w;
        u=find(u),v=find(v);
        if(u==v)continue;
        n++;
        b[n]=w;
        p[u]=p[v]=n;
        g[n].push_back(u),g[n].push_back(v);
    }
    dfs(n);
    b[0]=2e9+1;
    dfs2(n);
    while(q--){
        cin>>u>>k;
        for(int i=20;i>=0;i--){
            if(k>=ma[u][i])u=f[u][i];
        }
        cout<<a[u]+k<<'\n';
    }
}