#include<bits/stdc++.h> #define ll long long #define fi first #define se second #define ins insert #define pb push_back #define foru(i,a,b) for(int i=a;i<=b;i++) #define ford(i,a,b) for(int i=a;i>=b;i--) #define pii pair<int,int> #define pll pair<ll,ll> #define int ll using namespace std; int const block=330; int n,R,nq,c[200005]; int cntc[200005]; vector<int> adj[200005]; int id[200005],dp[200005],same[200005]; ll ans[200005]; int cnt,tt[200005],sz[200005]; int bit[200005]; vector<int> id1[200005],id2[200005],vv[200005]; vector<pair<int,int>> query1[200005],query2[200005]; vector<pair<pair<int,int>,int>> query; int res=0; void dfs1(int u,int par,int color) { if(c[u]==color) { res++; } ans[id[c[u]]]+=res; // cout<<'!'<<id[c[u]]<<' '<<res<<endl; for(auto v:adj[u]) { if(v==par) continue; dfs1(v,u,color); } if(c[u]==color) { res--; } } void dfs2(int u,int par,int color) { dp[u]=0; if(c[u]==color) dp[u]++; for(auto v:adj[u]) { if(v==par) continue; dfs2(v,u,color); dp[u]+=dp[v]; } ans[id[c[u]]]+=dp[u]; } void dfs(int u,int par) { cnt++; tt[u]=cnt; sz[u]=1; for(auto v:adj[u]) { if(v==par) continue; dfs(v,u); sz[u]+=sz[v]; } } void update(int u, int v) { int idx = u; while (idx <= n) { bit[idx] += v; idx += (idx & (-idx)); } } int getSum(int p) { int idx = p, ans = 0; while (idx > 0) { ans += bit[idx]; idx -= (idx & (-idx)); } return ans; } int get(int l,int r) { return getSum(r)-getSum(l-1); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); // freopen(".inp","r",stdin); // freopen(".out","w",stdout); cin>>n>>R>>nq; cin>>c[1]; cntc[c[1]]++; vv[c[1]].pb(1); for(int i=2;i<=n;i++) { int x; cin>>x; adj[x].pb(i); adj[i].pb(x); cin>>c[i]; cntc[c[i]]++; vv[c[i]].pb(i); } for(int i=1;i<=nq;i++) { int r1,r2; cin>>r1>>r2; // if(r1==r2) // { // while(true) // { // cout<<"DMM"<<endl; // } // } if(cntc[r1]>=block) { query1[r1].pb({r2,i}); } else // { if(cntc[r2]>=block) { query2[r2].pb({r1,i}); } else { query.pb({{r1,r2},i}); } // } } for(int u=1;u<=R;u++) { if(query1[u].empty()) continue; for(auto o:query1[u]) { int v=o.fi,i=o.se; if(id[v]==0) id[v]=i; else same[i]=id[v]; } res=0; dfs1(1,0,u); for(auto o:query1[u]) { int v=o.fi,i=o.se; id[v]=0; } } for(int u=1;u<=R;u++) { if(query2[u].empty()) continue; for(auto o:query2[u]) { int v=o.fi,i=o.se; if(id[v]==0) id[v]=i; else same[i]=id[v]; } res=0; dfs2(1,0,u); for(auto o:query2[u]) { int v=o.fi,i=o.se; id[v]=0; } } dfs(1,0); for(auto o:query) { int r1=o.fi.fi,r2=o.fi.se,id=o.se; for(auto u:vv[r2]) { update(tt[u],1); } for(auto u:vv[r1]) { ans[id]+=get(tt[u],tt[u]+sz[u]-1); } for(auto u:vv[r2]) { update(tt[u],-1); } } for(int i=1;i<=nq;i++) { if(same[i]!=0) cout<<ans[same[i]]<<'\n'; else cout<<ans[i]<<'\n'; } } /* em thi cho du co khoc cung se den ngay phai quen thien duong van cho ngay em den */