今回は、全ての加算の後に全ての質問が来ることを利用して過剰な \(\log\) を回避する解法を説明します。

まず、 \(Q\) 回の加算を処理します。

根を \(r\) とする木上の \(u-v\) パスにある操作をかけたい場合、操作を以下のように言い換えることができます。

• \(r-u\) パスに操作をかける。
• \(r-v\) パスに操作をかける。
• \(u,v\) の LCA (最小共通祖先) を \(l\) としたとき、 \(r-l\) パスにて操作を ( \(2\) 回分) 解除する。

本問 ( \(u-v\) に \(1\) 加算) の場合、累積和の考えも利用して以下の通りにできます。

• 長さ \(N\) の配列 \((\Delta_1,\Delta_2,\dots,\Delta_N)\) を用意する。はじめ、全ての要素は \(0\) である。
• \(\Delta_u\) に \(1\) 加算する。
• \(\Delta_v\) に \(1\) 加算する。
• \(u,v\) の LCA (最小共通祖先) を \(l\) としたとき、 \(\Delta_l\) から \(2\) 減算する。
• 全ての加算が終わった後、各頂点 \(v\) について葉から順に以下を行う(本問では \(P_i < i\) なので、頂点 \(N,N-1,\dots,1\) の順に行えばよいです)。
  • この時点での \(\Delta_v\) が \(v-P_v\) 辺に加算される値である。
  • その後、 \(\Delta_{P_v}\) に \(\Delta_v\) を加算する。

こうして各辺の耐久値を求める方法が分かりました。
次に \(R\) 回の質問を処理しましょう。

ここで、ダブリングによる LCA の求解を思い出しましょう (参考1 参考2)。

ダブリングによる LCA では、 \({\rm vertex}[k][v] = \{\) 頂点 \(v\) から \(2^k\) だけ上に辿った頂点 \(\}\) を構築しました。
\({\rm weight}[k][v] = \{\) 頂点 \(v\) から \(2^k\) だけ上に辿るときに通る辺の耐久値の最小値 \(\}\) を考えます。

\({\rm weight}\) の構築は \({\rm vertex}\) と同様の方法で行うことができます。
\(a,b\) の LCA を求める際に辺を登っていくことになりますが、その際一気に通過した辺の重みの最小値を参照することで、パス内の最小値を求めることができます。
頂点 \(v\) から \(2^k\) 頂点を登るタイミングで、 \({\rm weight}[k][v]\) を参照すればよいです。
一連の流れは、 LCA を求める際のダブリングと同様の手続きで行うことができます。

問題中の指示により、辺をひとつも含まないパスに対する答えを \(0\) とすることに注意してください。
本解法の時間計算量は \(O((N+Q+R) \log N)\) です。

なお、 lazy segtree と HLD (HL分解/ 重軽分解) を組み合わせて利用することで、機械的に \(O(N + (Q+R) \log^2 N)\) で解くこともできます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
const int big=2e9;

int main(){
  int N;
  cin >> N;
  vector<int> dep(N,0);
  vector<vector<int>> doub_ver(20,vector<int>(N,-1));
  vector<int> P(N),W(N);
  for(int i=1;i<N;i++){
    cin >> P[i] >> W[i];
    P[i]--;
    doub_ver[0][i]=P[i];
    dep[i]=dep[P[i]]+1;
  }

  for(int lv=1;lv<20;lv++){
    for(int i=0;i<N;i++){
      int v=doub_ver[lv-1][i];
      if(v==-1){doub_ver[lv][i]=-1;}
      else{doub_ver[lv][i]=doub_ver[lv-1][v];}
    }
  }

  int Q;
  cin >> Q;
  vector<int> delta(N,0);
  while(Q--){
    int u,v;
    cin >> u >> v;
    u--; v--;
    delta[u]++; delta[v]++;
    if(dep[u]>dep[v]){swap(u,v);}
    for(int lv=19;lv>=0;lv--){
      if(doub_ver[lv][v]==-1){continue;}
      if(dep[u]<=dep[doub_ver[lv][v]]){v=doub_ver[lv][v];}
    }
    if(u!=v){
      for(int lv=19;lv>=0;lv--){
        if(doub_ver[lv][u]!=doub_ver[lv][v]){
          u=doub_ver[lv][u];
          v=doub_ver[lv][v];
        }
      }
      u=P[u];
      v=P[v];
    }
    delta[u]-=2;
  }

  vector<vector<int>> doub_wei(20,vector<int>(N,big));
  for(int i=N-1;i>=0;i--){
    W[i]+=delta[i];
    doub_wei[0][i]=W[i];
    delta[P[i]]+=delta[i];
  }

  for(int lv=1;lv<20;lv++){
    for(int i=0;i<N;i++){
      int v=doub_ver[lv-1][i];
      if(v==-1){doub_wei[lv][i]=doub_wei[lv-1][i];}
      else{doub_wei[lv][i]=min(doub_wei[lv-1][i],doub_wei[lv-1][v]);}
    }
  }

  int R;
  cin >> R;
  while(R--){
    int a,b;
    cin >> a >> b;
    a--; b--;
    int res=big;
    if(dep[a]>dep[b]){swap(a,b);}
    for(int lv=19;lv>=0;lv--){
      if(doub_ver[lv][b]==-1){continue;}
      if(dep[a]<=dep[doub_ver[lv][b]]){
        res=min(res,doub_wei[lv][b]);
        b=doub_ver[lv][b];
      }
    }
    if(a!=b){
      for(int lv=19;lv>=0;lv--){
        if(doub_ver[lv][a]!=doub_ver[lv][b]){
          res=min(res,doub_wei[lv][a]);
          a=doub_ver[lv][a];
          res=min(res,doub_wei[lv][b]);
          b=doub_ver[lv][b];
        }
      }
      res=min(res,W[a]);
      res=min(res,W[b]);
    }
    if(res==big){res=0;}
    cout << res << "\n";
  }
  return 0;
}