#1164011 (C++23) No.399 動的な領主

• 問題: No.399 動的な領主
• ユーザー: yt142857
• 提出日時: 2026-05-08 23:30:34
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 590 ms / 2,000 ms
• コード長: 8,621 bytes
• コンパイル時間: 3,606 ms
• コンパイル使用メモリ: 364,356 KB
• 実行使用メモリ: 58,792 KB
• 最終ジャッジ日時: 2026-05-08 23:30:46
• 合計ジャッジ時間: 9,650 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

ファイルパターン	結果
other	AC * 19

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define Min(x) *min_element(x.begin(),x.end())
#define Max(x) *max_element(x.begin(),x.end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define range(i,a,b,c) for(int i=a;i<(int)(b);i+=c)
using ll = long long;
using ch = char;
using str = string;
using vll = vector<ll>;
using vch = vector<ch>;
using vvll = vector<vll>;
using sll = set<ll>;
const ll mod998 = 998244353;
const ll mod107 = 1e9+7;
const ll using_mod = mod998;
vll erat(2e6,-1);
vll mobius(2e6,1);
void comp_erat(){
  erat[1] = 1;
  for(int i=2;i<2e6;i++){
    if(erat[i]==-1){
      for(int j=i;j<2e6;j+=i){
        if(j%(i*i)==0) mobius[j] = 0;
        else mobius[j] *= -1;
        if(erat[j]==-1) erat[j] = i;
      }
    }
  }
}
template <class T>
vector<T> fast_zeta(vector<T> &f){
  int len_f = f.size();
  vector<T> F = f;
  for(int i=2;i<len_f;i++){
    if(erat[i]==i){
      for(int j=(len_f-1)/i;j>0;j--){
        F[j] += F[j*i];
      }
    }
  }
  return F;
}
template <class T>
vector<T> fast_mobius(vector<T> &F){
  int len_F = F.size();
  vector<T> f = F;
  for(int i=2;i<len_F;i++){
    if(erat[i]==i){
      for(int j=0;j<=(len_F-1)/i;j++){
        f[j] -= f[j*i];
      }
    }
  }
  return f;
}

