結果

問題 No.1197 モンスターショー
ユーザー KoD
提出日時 2020-08-22 17:48:42
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,987 bytes
コンパイル時間 4,639 ms
コンパイル使用メモリ 130,564 KB
最終ジャッジ日時 2025-01-13 11:07:53
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 WA * 25 TLE * 10
権限があれば一括ダウンロードができます

ソースコード

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

#line 1 "main.cpp"
/**
 * @title Template
 */
#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/chmin_chmax.cpp"
template <class T, class U>
constexpr bool chmin(T &lhs, const U &rhs) {
  if (lhs > rhs) { lhs = rhs; return true; }
  return false;
}
template <class T, class U>
constexpr bool chmax(T &lhs, const U &rhs) {
  if (lhs < rhs) { lhs = rhs; return true; }
  return false;
}
/**
 * @title Chmin/Chmax
 */
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/range.cpp"
#line 4 "/Users/kodamankod/Desktop/Programming/Library/other/range.cpp"
class range {
public:
  class iterator {
  private:
    int64_t M_position;
  public:
    constexpr iterator(int64_t position) noexcept: M_position(position) { }
    constexpr void operator ++ () noexcept { ++M_position; }
    constexpr bool operator != (iterator other) const noexcept { return M_position != other.M_position; }
    constexpr int64_t operator * () const noexcept { return M_position; }
  };
  class reverse_iterator {
  private:
    int64_t M_position;
  
  public:
    constexpr reverse_iterator(int64_t position) noexcept: M_position(position) { }
    constexpr void operator ++ () noexcept { --M_position; }
    constexpr bool operator != (reverse_iterator other) const noexcept { return M_position != other.M_position; }
    constexpr int64_t operator * () const noexcept { return M_position; }
  };
  
private:
  const iterator M_first, M_last;
public:
  constexpr range(int64_t first, int64_t last) noexcept: M_first(first), M_last(std::max(first, last)) { }
  constexpr iterator begin() const noexcept { return M_first; }
  constexpr iterator end() const noexcept { return M_last; }
  constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator(*M_last - 1); } 
  constexpr reverse_iterator rend() const noexcept { return reverse_iterator(*M_first - 1); } 
};
/**
 * @title Range
 */
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/rev.cpp"
#include <type_traits>
#include <iterator>
#line 6 "/Users/kodamankod/Desktop/Programming/Library/other/rev.cpp"
template <class T>
class rev_impl {
public:
  using iterator = decltype(std::rbegin(std::declval<T>()));
private:
  const iterator M_begin;
  const iterator M_end;
public:
  constexpr rev_impl(T &&cont) noexcept: M_begin(std::rbegin(cont)), M_end(std::rend(cont)) { }
  constexpr iterator begin() const noexcept { return M_begin; }
  constexpr iterator end() const noexcept { return M_end; }
};
template <class T>
constexpr decltype(auto) rev(T &&cont) {
  return rev_impl<T>(std::forward<T>(cont));
}
/**
 * @title Reverser
 */
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/fix_point.cpp"
#line 4 "/Users/kodamankod/Desktop/Programming/Library/other/fix_point.cpp"
template <class Func>
struct fix_point_impl: private Func {
  explicit constexpr fix_point_impl(Func &&func): Func(std::forward<Func>(func)) { }
  template <class... Args>
  constexpr decltype(auto) operator () (Args &&... args) const {
    return Func::operator()(*this, std::forward<Args>(args)...);
  }
};
template <class Func>
constexpr decltype(auto) fix_point(Func &&func) {
  return fix_point_impl<Func>(std::forward<Func>(func));
}
/**
 * @title Lambda Recursion
 */
#line 18 "main.cpp"
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
constexpr i32 inf32 = (i32(1) << 30) - 1;
constexpr i64 inf64 = (i64(1) << 62) - 1;
constexpr i32 Bucket = 300;
struct query_type {
  i32 vertex, index;
  query_type(): vertex(0), index(0) { }
};
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  i32 N, K, Q;
  std::cin >> N >> K >> Q;
  std::vector<i32> C(K);
  for (auto &x: C) {
    std::cin >> x;
    --x;
  }
  std::vector<std::vector<i32>> graph(N);
  for (auto i: range(1, N)) {
    i32 u, v;
    std::cin >> u >> v;
    --u; --v;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
  std::vector<std::array<i32, 17>> parent(N);
  std::vector<i32> depth(N);
  fix_point([&](auto dfs, i32 u, i32 p) -> void {
    if (p == -1) {
      depth[u] = 0;
      parent[u][0] = u;
    } 
    else {
      depth[u] = depth[p] + 1;
      parent[u][0] = p;
    }
    for (auto v: graph[u]) {
      if (v != p) {
        dfs(v, u);
      }
    }
  })(0, -1);
  for (auto j: range(0, 16)) {
    for (auto i: range(0, N)) {
      parent[i][j + 1] = parent[parent[i][j]][j];
    }
  }
  
  auto lca = [&](i32 u, i32 v) {
    if (depth[u] > depth[v]) {
      std::swap(u, v);
    }
    auto dif = depth[v] - depth[u];
    for (auto j: range(0, 17)) {
      if (dif & 1) {
        v = parent[v][j];
      }
      dif >>= 1;
    }
    if (u == v) {
      return u;
    }
    for (auto j: rev(range(0, 17))) {
      if (parent[u][j] != parent[v][j]) {
        u = parent[u][j];
        v = parent[v][j];
      }
    }
    return parent[u][0];
  };
  auto calc = [&](i32 u, i32 v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
  };
  std::vector<query_type> query(Q);
  std::vector<i64> answer;
  for (auto &[v, i]: query) {
    i32 type;
    std::cin >> type;
    if (type == 1) {
      std::cin >> i >> v;
      --i; --v;
    }
    else {
      std::cin >> v;
      --v;
      answer.push_back(0);
      i = -((i32) answer.size());
    }
  }
  const i32 Block = (Q + Bucket - 1) / Bucket;
  for (auto steps: range(0, Block)) {
    const i32 first = steps * Bucket;
    const i32 last = std::min<i32>((steps + 1) * Bucket, Q);
    std::vector<i64> size(N), dist(N);
    std::vector<bool> stable(K, true);
    std::vector<i32> indices;
    for (auto i: range(first, last)) {
      if (query[i].index >= 0) {
        indices.push_back(query[i].index);
        stable[query[i].index] = false;
      }
    }
    for (auto i: range(0, K)) {
      if (stable[i]) {
        ++size[C[i]];
      } 
    }
    fix_point([&](auto dfs, i32 u, i32 p) -> void {
      for (auto v: graph[u]) {
        if (v != p) {
          dfs(v, u);
          size[u] += size[v];
          dist[u] += dist[v] + size[v];
        }
      }
    })(0, -1);
    fix_point([&](auto dfs, i32 u, i32 p, i64 s, i64 d) -> void {
      for (auto v: graph[u]) {
        if (v == p) {
          size[u] += s;
          dist[u] += s + d;
        }
      }
      for (auto v: graph[u]) {
        if (v != p) {
          dfs(v, u, size[u] - size[v], dist[u] - (size[v] + dist[v]));
        }
      }
    })(0, -1, 0, 0);
    for (auto i: range(first, last)) {
      if (query[i].index >= 0) {
        C[query[i].index] = query[i].vertex;
      }
      else {
        const auto j = -(query[i].index + 1);
        answer[j] += dist[query[i].vertex];
        for (auto k: indices) {
          answer[j] += calc(query[i].vertex, C[k]);
        }
      }
    }
  }
  for (auto x: answer) {
    std::cout << x << '\n';
  }
  return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0