結果

問題 No.399 動的な領主
ユーザー sugim48sugim48
提出日時 2016-07-15 22:53:28
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 92 ms / 2,000 ms
コード長 2,146 bytes
コンパイル時間 991 ms
コンパイル使用メモリ 101,996 KB
実行使用メモリ 17,280 KB
最終ジャッジ日時 2024-11-07 19:09:33
合計ジャッジ時間 2,971 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
6,016 KB
testcase_01 AC 3 ms
6,016 KB
testcase_02 AC 3 ms
6,016 KB
testcase_03 AC 4 ms
5,888 KB
testcase_04 AC 3 ms
6,144 KB
testcase_05 AC 10 ms
6,528 KB
testcase_06 AC 92 ms
11,136 KB
testcase_07 AC 91 ms
11,264 KB
testcase_08 AC 89 ms
11,264 KB
testcase_09 AC 89 ms
11,264 KB
testcase_10 AC 5 ms
6,016 KB
testcase_11 AC 9 ms
6,528 KB
testcase_12 AC 66 ms
11,904 KB
testcase_13 AC 66 ms
11,776 KB
testcase_14 AC 63 ms
17,280 KB
testcase_15 AC 61 ms
17,152 KB
testcase_16 AC 60 ms
14,080 KB
testcase_17 AC 89 ms
11,136 KB
testcase_18 AC 88 ms
11,392 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'void dfs_hl(int, int)':
main.cpp:72:17: warning: 'x' may be used uninitialized [-Wmaybe-uninitialized]
   72 |                 if (v == x) id[v] = id[u];
      |                 ^~
main.cpp:62:13: note: 'x' was declared here
   62 |         int x, ma = 0;
      |             ^

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
// struct edge { int u, v; ll w; };
 
int INF = INT_MAX;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;
 
int N;
vector<int> G[100010];
int sz[100010], dep[100010];
int M = 1;
int id[100010], par[100010];
int unko[100010], pr[100010];
 
void dfs_sz(int u, int p) {
	sz[u] = 1;
	for (int v: G[u]) {
		if (v == p) continue;
		dfs_sz(v, u);
		sz[u] += sz[v];
	}
}
 
void dfs_dep(int u, int p) {
	for (int v: G[u]) {
		if (v == p) continue;
		dep[v] = dep[u] + 1;
		pr[v] = u;
		dfs_dep(v, u);
	}
}
 
void dfs_hl(int u, int p) {
	int x, ma = 0;
	for (int v: G[u]) {
		if (v == p) continue;
		if (sz[v] > ma) {
			x = v;
			ma = sz[v];
		}
	}
	for (int v: G[u]) {
		if (v == p) continue;
		if (v == x) id[v] = id[u];
		else {
			id[v] = M;
			par[M] = u;
			M++;
		}
		dfs_hl(v, u);
	}
}

void dfs_unko(int u, int p) {
	for (int v: G[u]) {
		if (v == p) continue;
		dfs_unko(v, u);
		unko[u] += unko[v];
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		int u, v; scanf("%d%d", &u, &v);
		u--; v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs_sz(0, N);
	dep[N] = -1;
	dfs_dep(0, N);
	par[0] = N;
	dfs_hl(0, N);
	int Q; cin >> Q;
	while (Q--) {
		int u, v; scanf("%d%d", &u, &v);
		u--; v--;
		unko[u]++; unko[v]++;
		while (id[u] != id[v]) {
			int U = par[id[u]], V = par[id[v]];
			if (dep[U] > dep[V]) u = U;
			else v = V;
		}
		int x = (dep[u] < dep[v] ? u : v);
		unko[x]--;
		if (x) unko[pr[x]]--;
	}
	dfs_unko(0, N);
	ll ans = 0;
	for (int u = 0; u < N; u++)
		ans += (ll)unko[u] * (unko[u] + 1) / 2;
	cout << ans << endl;
}
0