結果

問題 No.399 動的な領主
ユーザー koyumeishikoyumeishi
提出日時 2016-07-13 05:24:11
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,995 bytes
コンパイル時間 958 ms
コンパイル使用メモリ 84,840 KB
実行使用メモリ 25,400 KB
最終ジャッジ日時 2024-10-14 15:32:14
合計ジャッジ時間 7,645 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,496 KB
testcase_01 AC 1 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 18 ms
5,248 KB
testcase_06 AC 486 ms
16,572 KB
testcase_07 AC 490 ms
16,464 KB
testcase_08 AC 386 ms
16,520 KB
testcase_09 AC 353 ms
16,648 KB
testcase_10 AC 3 ms
5,248 KB
testcase_11 AC 12 ms
5,248 KB
testcase_12 AC 155 ms
17,120 KB
testcase_13 AC 149 ms
17,100 KB
testcase_14 TLE -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cassert>
#include <functional>
#include <algorithm>
using namespace std;

class LCA{

  int root;
  //depth of node[i]
  vector<int> d;
  
  //parent of node[i]
  vector<vector<int> > p;

  
  int size;
  
  //initialization of depths and parents
  void init(vector<vector<int> > &g, int pos, int last, int v){
    d[pos] = v;
    p[0][pos] = last;
    for(int i=0; i<g[pos].size(); i++){
      if(g[pos][i] == last) continue;
      init(g, g[pos][i], pos, v+1);
    }
  }

 public:

  //vector<vector<int> >
  //g[i][j] := node[i]'s edge gose to node[ g[i][j] ]
  
  LCA(vector<vector<int> > &g, int r){
    int n = g.size();
    root = r;
    d = vector<int>(n);

    size = 1;
    while((1<<size) <= n){
      size++;
    }
    
    p = vector<vector<int> >(size, vector<int>(n));
    
    init(g, root,-1,0);
    
    for(int k=0; k+1 < size; k++){
      for(int v=0; v<n; v++){
        if(p[k][v] < 0) p[k+1][v] = -1;
        else p[k+1][v] = p[k][p[k][v]];
      }
    }
  }
  
  LCA(vector<vector<int> > &g){
    int n = g.size();
    root = 0;
    d = vector<int>(n);
    size = 1;
    while((1<<size) <= n){
      size++;
    }
    p = vector<vector<int> >(size, vector<int>(n));

    //initialize as root = 0
    init(g, root,-1,0);
    
    for(int k=0; k+1 < size; k++){
      for(int v=0; v<n; v++){
        if(p[k][v] < 0) p[k+1][v] = -1;
        else p[k+1][v] = p[k][p[k][v]];
      }
    }
  }
  
  //return the node number of lowest common ancestor between u and v
  int get_lca(int u, int v){
    if(d[u] > d[v]) swap(u,v);
    for(int k=0; k<size; k++){
      if( (d[v] - d[u]) >> k & 1){
        v = p[k][v];
      }
    }
    if(u==v) return u;

    for(int k=size-1; k>=0; k--){
      if(p[k][u] != p[k][v]) {
        u = p[k][u];
        v = p[k][v];
      }
    }
    return p[0][u];
  }

  //return depth of node[u]
  int get_depth(int u){
    return d[u];
  }
  int get_max_depth(){
    return *max_element(d.begin(), d.end());
  }
  int get_parent(int u){
    return p[0][u];
  }
};

int main(){
  int n;
  cin >> n;
  vector<vector<int>> G(n+1);
  G[n].push_back(0);
  G[0].push_back(n);
  for(int i=0; i<n-1; i++){
    int u,v;
    cin >> u >> v;
    u--; v--;
    G[u].push_back(v);
    G[v].push_back(u);
  }

  LCA lca(G, n);

  long long ans = 0;

  vector<long long> num_visit(n+1, 0);

  int q;
  cin >> q;
  while(q--){
    int u,v;
    cin >> u >> v;
    u--; v--;

    int p = lca.get_lca(u,v);
    if(p == u || p == v){
      if(u==p) swap(u,v);
      while(1){
        num_visit[u]++;
        ans += num_visit[u];
        if(u == p) break;
        u = lca.get_parent(u);
      }
    }else{
      while(1){
        num_visit[u]++;
        ans += num_visit[u];
        if(u == p) break;
        u = lca.get_parent(u);
      }
      while(1){
        if(v == p) break;
        num_visit[v]++;
        ans += num_visit[v];
        v = lca.get_parent(v);
      }
    }
  }

  cout << ans << endl;

  return 0;
}
0