vll PF(ll num){
  vll re;
  while(num!=1){
    re.push_back(erat[num]);
    num = num / erat[num];
  }
  return re;
}
vll fact_mod = {1};
void comp_fact(const ll &mod=using_mod){
  for(int i=0;i<1e6;i++){
    fact_mod.push_back((fact_mod[i]*(i+1))%mod);
  }
}
ll pow_mod(const ll &a,const ll &b,const ll &mod=using_mod){
  vll amari;
  amari.push_back(a%mod);
  int count = 0;
  ll count_two = 2;
  while(count_two<=b){
    amari.push_back((amari[count]*amari[count])%mod);
    count += 1;
    count_two *= 2;
  }
  ll re = 1;
  for (int i=0;i<(int)amari.size();i++){
    if (b>>i & 1){
      re = (re*amari[i])%mod;
    }
  }
  return re;
}
ll inv(ll a,ll m=using_mod) {
  ll b = m, u = 1, v = 0;
  while (b) {
    ll t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= m;
  if (u < 0) u += m;
  return u;
}
ll nCr(const ll &n,const ll &r,const ll &mod=using_mod){
  if (n < r) return 0;
  ll one = fact_mod[n];
  ll two = (fact_mod[n-r]*fact_mod[r])%mod;
  ll re = (one*inv(two,mod))%mod;
  return re;
}
ll _GCM(ll n,ll m){
  if(m>n) swap(n,m);
  if(m == 0){
    return n;
  }
  else{
    return _GCM(m,n%m);
  }
}
ll GCM(ll n,ll m){
  if(n<0) n*=-1;
  if(m<0) m*=-1;
  return _GCM(n,m);
}
vll ruiseki(const vll &a){
  vll re(a.size()+1);
  for(int i=0;i<(int)a.size();i++){
    re[i+1] = re[i]+a[i];
  }
  return re;
}
ll bisect_left(const vll &s,const ll &a){
  auto itr = lower_bound(s.begin(), s.end(), a);
  ll re = itr - s.begin();
  return re;
}
ll bisect_right(const vll &s,const ll &a){
  auto itr = lower_bound(s.begin(), s.end(), a+1);
  ll re = itr - s.begin();
  return re;
}


void print(vector<int> s){
  cout << '[';
  for(int i:s){
    cout << i << ' ';
  }
  cout << ']';
  cout << endl;
}
void print(vector<pair<int,int>> s){
  cout << '[';
  for(pair<int,int> i:s){
    cout << '{' << i.first << ' ' << i.second << '}' << ' ';
  }
  cout << ']';
  cout << endl;
}

struct HLD{
  int n;
  vector<vector<int>> tree;
  vector<int> childs_num;
  vector<int> parents;
  vector<int> vertex;
  vector<int> id;
  vector<int> head;
  vector<int> depth;
  
  //部分木サイズを計算
  void comp_childs_num(int node){
    int now = 0;
    for(int nei:tree[node]){
      comp_childs_num(nei);
      now += childs_num[nei];
    }
    childs_num[node] = now + 1;
  }
  //heavy child優先のdfs
  void dfs(int node,int now_head){
    head[node] = now_head;
    vertex.push_back(node);
    pair<int,int> maxi(-1,-1);
    for(int nei:tree[node]){
      maxi = max(maxi,{childs_num[nei],nei});
    }
    int heavy_child = maxi.second;
    if(heavy_child != -1){
      int heavy_child = maxi.second;
      dfs(heavy_child,now_head);
      for(int nei:tree[node]){
        if(nei!=heavy_child){
          dfs(nei,nei);
        }
      }
    }
  }
  //コンストラクタ
  HLD(int _n,vector<pair<int,int>> s){
    n = _n;
    tree.assign(n,vector<int>(0));
    
    id.assign(n,0);
    head.assign(n,0);
    depth.assign(n,0);
    parents.assign(n,-1);
    childs_num.assign(n,-1);
    
    vector<vector<int>> graph(n,vector<int>(0));
    for(pair<int,int> i : s){
      graph[i.first].push_back(i.second);
      graph[i.second].push_back(i.first);
    }
    
    //根付き木の構築
    //depth.parentsをついでに計算
    deque<int> queue;
    queue.push_back(0);
    vector<bool> visited(n,false); 
    visited[0] = true;
    while(!queue.empty()){
      int now = queue.front();queue.pop_front();
      for(int nei:graph[now]){
        if(!visited[nei]){
          depth[nei] = depth[now] + 1;
          parents[nei] = now;
          tree[now].push_back(nei);
          visited[nei] = true;
          queue.push_back(nei);
        }
      }
    }
    
    //部分木サイズを計算
    comp_childs_num(0);
    
    //heavy_child優先のdfs
    //head,vertexを計算
    dfs(0,0);

    //idを計算
    for(int i=0;i<n;i++){
      id[vertex[i]] = i;
    }
  }
  
  int LCA(int u,int v){
    while(true){
      if(head[u] == head[v]){
        if(depth[u] < depth[v]){
          return u;
        }
        else{
          return v;
        }
      }
      if(id[u] < id[v]){
        v = parents[head[v]];
      }
      else{
        u = parents[head[u]];
      }
    }
  }
  
  int dis(int u,int v){
    int lca = LCA(u,v);
    return depth[u]-depth[lca] + depth[v]-depth[lca];
  }
  
  vector<int> to_path(){
    return vertex;
  }
  
  vector<pair<int,int>> use_path(int u,int v){
    vector<pair<int,int>> re;
    while(true){
      if(head[u] == head[v]){
        re.push_back({min(id[u],id[v]) ,max(id[u],id[v]) + 1});
        return re;
      }
      if(id[u] < id[v]){
        re.push_back({min(id[v],id[head[v]]) ,max(id[v],id[head[v]]) + 1});
        v = parents[head[v]];
      }
      else{
        re.push_back({min(id[u],id[head[u]]) ,max(id[u],id[head[u]]) + 1});
        u = parents[head[u]];
      }
    }

  }
};


using S = pair<ll,int>;
using F = int;
S op(S a,S b){
  S re = {a.first+b.first,a.second+b.second};
  return re;
}
S e(){
  return {0,0};
}
S mapping(F a,S b){
  b.first += b.second  * a;
  return b;
}
F composition(F a,F b){
  return a+b;
}
F id(){
  return 0;
}
template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct LazySegTree{
  int _n,size,log_;
  vector<S> data;
  vector<F> lazy;
  LazySegTree(int num){
    log_ = 0;
    size = 1;
    while(size < num){
      log_ ++;
      size *= 2;
    }
    data.assign(2*size, e());
    lazy.assign(2*size, id());
  }
  void push(int num){
    data[num] = mapping(lazy[num],data[num]);
    if(num < size){
      lazy[num*2] = composition(lazy[num],lazy[num*2]);
      lazy[num*2+1] = composition(lazy[num],lazy[num*2+1]);
    }
    lazy[num] = id();
  }
  void push_up(int num){
    if(num < size){
      data[num] = op(data[num*2],data[num*2+1]);
    }
  }
  void set(int num,S s) {
    num += size;
    for(int i=log_;i >= 1;i--) push(num >> i);
    data[num] = s;
    for(int i=1;i <= log_;i++) push_up(num >> i);
  }
  S _prod(int nl,int nr,int gl,int gr,int node){
    push(node);
    if(nr <= gl || gr <= nl) return e();
    else if(gl <= nl && nr <= gr){
      return data[node];
    }
    else{
      int mid = (nl+nr) / 2;
      S re = op(_prod(nl,mid,gl,gr,node*2),_prod(mid,nr,gl,gr,node*2+1));
      push_up(node);
      return re;
    }
  }
  S prod(int l,int r){
    return _prod(0,size,l,r,1);
  }
  void _apply(int nl,int nr,int gl,int gr,int node,F f){
    push(node);
    if(nr <= gl || gr <= nl){}
    else if(gl <= nl && nr <= gr){
      lazy[node] = f;
      push(node);
    }
    else{
      int mid = (nl+nr) / 2;
      _apply(nl,mid,gl,gr,node*2,f);_apply(mid,nr,gl,gr,node*2+1,f);
      push_up(node);
    }
  }
  void apply(int l,int r,F f){
    _apply(0,size,l,r,1,f);
  }
};


int main(){
  int n;cin >> n;
  vector<pair<int,int>> edgs;
  rep(i,n-1){
    int a,b;cin >> a >> b;a--;b--;
    edgs.push_back({a,b});
  }
  HLD hld(n,edgs);
  LazySegTree<S,op,e,F,mapping,composition,id> seg(n);
  rep(i,n){
    seg.set(i,{1,1});
  }
  int q;cin >> q;
  ll ans = 0;
  rep(i,q){
    int a,b;cin >> a >> b;a--;b--;
    for(pair<int,int> j:hld.use_path(a,b)){
      pair<ll,int> now = seg.prod(j.first,j.second);
      ans += now.first;
      seg.apply(j.first,j.second,1);
    }
  }
  cout << ans << endl;
}