結果

問題 No.399 動的な領主
ユーザー Min_25Min_25
提出日時 2017-09-17 13:31:35
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 33 ms / 2,000 ms
コード長 5,124 bytes
コンパイル時間 1,159 ms
コンパイル使用メモリ 105,196 KB
実行使用メモリ 12,928 KB
最終ジャッジ日時 2024-11-08 01:52:56
合計ジャッジ時間 3,425 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 4 ms
5,248 KB
testcase_06 AC 33 ms
8,156 KB
testcase_07 AC 33 ms
8,188 KB
testcase_08 AC 32 ms
8,060 KB
testcase_09 AC 32 ms
8,156 KB
testcase_10 AC 3 ms
5,248 KB
testcase_11 AC 4 ms
5,248 KB
testcase_12 AC 24 ms
8,264 KB
testcase_13 AC 24 ms
8,188 KB
testcase_14 AC 18 ms
12,796 KB
testcase_15 AC 18 ms
12,928 KB
testcase_16 AC 17 ms
10,492 KB
testcase_17 AC 32 ms
8,064 KB
testcase_18 AC 32 ms
8,060 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstring>

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <stack>
#include <queue>

#include <tuple>

#define getchar getchar_unlocked
#define putchar putchar_unlocked

#define _rep(_1, _2, _3, _4, name, ...) name
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c))
#define rep(...) _rep(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__)

using namespace std;

using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f80 = long double;

int get_int() {
  int c, n;
  while ((c = getchar()) < '0');
  n = c - '0';
  while ((c = getchar()) >= '0') n = n * 10 + (c - '0');
  return n;
}

class RootedTree {
private:
  struct InputEdge { int from, to; };

  template <typename T>
  struct Range {
    struct Iterator {
      T& operator * () const { return *iter; }
      bool operator != (const Iterator& rhs) const { return iter != rhs.iter; }
      void operator ++ () { ++iter; }
      T* operator + (int i) const { return iter + i; }
      size_t operator - (const Iterator rhs) const { return iter - rhs.iter; }
      T* iter;
    };
    Range(T* f, T* l) : first({f}), last({l}) {}
    T operator [] (int i) { return *(first + i); }
    size_t size() const { return last - first; }
    Iterator& begin() { return first; }
    Iterator& end() { return last; }
    Iterator first, last;
  };

public:
  RootedTree(int N, int M=0) 
      : N(N), ofs(N + 1), 
        par(N), vid(N), head(N), heavy(N), len(N) {
    if (M > 0) in.reserve(M);
  }
  Range<int> operator [] (int u) { 
    return Range<int>(&edges[ofs[u]], &edges[ofs[u + 1]]); 
  }
  void add_edge(int u, int v) { in.push_back({u, v}); }
  void build(int root) { init(), dfs(root), bfs(root); }
  int lca(int u, int v) const {
    for (; head[u] != head[v]; u = par[head[u]]) if (vid[u] < vid[v]) swap(u, v);
    return vid[u] > vid[v] ? v : u;
  }
  
  pair< vector<int>, vector< pair<int, int> > > signed_euler_tour(int root) {
    range.resize(N);
    tour.resize(2 * N);
    int id = 0;
    e_rec(root, id);
    return {tour, range};
  }

  vector<int> get_path(int u, int v) const {
    vector<int> pu, pv; int s = 0;
    while (head[u] != head[v]) {
      if (vid[u] < vid[v]) swap(u, v), swap(pu, pv), s ^= 1;
      for (int w = par[head[u]]; u != w; u = par[u]) pu.push_back(u);
    }
    if (vid[u] < vid[v]) swap(u, v), swap(pu, pv), s ^= 1;
    for (; vid[u] != vid[v]; u = par[u]) pu.push_back(u);
    pu.push_back(u);
    if (s) swap(pu, pv);
    reverse(pv.begin(), pv.end());
    for (auto& w : pv) pu.push_back(w);
    return pu;
  }

  int parent(int u) const { return par[u]; }

  vector<int> get_order() const {
    vector<int> order(N);
    for (int i = 0; i < N; ++i) order[vid[i]] = i;
    return order;
  }

private:
  void e_rec(int u, int& id, int p=-1) {
    tour[id] = u;
    range[u].first = id++;
    for (auto& v : (*this)[u]) if (v != p) e_rec(v, id, u);
    tour[id] = ~u;
    range[u].second = id++;
  }

  void bfs(int root) {
    vector<int> que(N); 
    int qh = 0, qt = 0, id = 0;
    que[qt++] = root;
    for (; qh < qt; ) {
      int u = que[qh++];
      for (int v = u; v >= 0; v = heavy[v]) {
        vid[v] = id++, head[v] = u;
        for (auto& w : (*this)[v]) if (w != par[v] && w != heavy[v]) que[qt++] = w;
      }
      len[u] = id - vid[u];
    }
  }

  int dfs(int u, int p=-1) {
    int s = 1, best = 0, h = -1;
    par[u] = p;
    for (auto& v : (*this)[u]) if (v != p) {
      int c = dfs(v, u);
      if (c > best) best = c, h = v;
      s += c;
    }
    heavy[u] = h;
    return s;
  }

  void init() {
    edges.resize(2 * in.size());
    for (auto& e : in) ofs[e.from + 1]++, ofs[e.to + 1]++;
    for (int i = 1; i <= N; ++i) ofs[i] += ofs[i - 1];
    for (auto& e : in) edges[ofs[e.from]++] = e.to, edges[ofs[e.to]++] = e.from;
    for (int i = N; i > 0; --i) ofs[i] = ofs[i - 1];
    ofs[0] = 0;
  }

private:
  int N;
  vector<InputEdge> in;
  vector<int> ofs, edges;

  vector<int> par, vid, head, heavy, len;

  vector< pair<int, int> > range;
  vector<int> tour;
};

void solve() {
  int N;
  while (~scanf("%d", &N)) {
    auto g = RootedTree(N);
    rep(i, N - 1) {
      int u = get_int() - 1, v = get_int() - 1;
      g.add_edge(u, v);
    }
    g.build(0);
    vector<int> cumu(N);
    int M = get_int();
    rep(i, M) {
      int u = get_int() - 1, v = get_int() - 1;
      int lca = g.lca(u, v), p = g.parent(lca);
      cumu[u] += 1;
      cumu[v] += 1;
      cumu[lca] -= 1;
      if (p >= 0) cumu[p] -= 1;
    }
    auto order = g.get_order();
    i64 ans = 0;
    rep(i, N) {
      int u = order[N - 1 - i], p = g.parent(u);
      ans += i64(cumu[u]) * (cumu[u] + 1) / 2;;
      if (p >= 0) cumu[p] += cumu[u];
    }
    printf("%lld\n", ans);
  }
}

int main() {
  clock_t beg = clock();
  solve();
  clock_t end = clock();
  fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC);
  return 0;
}
0