結果

問題 No.399 動的な領主
ユーザー HaruiHarui
提出日時 2024-07-30 23:57:26
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 242 ms / 2,000 ms
コード長 5,355 bytes
コンパイル時間 1,680 ms
コンパイル使用メモリ 112,804 KB
実行使用メモリ 17,280 KB
最終ジャッジ日時 2024-07-30 23:57:32
合計ジャッジ時間 5,275 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 3 ms
6,940 KB
testcase_05 AC 18 ms
6,944 KB
testcase_06 AC 214 ms
12,416 KB
testcase_07 AC 242 ms
12,416 KB
testcase_08 AC 214 ms
12,672 KB
testcase_09 AC 213 ms
12,672 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 17 ms
6,944 KB
testcase_12 AC 177 ms
13,056 KB
testcase_13 AC 179 ms
13,056 KB
testcase_14 AC 154 ms
17,272 KB
testcase_15 AC 134 ms
17,280 KB
testcase_16 AC 149 ms
15,872 KB
testcase_17 AC 222 ms
12,672 KB
testcase_18 AC 220 ms
12,672 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "playground_A.cpp"
#include <iostream>
#line 1 "/home/samejima/CompetitiveProgramming/library/graph/tree/heavy_light_decomposition.hpp"



#include <vector>
#include <algorithm>
#include <cassert>
#include <utility>

#line 1 "/home/samejima/CompetitiveProgramming/library/graph/graph_template.hpp"



#line 5 "/home/samejima/CompetitiveProgramming/library/graph/graph_template.hpp"

template <typename T>
struct Edge {
  int from; int to;
  T cost;

  Edge(int _from, int _to, T _cost) : from(_from), to(_to), cost(_cost) {}

  // unweighted
  Edge(int _from, int _to) : from(_from), to(_to), cost(T(1)) {}

  bool operator==(const Edge& rhs) {
    return from == rhs.from && to == rhs.to && cost == rhs.cost;
  }

};


template <typename T>
struct Graph : std::vector<std::vector<Edge<T>>> {

  using std::vector<std::vector<Edge<T>>>::vector; // inherit constructors

  void add_edge(int i, Edge<T> e) {
    (*this)[i].push_back(e);
  }

  // weighted
  void add_edge(int _from, int _to, T _cost) {
    (*this)[_from].push_back(Edge(_from, _to, _cost));
  }

  // unweighted
  void add_edge(int _from, int _to) {
    (*this)[_from].push_back(Edge(_from, _to, T(1)));
  }

};


#line 10 "/home/samejima/CompetitiveProgramming/library/graph/tree/heavy_light_decomposition.hpp"

// cf : https://ngtkana.hatenablog.com/entry/2024/06/24/200138
struct Interval {
  // i : interval のもっとも根に近い頂点のid
  // j : interval のもっとも葉に近い頂点のid
  // last : LCAを含む interval であるかどうか
  // reverse : from → to と i → jが逆向きかどうか
  int i, j;
  bool last;
  bool reverse;

  Interval(int _i, int _j, bool _last, bool _reverse) : i(_i), j(_j), last(_last), reverse(_reverse) {

  }
};

using Path = std::vector<Interval>;

struct HLD {

  //vector<vector<int>>children;
  std::vector<int>parent;
  std::vector<int> id;
  std::vector<int> id2;
  std::vector<int> head;
  std::vector<int>depth;
  Graph<int>graph;

  HLD (int N) : parent(std::vector<int>(N, -1)), id(std::vector<int>(N)), id2(std::vector<int>(N)), head(std::vector<int>(N)), depth(std::vector<int>(N)), graph(N) {}

  void build(int root=0) {
    dfs_sz(root);
    int k = 0; dfs_hld(root, k);
  }

  int dfs_sz(int v) {
    int ret = 1, mx_sz = 0;
    for (Edge<int>& nxt : graph[v]) {
      if (nxt.to == parent[v]) continue;

      parent[nxt.to] = v;
      depth[nxt.to] = depth[v] + 1;
      int sz = dfs_sz(nxt.to);
      ret += sz;
      if (mx_sz < sz) {
        mx_sz = sz;
        std::swap(graph[v][0], nxt);
      }
    }

    return ret;
  }

  void dfs_hld(int v, int& k) {
    id[v] = k; k++;
    for (Edge e : graph[v]) {
      if (e.to == parent[v]) continue;

      head[e.to] = (e == graph[v][0] ? head[v] : e.to);
      dfs_hld(e.to, k);
    }
    id2[v] = k;
  }

  int lca(int u, int v) {
    while (true) {
      if (id[u] > id[v]) std::swap(u, v);
      if (head[u] == head[v]) return u;

      v = parent[head[v]];
    }
  }

  Path get_path(int u, int v) {
    Path upath, vpath;

    while (head[u] != head[v]) {

      // ちなみにu,vのdepthの大小関係は変わり続けることもある。
      // 10 → 12など。

      // v's head is deeper
      if (depth[head[v]] >= depth[head[u]]) {
        assert(depth[head[v]] >= depth[head[u]]);
        /*
          /   : heavy edge
         .... : light edge

            head[u]
               /
              /...
             u  ...
            /   head[v]
           /       \
          /         \
         /           v
        */

        // u→v なのでreverse=false
        vpath.emplace_back(id[head[v]], id[v], false, false);
        v = parent[head[v]];
      }

      // u's head is deeper
      else if (depth[head[v]] < depth[head[u]]) {
        /*
          /   : heavy edge
         .... : light edge

            head[v]
               /
              /...
             v  ...
            /   head[u]
           /       \
          /         \
         /           u
        */

        //
        upath.emplace_back(id[head[u]], id[u], false, true);
        u = parent[head[u]];
      }
    }

    // v is deeper
    /*
       u
      /
     /  ←↓
    /
   v

    */
    if (depth[v] > depth[u]) {
      upath.emplace_back(id[u], id[v], true, false);
    }

    // u is deeper
    /*
       v
      /
     /  →↑
    /
   u

    */
    else {
      upath.emplace_back(id[v], id[u], true, true);
    }
    Path retpath = upath;
    reverse(vpath.begin(), vpath.end());
    for (Interval path : vpath) retpath.push_back(path);

    return retpath;
  }

  std::pair<int,int> subtree_query(int r) {
    assert(r < int(id.size()));
    return std::make_pair(id[r], id2[r]);
  }

};


#line 3 "playground_A.cpp"

using namespace std;

int main() {
  int N; cin >> N;
  HLD hld(N);
  for (int i=0; i<N-1; i++) {
    int u, v; cin >> u >> v;
    u--;
    v--;
    hld.graph.add_edge(u,v);
    hld.graph.add_edge(v,u);
  }
  hld.build();
  vector<long> cusum(N+1);
  int Q; cin >> Q;
  for (int q=0; q<Q; q++) {
    int A, B; cin >> A >> B;
    A--;
    B--;

    for (Interval intv : hld.get_path(A,B)) {
      cusum[intv.i] += 1;
      cusum[intv.j+1] -= 1;
    }
  }

  long ans = 0;
  for (int i=0; i<N; i++) {
    cusum[i+1] += cusum[i];
    ans += cusum[i] * (cusum[i] + 1) / 2;
  }

  cout << ans << endl;
}
0