#420797 (C++17) No.399 動的な領主

• 問題: No.399 動的な領主
• ユーザー: Imperi_Night
• 提出日時: 2020-01-23 13:52:14
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 968 ms / 2,000 ms
• コード長: 6,557 bytes
• コンパイル時間: 1,699 ms
• コンパイル使用メモリ: 151,368 KB
• 実行使用メモリ: 47,360 KB
• 最終ジャッジ日時: 2024-07-19 05:33:17
• 合計ジャッジ時間: 11,549 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	3 ms; 5,376 KB
testcase_04	AC	5 ms; 5,376 KB
testcase_05	AC	53 ms; 6,656 KB
testcase_06	AC	968 ms; 40,192 KB
testcase_07	AC	958 ms; 40,192 KB
testcase_08	AC	941 ms; 40,064 KB
testcase_09	AC	941 ms; 40,064 KB
testcase_10	AC	6 ms; 5,376 KB
testcase_11	AC	36 ms; 6,656 KB
testcase_12	AC	626 ms; 39,552 KB
testcase_13	AC	574 ms; 39,552 KB
testcase_14	AC	258 ms; 47,360 KB
testcase_15	AC	308 ms; 47,360 KB
testcase_16	AC	419 ms; 43,264 KB
testcase_17	AC	968 ms; 40,192 KB
testcase_18	AC	916 ms; 40,064 KB

ソースコード

#include <cassert>
#include <limits>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <chrono>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <random>
#include <memory>
#include <utility>
#include "limits.h"
 
#define rep(i, a, b) for (long long (i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

void debug_out(){std::cerr<<std::endl;}

template<typename H,typename... T>
void debug_out(H head,T... tail){
  std::cerr<<" "<<head;
  debug_out(tail...);
}

 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}
 
long long pow_mod(long long a, long long b, long long mod=-1) {
  if ((a == 0)||(mod!=-1&&a%mod==0))return 0;
  long long x = 1;
  while (b > 0) {
    if (b & 1)x = (mod!=-1)?(x * a) % mod:x*a;
    a = (mod!=-1)?(a * a) % mod:a*a;
    b >>= 1;
  }
  return x;
}
 
// const long long MOD = 998244353;
const long long MOD = 1e9 + 7;

using ll = long long;
using P = std::pair<long long,long long>;

//LowestCommonAncestor
//ダブリングを使う 前処理O(Nlog N),クエリO(log N)
class LowestCommonAncestor{
  using ll=long long;
  private:

  ll n,bit;
  std::vector<ll> depth;
  std::vector<std::vector<ll>> par_doubling,graph;

  ll getbit(ll temp){
    ll a=1;
    while(temp>0){
      a++;
      temp>>=1;
    }
    return a;
  }

  void dfs(ll now,ll par,ll dep){
    depth[now]=dep;
    if(par!=-1)par_doubling[now][0]=par;
    else par_doubling[now][0]=now;

    for(auto e:graph[now]){
      if(e!=par){
        dfs(e,now,dep+1);
      }
    }
  }

  void doubling(){
    for(ll i=1;i<bit;i++){
      for(ll j=0;j<n;j++){
        par_doubling[j][i]=par_doubling[par_doubling[j][i-1]][i-1];
      }
    }
  }

  public:

  //隣接リストのグラフと木の根を渡す
  LowestCommonAncestor(const std::vector<std::vector<ll>>& g,ll root_):graph(g),n(g.size()),bit(getbit(g.size())),
                                                              depth(n),par_doubling(n,std::vector<ll>(bit)){
    dfs(root_,-1,0);
    doubling();
  }
  
  ll query(ll a,ll b){
    if(depth[a]<depth[b])std::swap(a,b);

    for(ll i=0;i<bit;i++){
      if(((depth[a]-depth[b])>>i)&1)a=par_doubling[a][i];
    }

    if(a==b)return a;

    for(ll i=bit-1;i>=0;i--){
      if(par_doubling[a][i]!=par_doubling[b][i]){
        a=par_doubling[a][i];
        b=par_doubling[b][i];
      }
    }

    return par_doubling[a][0];
  }

};

//遅延セグ木
template<typename T,typename E>
class LazySegmentTree{
  private:
  int n,n0;
  std::vector<T> dat;
  std::vector<E> lazy;

  T init_t;
  E init_e;

  using F=std::function<T(T,T)>;
  using G=std::function<T(T,E)>;
  using H=std::function<E(E,E)>;
  using P=std::function<E(E,int)>;

  F f;
  G g;
  H h;
  P p;

