結果

問題 No.399 動的な領主
コンテスト
ユーザー tnakao0123
提出日時 2016-07-17 19:22:10
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 192 ms / 2,000 ms
コード長 2,495 bytes
コンパイル時間 1,338 ms
コンパイル使用メモリ 95,284 KB
実行使用メモリ 17,664 KB
最終ジャッジ日時 2024-11-07 19:31:44
合計ジャッジ時間 3,946 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/* -*- coding: utf-8 -*-
 *
 * 399.cc: No.399 動的な領主 - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;
const int BN = 17;

/* typedef */

typedef long long ll;
typedef vector<int> vi;
typedef queue<int> qi;

struct Stat {
  int i, p, d;
  Stat() {}
  Stat(int _i, int _p, int _d): i(_i), p(_p), d(_d) {}
};

/* global variables */

vi nbrs[MAX_N];
int ds[MAX_N], prts[MAX_N][BN], cns[MAX_N], ts[MAX_N];

/* subroutines */

/* main */

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int ai, bi;
    cin >> ai >> bi;
    ai--, bi--;
    nbrs[ai].push_back(bi);
    nbrs[bi].push_back(ai);
  }

  ds[0] = 0;
  prts[0][0] = -1;
  cns[0] = nbrs[0].size();

  queue<Stat> q;
  q.push(Stat(0, -1, 0));

  while (! q.empty()) {
    Stat u = q.front(); q.pop();
    vi &nbru = nbrs[u.i];
    int vd = u.d + 1;

    for (vi::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {
      int &vi = *vit;
      if (vi != u.p) {
	ds[vi] = vd;
	prts[vi][0] = u.i;
	cns[vi] = nbrs[vi].size() - 1;
	q.push(Stat(vi, u.i, vd));
      }
    }
  }

  for (int i = 1; i < BN; i++)
    for (int j = 0; j < n; j++) {
      int &p = prts[j][i - 1];
      prts[j][i] = (p < 0) ? -1 : prts[p][i - 1];
    }

  int m;
  cin >> m;

  while (m--) {
    int ai, bi;
    cin >> ai >> bi;
    ai--, bi--;

    int u = ai, v = bi;
    if (ds[u] > ds[v]) swap(u, v);

    for (int i = BN - 1; i >= 0; i--)
      if (((ds[v] - ds[u]) >> i) & 1) v = prts[v][i];

    if (u != v) {
      for (int i = BN - 1; i >= 0; i--)
	if (prts[u][i] != prts[v][i])
	  u = prts[u][i], v = prts[v][i];
      u = prts[u][0];
    }

    ts[ai]++;
    ts[bi]++;
    ts[u]--;
    if (prts[u][0] >= 0) ts[prts[u][0]]--;
  }

  qi qq;
  for (int i = 0; i < n; i++)
    if (cns[i] == 0) qq.push(i);

  while (! qq.empty()) {
    int u = qq.front(); qq.pop();
    int v = prts[u][0];
    if (v >= 0) {
      ts[v] += ts[u];
      if (--cns[v] == 0) qq.push(v);
    }
  }
  //for (int i = 0; i < n; i++) printf("%d ", ts[i]); putchar('\n');

  ll sum = 0;
  for (int i = 0; i < n; i++) {
    ll t = ts[i];
    sum += t * (t + 1) / 2;
  }
  printf("%lld\n", sum);
  return 0;
}
0