結果

問題 No.399 動的な領主
ユーザー koyumeishi
提出日時 2016-07-13 05:23:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 461 ms / 2,000 ms
コード長 8,549 bytes
コンパイル時間 1,620 ms
コンパイル使用メモリ 96,160 KB
実行使用メモリ 35,780 KB
最終ジャッジ日時 2024-11-07 18:29:03
合計ジャッジ時間 6,649 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
#include <cassert>
#include <functional>
#include <algorithm>
using namespace std;
template<class T=int>
class Segment_Tree_Lazy{
private:
  //default values are set in the constractor
  const T default_value;    //default (NULL) node value
  const T default_lazy_value; //default lazy value
  struct node{
    T value; T lazy_value;
    bool lazy; int lb; int ub;
    node* par; node* lch; node* rch;
    node(T default_value, T default_lazy_value) : 
      value(default_value),
      lazy_value(default_lazy_value),
      lazy(false),
      lb(0),ub(0),      //this node covers [lb, rb)
      par(NULL),lch(NULL),rch(NULL){
    }
  };
  T evaluate(T left_val, T right_val){  //evaluate node value
    return left_val + right_val;  //sum
    //return max(left_val, right_val);  //max
  }
  T evaluate_node_and_lazy(T node_val, T lazy_val){ //evaluate node value and lazy value
    return node_val + lazy_val; //sum
    //return max(node_val, lazy_val); //max
    //return lazy_val;  //fill
  }
  T evaluate_lazy_and_lazy(T old_val, T new_val){ 
    return old_val + new_val; //sum
    //return new_val;   //fill
  }
  void new_lazy(node* t, T add_value){  
    if(t==NULL) return;
    if(t->lazy){
      t->lazy_value = evaluate_lazy_and_lazy(t->lazy_value, add_value);
    }else{
      t->lazy_value = add_value;
    }
    t->lazy = true;
  }
  T lazy_to_value(node* t){
    if(t->lazy) return t->lazy_value * (t->ub - t->lb);
    return default_lazy_value;
  }
  T get_value(node* t){
    if(t==NULL) return default_value;
    return evaluate_node_and_lazy(t->value , lazy_to_value(t));
  }
  vector<node> v;
  node* root;
  int size;
  node* constract(node* t, int pos, int lb, int ub){
    if(pos == 0){
      t->par = t;
    }
    t->lb = lb;
    t->ub = ub;
    if(pos<size-1){
      t->lch = constract(&v[(pos<<1) + 1], (pos<<1) + 1, lb, (ub+lb)>>1);
      t->lch->par = t;
      t->rch = constract(&v[(pos<<1) + 2], (pos<<1) + 2, (ub+lb)>>1, ub);
      t->rch->par = t;
    }
    return t;
  }
  void initialize(int size_){
    size = 1;
    while(size < size_) size <<= 1;
    v = vector<node>(size<<1, node(default_value, default_lazy_value));
    root = constract(&v[0], 0, 0, size);
  }
  //propagate lazy value of node t to its children
  void push(node* t){
    if(t==NULL) return;
    if(t->lazy){
      if(t->lch != NULL){ //has child
        new_lazy(t->lch, t->lazy_value);
        new_lazy(t->rch, t->lazy_value);
        t->value = evaluate( get_value(t->lch), get_value(t->rch) );
      }else{
        t->value = get_value(t);
      }
      t->lazy_value = default_lazy_value;
      t->lazy = false;
    }
  }
  void range_add(int left, int right, T add_value, node* t){
    if(t==NULL) return;
    if(t->ub <= left || right <= t->lb){
      return;
    }
    push(t);
    if(left <= t->lb && t->ub <= right){
      new_lazy(t, add_value);
      return;
    }
    //partialy covered
    range_add(left, right, add_value, t->lch);
    range_add(left, right, add_value, t->rch);
    
    t->value = evaluate( get_value(t->lch), get_value(t->rch) );
  }
  //get value of [left,right)
  T get_range_value(int left, int right, node* t){
    if(t==NULL) return default_value;
    if(t->ub <= left || right <= t->lb){
      return default_value;
    }
    push(t);
    if(left <= t->lb && t->ub <= right){
      return get_value(t);
    }
    T L = get_range_value(left, right, t->lch);
    T R = get_range_value(left, right, t->rch);
    return evaluate(L, R);
  }
  void lazy_update(node* t){
    if(t->par != root){
      lazy_update(t->par);
    }
    push(t);
  }
public:
  //default node value must be set
  // sum : 0
  // max : MIN_INF
  // min : MAX_INF
  // gcd : 1
  Segment_Tree_Lazy(int size_, T default_value__ = 0, T default_lazy_value__ = 0) : 
    default_value(default_value__), default_lazy_value(default_lazy_value__){
    initialize(size_);
  }
  //node[pos] <= new_value
  void update(int pos, T new_value){
    node* t = &v[pos + size-1];
    
    lazy_update(t);
    t->value = new_value;
    while(t != root){
      t = t->par;
      t->value = evaluate( get_value(t->lch), get_value(t->rch) );
    }
  }
  //[l,r) += add_value
  void range_add(int left, int right, T add_value){
    range_add(left, right, add_value, root);
  }
  //get value [left,right)
  T get_range_value(int left, int right){
    return get_range_value(left, right, root);
  }
  void dbg(){
    for(int i=0; i<v.size(); i++){
      cerr << get_value(&v[i]) << " ";
    }
    cerr << endl;
  }
};
//HL分解 構築O(|v|), 空間O(|v|)
class HeavyLightDecomposition{
 public:
  struct heavy_set{
    vector<int> element;
    int depth;
    int parent_vertex;
    heavy_set(int v, int d, int par) : element(1,v), depth(d), parent_vertex(par){}
  };
  vector<vector<int>>& G;
  vector<heavy_set> S;
  vector<int> subtree_size;
  vector<int> set_index;
  vector<int> ele_index;
 private:
  int get_subtree_size(int pos, int par){
    int sz = 1;
    for(int ch : G[pos]){
      if(ch == par) continue;
      sz += get_subtree_size(ch, pos);
    }
    return subtree_size[pos] = sz;
  }
  void make_path(int pos, int par, int set_id){
    set_index[pos] = set_id;
    ele_index[pos] = S[set_id].element.size()-1;
    int largest_child = -1;
    int value = 0;
    for(int ch : G[pos]){
      if(ch == par) continue;
      if(value < subtree_size[ch]){
        value = subtree_size[ch];
        largest_child = ch;
      }
    }
    for(int ch : G[pos]){
      if(ch == par) continue;
      if(largest_child == ch){
        S[set_id].element.push_back(ch);
        make_path(ch, pos, set_id);
      }else{
        S.emplace_back( ch, S[set_id].depth+1, pos );
        make_path(ch, pos, S.size()-1);
      }
    }
  }
  void init(int root){
    subtree_size.resize(G.size(), 0);
    get_subtree_size(root,root);
    set_index.resize(G.size(), 0);
    ele_index.resize(G.size(), 0);
    S.emplace_back( root,0,root );
    make_path( root, root, 0 );
    subtree_size.clear();
  }
 public:
  HeavyLightDecomposition(vector<vector<int>>& G_, int root = 0) : G(G_){
    init(root);
  }
  //set_index, element_index
  //S[set_index].element[element_index] == v
  pair<int,int> get_position(int v){
    return {set_index[v], ele_index[v]};
  }
};
//Lowest Common Ancestor with HL-decomposition tree
//O(log n) / query
int LCA(HeavyLightDecomposition& T, int u, int v){
  auto pu = T.get_position(u);
  auto pv = T.get_position(v);
  if(pu.first == pv.first){
    return pu.second < pv.second ? u : v;
  }
  if(T.S[pu.first].depth > T.S[pv.first].depth){
    swap(pu, pv);
    swap(u,v);
  }
  while(T.S[pu.first].depth != T.S[pv.first].depth){
    v = T.S[pv.first].parent_vertex;
    pv = T.get_position( v );
  }
  while(pu.first != pv.first){
    u = T.S[pu.first].parent_vertex;
    v = T.S[pv.first].parent_vertex;
    pu = T.get_position(u);
    pv = T.get_position(v);
    if(T.S[pv.first].depth == 0) break;
    if(T.S[pv.first].depth == 0) break;
  }
  if(pu.first == pv.first){
    return pu.second < pv.second ? u : v;
  }else{
    abort();
  }
  return -1;
}
int main(){
  int n;
  cin >> n;
  vector<vector<int>> G(n);
  for(int i=0; i<n-1; i++){
    int u,v;
    cin >> u >> v;
    u--; v--;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  HeavyLightDecomposition t(G, 0);
  vector<Segment_Tree_Lazy<long long>> seg;
  seg.reserve( t.S.size() );
  for(int i=0; i<t.S.size(); i++){
    seg.emplace_back( t.S[i].element.size() );
  }
  long long ans = 0;
  int q;
  cin >> q;
  while(q--){
    int u,v;
    cin >> u >> v;
    u--; v--;
    int p = LCA(t, u,v);
    while( t.get_position(u).first != t.get_position(p).first ){
      auto tmp = t.get_position(u);
      seg[ tmp.first ].range_add(0, tmp.second+1, 1);
      ans += seg[ tmp.first ].get_range_value(0, tmp.second+1);
      u = t.S[ tmp.first ].parent_vertex;
    }
    while( t.get_position(v).first != t.get_position(p).first ){
      auto tmp = t.get_position(v);
      seg[ tmp.first ].range_add(0, tmp.second+1, 1);
      ans += seg[ tmp.first ].get_range_value(0, tmp.second+1);
      v = t.S[ tmp.first ].parent_vertex;
    }
    auto tmp_u = t.get_position(u);
    auto tmp_v = t.get_position(v);
    seg[tmp_u.first].range_add( min(tmp_u.second, tmp_v.second), max(tmp_u.second, tmp_v.second)+1, 1);
    ans += seg[tmp_u.first].get_range_value( min(tmp_u.second, tmp_v.second), max(tmp_u.second, tmp_v.second)+1 );
  }
  cout << ans << endl;
  return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0