結果

問題 No.399 動的な領主
ユーザー koyumeishikoyumeishi
提出日時 2016-07-13 05:22:00
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 210 ms / 2,000 ms
コード長 4,204 bytes
コンパイル時間 1,039 ms
コンパイル使用メモリ 89,156 KB
実行使用メモリ 26,828 KB
最終ジャッジ日時 2024-11-07 18:28:35
合計ジャッジ時間 4,171 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 3 ms
5,248 KB
testcase_05 AC 17 ms
5,248 KB
testcase_06 AC 210 ms
18,532 KB
testcase_07 AC 210 ms
18,660 KB
testcase_08 AC 204 ms
18,464 KB
testcase_09 AC 202 ms
18,464 KB
testcase_10 AC 4 ms
5,248 KB
testcase_11 AC 15 ms
5,248 KB
testcase_12 AC 167 ms
18,808 KB
testcase_13 AC 161 ms
18,912 KB
testcase_14 AC 136 ms
26,828 KB
testcase_15 AC 148 ms
26,760 KB
testcase_16 AC 157 ms
22,220 KB
testcase_17 AC 198 ms
18,464 KB
testcase_18 AC 195 ms
18,468 KB
権限があれば一括ダウンロードができます

ソースコード

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];
  }
};


class UnionFindTree{
  struct base_node{
    int parent;
    int rank;
    int size;
  };
  
  vector<base_node> node;
 public:
  UnionFindTree(int n){
    node.resize(n);
    for(int i=0; i<n; i++){
      node[i].parent=i;
      node[i].rank=0;
      node[i].size=1;
    }
  }

  int find(int x){  //return root node of x
    if(node[x].parent == x) return x;
    else{
      return node[x].parent = find(node[x].parent);
    }
  }
  
  bool same(int x, int y){
    return find(x) == find(y);
  }

  int size(int at){
    return node[find(at)].size;
  }

  void unite(int x, int y){
    x = find(node[x].parent);
    y = find(node[y].parent);

    if(x==y) return;

    if(node[x].rank < node[y].rank){
      node[x].parent = y;
      node[y].size += node[x].size;
    }else if(node[x].rank > node[y].rank){
      node[y].parent = x;
      node[x].size += node[y].size;
    }else{
      node[x].rank++;
      unite(x,y);
    }
  }
};


int main(){
  int n;
  cin >> n;
  assert(2<=n && n<=100000);

  UnionFindTree uft(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;

    assert(1<=u && u<=n);
    assert(1<=v && v<=n);
    assert(u != v);

    u--; v--;
    G[u].push_back(v);
    G[v].push_back(u);

    uft.unite(u,v);
  }

  assert(uft.size(0) == n);

  LCA lca(G, n);

  vector<vector<int>> d(lca.get_max_depth()+1);
  for(int i=0; i<n; i++){
    d[ lca.get_depth(i) ].push_back( i );
  }

  vector<long long> sum(n+1, 0);
  int q;
  cin >> q;
  assert(1<=q && q<=100000);
  while(q--){
    int u,v;
    cin >> u >> v;

    assert(1<=u && u<=n);
    assert(1<=v && v<=n);
    assert(u != v);

    u--; v--;
    int p = lca.get_lca(u,v);
    if(p == u || p == v){
      if(u==p) swap(u,v);
      sum[u]++;
      sum[lca.get_parent(p)]--;
    }else{
      sum[u]++;
      sum[v]++;
      sum[p]--;
      sum[lca.get_parent(p)]--;
    }
  }

  long long ans = 0;
  for(int i=d.size()-1; i>0; i--){
    for(int v : d[i]){
      ans += sum[v] * (sum[v]+1LL) / 2;
      sum[lca.get_parent(v)] += sum[v];
    }
  }

  cout << ans << endl;

  return 0;
}
0