結果

問題 No.899 γatheree
ユーザー niuezniuez
提出日時 2020-03-24 15:49:29
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 5,980 bytes
コンパイル時間 2,556 ms
コンパイル使用メモリ 185,956 KB
実行使用メモリ 16,268 KB
最終ジャッジ日時 2023-08-30 05:33:42
合計ジャッジ時間 8,365 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <iostream>

struct bfs_euler_tour {
  int N;
  std::vector<std::vector<int>> G;
  std::vector<int> in;
  std::vector<int> out;
  std::vector<int> para;
  std::vector<int> dep;
  std::vector<int> par;
  std::vector<int> start;
  int cnt;
  int D;

  bfs_euler_tour(int N): N(N), G(N), in(N), out(N), para(N, -1), dep(N), par(N) {}

  void add_edge(int a, int b) {
    G[a].push_back(b);
    G[b].push_back(a);
  }

  void dfs(int v, int f, int depth) {
    D = std::max(D, depth);
    par[v] = f;
    dep[v] = depth;
    in[v] = cnt++;
    for(auto t: G[v]) {
      if(t == f) continue;
      dfs(t, v, depth + 1);
    }
    out[v] = cnt;
  }

  void build(int r) {
    cnt = 0;
    D = 0;
    dfs(r, -1, 0);
    D++;

    cnt = 0;
    std::vector<int> que(N);
    int ql = 0;
    int qr = 0;
    que[qr++] = r;
    start.resize(D + 1);

    for(int d = 0; ql < qr; d++) {
      int r = qr;
      start[d] = cnt;
      while(ql < r) {
        int v = que[ql++];
        para[cnt++] = v;
        for(auto t: G[v]) {
          if(para[t] == -1) {
            que[qr++] = t;
          }
        }
      }
    }
    start[D] = cnt;
  }

  int para_lower_bound(int l, int r, int i) {
    while(r - l > 1) {
      int m = (l + r) >> 1;
      if(i <= in[para[m]]) {
        r = m;
      }
      else {
        l = m;
      }
    }
    return r;
  }

  std::pair<int, int> range(int v, int d) {
    if(dep[v] + d < D) {
      int l = start[dep[v] + d];
      int r = start[dep[v] + d + 1];
      return { para_lower_bound(l - 1, r, in[v]), para_lower_bound(l - 1, r, out[v]) };
    }
    else {
      return { 0, 0 };
    }
  }
};

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) noexcept {
  return std::vector<T>(n, std::forward<T>(val));
}

template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) noexcept {
  return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}

template<class T, class Cond>
struct chain {
  Cond cond; chain(Cond cond) : cond(cond) {}
  bool operator()(T& a, const T& b) const {
    if(cond(a, b)) { a = b; return true; }
    return false;
  }
};
template<class T, class Cond>
chain<T, Cond> make_chain(Cond cond) { return chain<T, Cond>(cond); }

#include <vector>
#include <set>
#include <iostream>
using i64 = long long;

struct lazy_segment_tree {
  using T = i64;
  using L = i64;
  static inline T t_ide() { return 0; }
  static inline L l_ide() { return 0; }
  static inline T ope(const T& a, const T& b) { return a + b; }
  static inline L lazy_ope(const L& a, const L& b) { return b; }
  static inline T effect(const T& t, const L& l) { return l; }

  int n, h;
  std::vector<T> node;
  std::vector<L> lazy;
  std::vector<bool> flag;

  lazy_segment_tree(int N) {
    n = 1;
    h = 1;
    while(n < N) n <<= 1, h++;
    node.resize(n << 1, t_ide());
    lazy.resize(n << 1, l_ide());
    flag.resize(n << 1, false);
  }
  lazy_segment_tree(const std::vector<T>& init) {
    n = 1;
    h = 1;
    while(n < init.size()) n <<= 1, h++;
    node.resize(n << 1, t_ide());
    lazy.resize(n << 1, l_ide());
    flag.resize(n << 1, false);
    for(int i = 0;i < init.size();i++) node[i + n] = init[i];
    for(int i = n; i --> 1;) node[i] = ope(node[(i << 1)], node[(i << 1) + 1]);
  }

  inline void eff(int k, L x) {
    if(k < n << 1) {
      lazy[k] = lazy_ope(lazy[k], x);
      flag[k] = true;
    }
  }
  inline T eval(int k) const { return flag[k] ? effect(node[k], lazy[k]) : node[k]; }

  inline void push(int k) {
    if(flag[k]) {
      node[k] = eval(k);
      eff(k << 1, lazy[k]);
      eff((k << 1) | 1, lazy[k]);
      lazy[k] = l_ide();
      flag[k] = false;
    }
  }

  inline void infuse(int k) {
    k = k >> __builtin_ctz(k);
    while((k >>= 1)) node[k] = ope(eval(k << 1), eval((k << 1) + 1));
  }

  inline void infiltrate(int k) {
    if(k == n << 1) return;
    int kc = __builtin_ctz(k);
    for(int i = h; i --> kc;) push(k >> i);
  }

  inline void infiltrate(int l, int r) {
    if(l == r) return;
    if(r == n << 1) infiltrate(l);
    else {
      int hh = h;
      int x = l ^ r;
      for(; !(x >> --hh);) push(l >> hh);
      int lc = __builtin_ctz(l);
      for(int i = hh + 1; i --> lc;) push(l >> i);
      int rc = __builtin_ctz(r);
      for(int i = hh + 1; i --> rc;) push(r >> i);
    }
  }

  void update(int a, int b, L x) {
    int l = a + n;
    int r = b + n;
    infiltrate(l, r);
    while(l < r) {
      if(l & 1) eff(l++, x);
      if(r & 1) eff(--r, x);
      l >>= 1;
      r >>= 1;
    }
    infuse(a + n);
    infuse(b + n);
  }

  T sum(int l, int r) {
    l += n;
    r += n;
    infiltrate(l, r);
    T lx = t_ide();
    T rx = t_ide();
    while(l < r) {
      if(l & 1) lx = ope(lx, eval(l++));
      if(r & 1) rx = ope(eval(--r), rx);
      l >>= 1;
      r >>= 1;
    }
    return ope(lx, rx);
  }
};

int main() {
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  int N;
  cin >> N;
  bfs_euler_tour eul(N);
  rep(i,0,N - 1) {
    int a, b;
    cin >> a >> b;
    eul.add_edge(a, b);
  }

  eul.build(0);

  vector<int> A(N);
  vector<i64> init(N);
  rep(i,0,N) {
    cin >> A[i];
  }
  rep(i,0,N) {
    init[i] = A[eul.para[i]];
  }
  lazy_segment_tree seg(init);

  int Q;
  cin >> Q;
  i64 sum = 0;
  auto func = [&](int v, int d) {
    int l, r;
    std::tie(l, r) = eul.range(v, d);
    sum += seg.sum(l, r);
    seg.update(l, r, 0);
  };
  while(Q--){
    int v;
    cin >> v;
    sum = 0;
    if(eul.par[v] != -1) {
      int p = eul.par[v];
      if(eul.par[p] != -1) {
        func(eul.par[p], 0);
      }
      func(p, 0);
      func(p, 1);
    }
    else {
      func(v, 0);
    }
    func(v, 1);
    func(v, 2);
    cout << sum << "\n";
    seg.update(eul.para[v], eul.para[v] + 1, sum);
  }
}
0