o25_oct_ringroad

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
using pii = pair <int, int>;
const int N = 2e5 + 5;
vector <pii> g[N];
lli dis[N], qs[N];
int in_sect[N];
int n, k, Q;

void Update(int pst, int val){
    for(int i=pst;i<=k;i+=i&-i)
        dis[i] += (lli) val;
}

lli Sum(int pst, lli sum = 0){
    for(int i=pst;i>=1;i-=i&-i)
        sum += dis[i];
    return sum;
}

lli RangeSum(int s, int e){
    return Sum(e) - Sum(s - 1);
}

lli Ring(int u, int v){
    if(u > v) swap(u, v);
    lli a = RangeSum(u, v - 1);
    lli b = RangeSum(1, u - 1) + RangeSum(v, k);
    return min(a, b);
}

void dfs(int cur, int u, int p, lli d){
    qs[u] = d;
    in_sect[u] = cur;
    for(auto vw: g[u]){
        int v = vw.first;
        int w = vw.second;
        if(v != p)
            dfs(cur, v, u, d + (lli) w);
    }
}

lli Same(int u, int v){
    return abs(qs[u] - qs[v]);
}

int main(){

    scanf("%d %d %d", &n, &k, &Q);

    for(int i=1;i<=k;i++){
        int w;
        scanf("%d", &w);
        Update(i, w);
    }

    for(int u=k+1;u<=n;u++){
        int v, w;
        scanf("%d %d", &v, &w);
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    for(int u=1;u<=k;u++){
        dfs(u, u, u, 0);
    }

    for(int q=1;q<=Q;q++){
        int opr;
        scanf("%d", &opr);
        if(opr == 0){
            int u, w;
            scanf("%d %d", &u, &w);
            Update(u, -RangeSum(u, u));
            Update(u, w);
        }
        else if(opr == 1){
            int u, v;
            scanf("%d %d", &u, &v);
            if(in_sect[u] == in_sect[v]) printf("%lld\n", Same(u, v));
            else {
                printf("%lld\n", qs[u] + qs[v] + Ring(in_sect[u], in_sect[v]));
            }
        }
    }

    return 0;
}