結果

問題 No.399 動的な領主
ユーザー twooimp2twooimp2
提出日時 2023-12-25 19:46:48
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 504 ms / 2,000 ms
コード長 6,103 bytes
コンパイル時間 8,460 ms
コンパイル使用メモリ 325,892 KB
実行使用メモリ 30,228 KB
最終ジャッジ日時 2024-09-27 14:36:48
合計ジャッジ時間 14,495 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,812 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 3 ms
6,940 KB
testcase_04 AC 4 ms
6,944 KB
testcase_05 AC 29 ms
6,940 KB
testcase_06 AC 491 ms
25,404 KB
testcase_07 AC 485 ms
25,456 KB
testcase_08 AC 487 ms
25,436 KB
testcase_09 AC 495 ms
25,388 KB
testcase_10 AC 5 ms
6,944 KB
testcase_11 AC 25 ms
6,940 KB
testcase_12 AC 360 ms
26,000 KB
testcase_13 AC 350 ms
26,240 KB
testcase_14 AC 128 ms
30,228 KB
testcase_15 AC 149 ms
30,020 KB
testcase_16 AC 208 ms
28,152 KB
testcase_17 AC 504 ms
25,504 KB
testcase_18 AC 494 ms
25,504 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
using P=pair<ll,ll>;
using T=tuple<ll,ll,ll>;

struct S{
    long long value;
    int size;
};
using F = long long;

S op(S a, S b){ return {a.value+b.value, a.size+b.size}; }
S e(){ return {0, 0}; }
S mapping(F f, S x){ return {x.value + f*x.size, x.size}; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }

void IO(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
}

struct HLD{
  //References:
  //　https://judge.yosupo.jp/submission/72507　原典
  //  https://atcoder.jp/contests/abc294/submissions/39859050　原典より使いやすいsegtree対応ver
  //　https://atcoder.jp/contests/past202010-open/submissions/33495220　原典より使いやすいlazy_segtree対応ver
  //　↑がReferencesの中で最もおすすめ
  
  //頂点に初期値を与える場合の注意点
  //　-hld.build()の実行後に行う
  //　-頂点uはHLD内部ではhld.in[u]となる
  //辺に値がある場合は子側の頂点に持たせてedge=trueで関数を呼び出す
  //lazy_segtreeを使用
  
  ll N,root;
  vector<vector<ll>> G;
  vector<ll> parent;//頂点uの親
  vector<ll> depth;//頂点uの深さ
  vector<ll> sz;//頂点uを根とする部分木のサイズ(heavy)
  vector<ll> in;//HLD時の探索順序(Euler Tour)
  vector<ll> out;//後述
  vector<ll> head;//頂点uが属するHL分解後の連結成分の根
  vector<ll> rev;//探索順序番号から元の頂点番号への逆引き
  ll t=0;//探索順序の計算用
  
  //[in[u],out[u])      :=頂点uを根とする部分木に対応
  //[in[head[u]],in[u]] :=HLD後の連結成分における頂点uからそのheadまでのパスに対応
  
  HLD(){}
  HLD(ll n,ll r=0):N(n),root(r){
    G.resize(N); parent.resize(N); depth.resize(N); sz.resize(N);
    in.resize(N); out.resize(N); head.resize(N); rev.resize(N);
  }
  
