o25_ringroad

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

int const K = 200010;
ll seg[4*K];
int k = 0;

void update(int idx,ll diff,int p = 1,int b = 1,int e = k){
    if(idx < b || idx > e)return;
    seg[p] += diff;

    if(b == e)return;
    int m = (b+e)/2;
    update(idx,diff,p*2,b,m);
    update(idx,diff,p*2+1,m+1,e);
    seg[p] = seg[p*2] + seg[p*2+1];
}

ll query(int l,int r,int p = 1,int b = 1,int e = k){
    if(r < b || l > e)return 0;
    if(l <= b && e <= r)return seg[p];
    int m = (b+e)/2;
    return query(l,r,p*2,b,m) + query(l,r,p*2+1,m+1,e);
}

int main()
{
    //freopen("input.txt","r",stdin);
    int n,Q;
    scanf("%d %d %d",&n,&k,&Q);

    ll MinDist[n+1];
    int MainIdx[n+1];
    ll MainRoad[k+1];
    ll SumMainRoad = 0;
    for(int i = 1 ; i <= n ; i ++){
        if(i <= k){ //Main station
            ll value;
            scanf("%lld",&value);
            MainRoad[i] = value;
            SumMainRoad += value;
            MinDist[i] = 0;
            MainIdx[i] = i;
            update(i,value);
        }
        else{ // Sub station
            int next;
            ll value;
            scanf("%d %lld",&next,&value);
            MainIdx[i] = MainIdx[next];
            MinDist[i] = MinDist[next] + value;
        }
    }
    for(int q = 0 ; q < Q ; q ++){
        int op;
        scanf("%d",&op);
        if(op == 1){ //Query
            int x,y;
            scanf("%d %d",&x,&y);
            if(MainIdx[x] > MainIdx[y])swap(x,y);
            if(MainIdx[x] == MainIdx[y])printf("%lld\n",abs(MinDist[x]-MinDist[y])); //Co-Main
            else{
            //  printf("Test query(%d,%d)\n",MainIdx[x],MainIdx[y]-1);
                ll Direct = query(MainIdx[x],MainIdx[y]-1);
            //  printf("SumMainRoad = %lld , Direct = %lld ,Sum = %lld + %lld + %lld = ",SumMainRoad,Direct,MinDist[x],min(SumMainRoad - Direct,Direct),MinDist[y]);
                printf("%lld\n",MinDist[x] + min(SumMainRoad - Direct,Direct) + MinDist[y]);
            }
        }
        else if(op == 0){ //Update
            int idx;
            ll value;
            scanf("%d %lld",&idx,&value);
            update(idx,value - MainRoad[idx]);
            SumMainRoad += value - MainRoad[idx];
            MainRoad[idx] = value;
        }
    }
    return 0;
}