DCP-150 TLE

/*
ID:sabertooth9
TASK:DCP-150
LANG: C++14
*/
#include<bits/stdc++.h>
using namespace std;
#define ll              long long
#define pb              push_back
#define read()         freopen("input.txt","r",stdin)
#define write()        freopen("output.txt","w",stdout)
#define lead_zero(x)    __builtin_clzll(x)
#define trail_zero(x)   __builtin_ctz(x)
#define total_1s(x)     __builtin_popcount(x)
#define mod             100000007
#define all(v)          v.begin(),v.end()

const ll N=100000;

vector< pair<ll,ll> >v[N+9];
map<ll,pair<ll,ll>>mp;
//itr.first==child itr.second.first==parent itr.second.second==weight

void create()
{
    map<ll,pair<ll,ll>>::iterator itr;
    for(itr=mp.begin(); itr!=mp.end(); itr++)
    {
        v[itr->second.first].push_back(make_pair(itr->first,itr->second.second));
    }
}

/*void show()
{
    for(ll i=0; i<=N; i++)
        if(v[i].size())
        {
            cout<<"showing "<<i<<":"<<endl;
            for(ll j=0; j<v[i].size(); i++)
            {
                cout<<v[i][j].first<<" "<<v[i][j].second<<endl;
            }
        }
}

void show2()
{
    map<ll,pair<ll,ll>>::iterator itr;
    for(itr=mp.begin(); itr!=mp.end(); itr++)
    {
        cout<<"source: "<<itr->second.first<<" Child :"<<itr->first<<" Weight :"<<itr->second.second<<endl;
    }
}*/

ll solve(ll source,ll en)
{
    priority_queue<ll>pq;
    vector<ll>dis(N+9,mod);
    dis[source]=0;
    pq.push(source);
    while(!pq.empty())
    {
        ll t1=pq.top();
        pq.pop();
        for(ll i=0; i<v[t1].size(); i++)
        {
            if(dis[t1]+v[t1][i].second<dis[v[t1][i].first])
            {
                dis[v[t1][i].first]=dis[t1]+v[t1][i].second;
                pq.push(v[t1][i].first);
            }
        }
    }
    return dis[en];
}

void init(ll n)
{
    for(ll i=0;i<n;i++)
    {
        if(mp[i].first==0)
            mp[i].first=i;
    }
}

int main()
{
    read();
    write();
    ll n;
    scanf("%lld",&n);
    ll i,a,b;
    for(i=1; i<n; i++)
    {
        scanf("%lld",&a);
        //v[a].pb(make_pair(i+1,0));
        mp[i+1]=make_pair(a,0);
    }
    for(i=1; i<n; i++)
    {
        scanf("%lld",&a);
        mp[i+1].second=a;
    }
    //printf("%lld\n\n",mp[1].first);
    create();
    init(n);
    //show2();
    ll q;
    scanf("%lld",&q);
    while(q--)
    {
        scanf("%lld %lld",&a,&b);
        if(a==1)
        {
            mp[b].first=b;
            mp[b].second=0;
            create();
            init(n);
        }
        else
        {
            ll t=mp[b].first,x;
            while(1)
            {
                t=mp[t].first;
                if(t==mp[t].first)
                {
                    break;
                }
            }
            printf("%lld %lld\n",t,solve(t,b));
        }
    }
}