結果

問題 No.1637 Easy Tree Query
ユーザー cutmdo
提出日時 2024-12-20 01:57:41
言語 C++23
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

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;
  }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0