  //双方向に辺を張る
  void add_edge(ll u,ll v){
    assert(0<=u&&u<N);
    assert(0<=v&&v<N);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  
  //各部分木のサイズを求める
  void dfs_sz(ll u,ll p,ll d){
    parent[u]=p;
    depth[u]=d;
    sz[u]=1;
    //heavy edgeが先頭に来るように維持しながら探索する
    if(G[u].size()&&G[u][0]==p){
      swap(G[u][0],G[u].back());
    }
    for(ll &v:G[u]){
      //NOTE: swapのためにポインタを用いる必要がある
      if(v!=p){
        dfs_sz(v,u,d+1);
        sz[u]+=sz[v];
        if(sz[G[u][0]]<sz[v]){
          swap(G[u][0],v);
        }
      }
    }
  }
  
  //HLD(Heavy Light Decomposition)
  void dfs_hld(ll u,ll p){
    in[u]=t++;
    rev[in[u]]=u;
    for(const ll &v:G[u]){
      if(v!=p){
        head[v]=(v==G[u][0]?head[u]:v);// heavy or light
        dfs_hld(v,u);
      }
    }
    out[u]=t;
  }
  
  void build(){
    dfs_sz(root,-1,0);
    dfs_hld(root,-1);
  }
  
  //頂点uから深さdだけ親をたどる (level-ancestor) : O(log N)
  ll la(ll u,ll d)const{
    assert(0<=u&&u<N);
    //辿った先が木上になければ-1を返す
    if(depth[u]-d<0){
      return -1;
    }
    while(1){
      ll v=head[u];
      if(in[u]-d>=in[v]){
        return rev[in[u]-d];
      }
      d-=in[u]-in[v]+1;
      u=parent[v];
    }
  }
  
  //頂点u,vのLCA : O(log N)
  ll lca(ll u,ll v)const{
    assert(0<=u&&u<N);
    assert(0<=v&&v<N);
    while(1){
      if(in[u]>in[v]){
        swap(u,v);//in[u]<=in[v] (uが根側)
      }
      if(head[u]==head[v]){
        return u;
      }
      v=parent[head[v]];
    }
  }
  
  //パス間の辺数
  ll distance(ll u,ll v)const{
    assert(0<=u&&u<N);
    assert(0<=v&&v<N);
    return depth[u]+depth[v]-2*depth[lca(u,v)];
  }
  
  //頂点wがパス(u,v)上に存在するか : O(log N)
  bool on_path(ll u,ll v,ll w)const{
    assert(0<=u&&u<N);
    assert(0<=v&&v<N);
    assert(0<=w&&w<N);
    return distance(u,w)+distance(w,v)==distance(u,v);
  }
  
  //パス[u,v]に対する何らかのクエリ : O((log N)^2)
  //閉区間に対応するクエリであることに注意
  vector<P> query(ll u,ll v,bool edge){
    assert(0<=u&&u<N);
    assert(0<=v&&v<N);
    vector<P> res;
    while(1){
      if(in[u]>in[v]){
        swap(u,v);
      }
      if(head[u]==head[v]){
        break;
      }
      res.emplace_back(in[head[v]],in[v]);
      v=parent[head[v]];
    }
    res.emplace_back(in[u]+edge,in[v]);
    return res;
  }
  
  //頂点uを根とする部分木に対する更新クエリ : O(log N)
  void apply_subtree(ll u,bool edge,function<void(ll,ll)> func){
    assert(0<=u&&u<N);
    func(in[u]+edge,out[u]-1);
  }
  
  //頂点uを根とする部分木に対する取得クエリ : O(log N)
  template<class S>
  S prod_subtree(ll u,bool edge,function<S(ll,ll)> func){
    assert(0<=u&&u<N);
    return func(in[u]+edge,out[u]-1);
  }
  
  //頂点uを返す
  //頂点uはHLD内部ではhld.in[u]となる
  ll vertex_idx(ll u){
    return in[u];
  }
  
  //辺に値がある場合は子側の頂点に持たせてedge=trueで関数を呼び出す
  ll edge_idx(ll u,ll v){
    return max(in[u],in[v]);
  }
};

int main(){
  IO();
  ll n;
  cin>>n;
  vector<P> uv;
  vector<T> edges;
  HLD hld(n);
  for(ll i=0;i<n-1;i++){
    ll u,v;
    cin>>u>>v;
    u--;
    v--;
    uv.emplace_back(u,v);
    hld.add_edge(u,v);
    edges.emplace_back(u,v,0);
  }
  hld.build();
  lazy_segtree<S,op,e,F,mapping,composition,id> seg(vector<S>(n,{0,1}));
  for(ll i=0;i<n-1;i++){
    ll u=get<0>(edges[i]);
    ll v=get<1>(edges[i]);
    ll w=get<2>(edges[i]);
    seg.apply(hld.edge_idx(u,v),hld.edge_idx(u,v)+1,w);
  }
  ll q;
  cin>>q;
  bool edge=false;
  while(q--){
    ll a,b;
    cin>>a>>b;
    a--;
    b--;
    vector<P> add_tax=hld.query(a,b,edge);
    for(auto pairs:add_tax){
      ll l=pairs.first;
      ll r=pairs.second;
      seg.apply(l,r+1,1);
    }
  }
  ll ans=0;
  for(ll i=0;i<n;i++){
    ll val=seg.prod(i,i+1).value;
    ans+=val*(val+1)/2;
  }
  cout<<ans<<endl;
}
0