  T update(int a,int b,E val,int l,int r,int k){
    if(lazy[k]!=init_e){
      if(k<n0-1){
        lazy[2*k+1]=h(lazy[2*k+1],lazy[k]);
        lazy[2*k+2]=h(lazy[2*k+2],lazy[k]);
      }
      dat[k]=g(dat[k],p(lazy[k],r-l));
      lazy[k]=init_e;
    }

    if(r<=a||b<=l)return dat[k];
    if(a<=l&&r<=b){
      lazy[k]=h(lazy[k],val);
      return g(dat[k],p(lazy[k],r-l));
    }

    return dat[k]=f(update(a,b,val,l,l+(r-l)/2,2*k+1),update(a,b,val,l+(r-l)/2,r,2*k+2));
  }

  T query(int a,int b,int l,int r,int k){
    if(lazy[k]!=init_e){
      if(k<n0-1){
        lazy[2*k+1]=h(lazy[2*k+1],lazy[k]);
        lazy[2*k+2]=h(lazy[2*k+2],lazy[k]);
      }
      dat[k]=g(dat[k],p(lazy[k],r-l));
      lazy[k]=init_e;
    }

    if(r<=a||b<=l)return init_t;
    if(a<=l&&r<=b)return dat[k];
    T lval=query(a,b,l,l+(r-l)/2,2*k+1);
    T rval=query(a,b,l+(r-l)/2,r,2*k+2);
    return f(lval,rval);
  }

  public:

  LazySegmentTree(int n_,F f_,G g_,H h_,T t,E e,std::vector<T> dat_=std::vector<T>(),P p_=[](E a,int n){return a;})
    :n(n_),init_t(t),init_e(e),f(f_),g(g_),h(h_),p(p_){

    n0=1;
    while(n0<n)n0<<=1;
    dat=std::vector<T>(2*n0-1,init_t);
    lazy=std::vector<E>(2*n0-1,init_e);
    if(n_==dat_.size()){
      for(int i=0;i<n_;i++)dat[i+n0-1]=dat_[i];
      for(int i=n0-2;i>=0;i--)dat[i]=f(dat[2*i+1],dat[2*i+2]);
    }
  }

  void update(int a,int b,E val){
    update(a,b,val,0,n0,0);
  }

  T query(int a,int b){
    return query(a,b,0,n0,0);
  }
};

int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  ll n;
  std::cin>>n;

  std::vector<std::vector<ll>> graph(n);
  std::vector<ll> par(n),sz(n),in(n),nxt(n);

  rep(i,0,n-1){
    ll u,v;
    std::cin>>u>>v;
    u--;v--;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  auto dfs_sz=[&](auto f,ll now,ll pa)->void{
    sz[now]=1;
    par[now]=pa;
    for(auto itr=graph[now].begin();itr!=graph[now].end();){
      if(*itr==pa){
        itr=graph[now].erase(itr);
      }else{
        f(f,*itr,now);
        sz[now]+=sz[*itr];
        if(sz[*itr]>sz[*graph[now].begin()]){
          std::iter_swap(itr,graph[now].begin());
        }
        itr++;
      }
    }
  };
  dfs_sz(dfs_sz,0,-1);

  LowestCommonAncestor lca(graph,0);

  ll cnt=0;
  auto dfs_hld=[&](auto f,ll now)->void{
    in[now]=cnt++;
    for(auto u:graph[now]){
      nxt[u]=(u==graph[now][0]?nxt[now]:u);
      f(f,u);
    }
  };
  dfs_hld(dfs_hld,0);

  auto sum=[](ll a,ll b){return a+b;};

  LazySegmentTree<ll,ll> seg(n,sum,sum,sum,0,0,std::vector<ll>(n,1),[](ll a,int n){return a*n;});

  ll ans=0;
  ll q;
  std::cin>>q;

  rep(_,0,q){
    ll v[2];
    std::cin>>v[0]>>v[1];
    v[0]--;v[1]--;
    ll l=lca.query(v[0],v[1]);

    rep(i,0,2){
      while(1){
        if(nxt[v[i]]==nxt[l]){
          ans+=seg.query(in[l]+i,in[v[i]]+1);
          seg.update(in[l]+i,in[v[i]]+1,1);
          break;
        }
        ans+=seg.query(in[nxt[v[i]]],in[v[i]]+1);
        seg.update(in[nxt[v[i]]],in[v[i]]+1,1);
        v[i]=par[nxt[v[i]]];
      }
    }
  }

  std::cout<<ans<<"\n";

  return 0;
}