結果

問題 No.1637 Easy Tree Query
ユーザー cutmdocutmdo
提出日時 2024-12-20 01:57:41
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 211 ms / 2,000 ms
コード長 4,236 bytes
コンパイル時間 2,067 ms
コンパイル使用メモリ 119,044 KB
実行使用メモリ 12,920 KB
最終ジャッジ日時 2024-12-20 01:57:52
合計ジャッジ時間 9,534 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 191 ms
12,920 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 41 ms
7,920 KB
testcase_05 AC 166 ms
6,816 KB
testcase_06 AC 108 ms
6,820 KB
testcase_07 AC 65 ms
6,816 KB
testcase_08 AC 33 ms
6,980 KB
testcase_09 AC 122 ms
10,244 KB
testcase_10 AC 73 ms
6,816 KB
testcase_11 AC 169 ms
10,940 KB
testcase_12 AC 168 ms
9,116 KB
testcase_13 AC 27 ms
6,820 KB
testcase_14 AC 74 ms
10,420 KB
testcase_15 AC 159 ms
11,376 KB
testcase_16 AC 119 ms
12,148 KB
testcase_17 AC 48 ms
6,816 KB
testcase_18 AC 152 ms
6,836 KB
testcase_19 AC 165 ms
7,308 KB
testcase_20 AC 181 ms
8,968 KB
testcase_21 AC 88 ms
8,148 KB
testcase_22 AC 187 ms
12,480 KB
testcase_23 AC 45 ms
6,816 KB
testcase_24 AC 68 ms
8,180 KB
testcase_25 AC 165 ms
6,816 KB
testcase_26 AC 211 ms
9,664 KB
testcase_27 AC 207 ms
11,952 KB
testcase_28 AC 119 ms
6,816 KB
testcase_29 AC 164 ms
8,836 KB
testcase_30 AC 39 ms
8,664 KB
testcase_31 AC 139 ms
6,820 KB
testcase_32 AC 70 ms
6,816 KB
testcase_33 AC 155 ms
6,816 KB
testcase_34 AC 35 ms
12,172 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#define PROBLEM "https://yukicoder.me/problems/no/1637"

#include <iostream>

#include <ranges>
#include <vector>
#include <stack>
#include <iostream>
#include <tuple>
#include <deque>
namespace mtd {  template <class Node = int, class Cost = long long>  class Graph {            using Edge = std::pair<Node, Cost>;    using Edges = std::vector<Edge>;    const int m_n;    std::vector<Edges> m_graph;  public:    Graph(int n) : m_n(n), m_graph(n) {}    Graph(const std::vector<Edges>& edges)        : m_n(edges.size()), m_graph(edges) {}    auto addEdge(const Node& f, const Node& t, const Cost& c = 1) {      m_graph[f].emplace_back(t, c);    }    auto addEdgeUndirected(const Node& f, const Node& t, const Cost& c = 1) {      addEdge(f, t, c);      addEdge(t, f, c);    }    auto getEdges(const Node& from) const {      class EdgesRange {        const typename Edges::const_iterator b, e;      public:        EdgesRange(const Edges& edges) : b(edges.begin()), e(edges.end()) {}        auto begin() const { return b; }        auto end() const { return e; }      };      return EdgesRange(m_graph[from]);    }    auto getEdges() const {      std::deque<std::tuple<Node, Node, Cost>> edges;      for (Node from : std::views::iota(0, m_n)) {        for (const auto& [to, c] : getEdges(from)) {          edges.emplace_back(from, to, c);        }      }      return edges;    }    auto getEdgesExcludeCost() const {      std::deque<std::pair<Node, Node>> edges;      for (Node from : std::views::iota(0, m_n)) {        for (const auto& [to, _] : getEdges(from)) {          edges.emplace_back(from, to);        }      }      return edges;    }    auto reverse() const {      auto rev = Graph<Node, Cost>(m_n);      for (const auto& [from, to, c] : getEdges()) { rev.addEdge(to, from, c); }      return rev;    }    auto size() const { return m_n; };    auto debug(bool directed = false) const {      for (const auto& [f, t, c] : getEdges()) {        if (f < t || directed) {          std::cout << f << " -> " << t << ": " << c << std::endl;        }      }    }  };}  
namespace mtd {  template <class Node, class Cost>  class EulerTour {    const std::vector<Node> m_tour;    const std::vector<std::pair<int, int>> m_appear;    auto constructTour(const Graph<Node, Cost>& tree, Node root) const {      auto n = tree.size();      std::vector<Node> tour;      std::stack<Node> stk;      std::vector<int> used(n);      stk.emplace(root);      while (!stk.empty()) {        auto from = stk.top();        tour.emplace_back(from);        stk.pop();        if (used[from]) { continue; }        stk.emplace(from);        used[from] = true;        for (auto [to, _] : tree.getEdges(from)) {          if (!used[to]) { stk.emplace(to); }        }      }      return tour;    }    auto constructAppear(int n) const {      std::vector<std::pair<int, int>> appear(n, {-1, -1});      for (int i = 0; i < 2 * n; ++i) {        if (appear[m_tour[i]].first == -1) {          appear[m_tour[i]].first = i;        } else {          appear[m_tour[i]].second = i;        }      }      return appear;    }  public:    EulerTour(const Graph<Node, Cost>& tree, Node root = 0)        : m_tour(constructTour(tree, root)),          m_appear(constructAppear(tree.size())) {}    auto lessOrder(int li, int ri) const {      return m_appear[li].first < m_appear[ri].first;    }    auto isSon(Node son, Node parent) {      return m_appear[parent].first < m_appear[son].first &&             m_appear[son].second < m_appear[parent].second;    }    auto range(Node u) const { return m_appear[u]; }  };}  

signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

  int n, q;
  std::cin >> n >> q;
  auto tree = mtd::Graph<>(n);
  for ([[maybe_unused]] auto _ : std::views::iota(0, n - 1)) {
    int a, b;
    std::cin >> a >> b;
    tree.addEdgeUndirected(a - 1, b - 1);
  }

  auto et = mtd::EulerTour(tree);
  std::vector<int> size(n);
  for (auto i : std::views::iota(0, n)) {
    auto [l, r] = et.range(i);
    size[i] = (r - l + 1) / 2;
  }

  long long ans = 0;
  for ([[maybe_unused]] auto _ : std::views::iota(0, q)) {
    int p;
    long long x;
    std::cin >> p >> x;
    ans += x * size[p - 1];
    std::cout << ans << std::endl;
  }
}
0