結果

問題 No.399 動的な領主
ユーザー Kutimoti_TKutimoti_T
提出日時 2018-08-21 10:54:08
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 213 ms / 2,000 ms
コード長 2,408 bytes
コンパイル時間 1,808 ms
コンパイル使用メモリ 169,940 KB
実行使用メモリ 25,944 KB
最終ジャッジ日時 2023-08-21 01:46:36
合計ジャッジ時間 5,822 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 3 ms
4,380 KB
testcase_05 AC 16 ms
4,720 KB
testcase_06 AC 213 ms
18,452 KB
testcase_07 AC 210 ms
18,536 KB
testcase_08 AC 202 ms
18,760 KB
testcase_09 AC 201 ms
18,596 KB
testcase_10 AC 3 ms
4,376 KB
testcase_11 AC 15 ms
5,088 KB
testcase_12 AC 171 ms
19,000 KB
testcase_13 AC 176 ms
19,168 KB
testcase_14 AC 129 ms
25,944 KB
testcase_15 AC 141 ms
25,828 KB
testcase_16 AC 162 ms
21,900 KB
testcase_17 AC 198 ms
18,612 KB
testcase_18 AC 199 ms
18,724 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

/*

        <LowerCommonAncestor>

*/

#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Graph {
  struct edge {
    int to;
  };

  int n;
  vector<vector<edge>> edges;

  Graph(int N) {
    n = N;
    edges.resize(n, vector<edge>());
  }

  int size() const { return n; }

  vector<edge>& operator[](int v) { return edges[v]; }
};

struct Lca {
  int n;
  int log2_n;
  vector<vector<int>> parent;
  vector<int> depth;

  Lca(Graph& g, int root) {
    n = g.size();
    log2_n = floor(log2(n) + 2);
    parent.resize(log2_n, vector<int>(n));
    depth.resize(n);

    dfs(g, root, -1, 0);
    for (int k = 0; k + 1 < log2_n; k++) {
      for (int v = 0; v < n; v++) {
        if (parent[k][v] < 0)
          parent[k + 1][v] = -1;
        else
          parent[k + 1][v] = parent[k][parent[k][v]];
      }
    }
  }

  void dfs(Graph& g, int v, int p, int d) {
    parent[0][v] = p;
    depth[v] = d;
    for (auto& e : g[v]) {
      if (e.to != p) dfs(g, e.to, v, d + 1);
    }
  }

  int get(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    for (int k = 0; k < log2_n; k++) {
      if ((depth[v] - depth[u]) >> k & 1) {
        v = parent[k][v];
      }
    }
    if (u == v) return u;
    for (int k = log2_n - 1; k >= 0; k--) {
      if (parent[k][u] != parent[k][v]) {
        u = parent[k][u];
        v = parent[k][v];
      }
    }
    return parent[0][u];
  }
};

/*
checked:
        http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2723881#1
*/

int N;

i64 cnt[101010];
int main(){
  cin >> N;
  Graph g(N + 1);
  rep(i,0,N - 2){
    int u,v;
    cin >> u >> v;
    g[u].push_back({v});
    g[v].push_back({u});
  }
  Lca lca(g,1);
  int Q;
  cin >> Q;
  rep(i,0,Q - 1){
    int A,B;
    cin >> A >> B;
    cnt[A]++;
    cnt[B]++;
    int p;
    cnt[p = lca.get(A,B)]--;
    if(lca.parent[0][p] != -1){
      cnt[lca.parent[0][p]]--;
    }
  }
  vector<pair<int,int>> vec;
  rep(i,1,N){
    vec.push_back({-lca.depth[i],i});
  }
  sort(all(vec));
  i64 ans = 0;
  for(auto p : vec){
    int i = p.second;
    if(lca.parent[0][i] != -1){
      cnt[lca.parent[0][i]] += cnt[i];
    }
    ans += (cnt[i] + 1) * cnt[i] / 2;
  }
  cout << ans << endl;
}
0