結果

問題 No.95 Alice and Graph
ユーザー asdasd
提出日時 2015-06-13 05:08:48
言語 C++11
(gcc 11.4.0)
結果
MLE  
実行時間 -
コード長 1,436 bytes
コンパイル時間 369 ms
コンパイル使用メモリ 46,628 KB
実行使用メモリ 813,992 KB
最終ジャッジ日時 2023-09-20 21:10:48
合計ジャッジ時間 4,387 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define MX 10005
using namespace std;

vector<int> adj[MX];
int N, len;
int dp[MX], pr[MX];
int deg[MX];

void dfs(int u, int p, int d) {
	dp[u] = d;
	pr[u] = p;
	int i, v;
	for (i = 0; i < adj[u].size(); i++) {
		v = adj[u][i];
		if (v != p) dfs(v, u, d + 1);
	}
}

int calc(int u, int p, int d) {
	int ret = 0, i, v;
	for (i = 0; i < adj[u].size(); i++) {
		v = adj[u][i];
		if (v != p) ret += !!calc(v, u, d + 1);
	}
	if (d == len / 2) return deg[u] = 1;
	return deg[u] = ret;
}

int main() {
	
	int T, u, v, i, j, k;
	for (scanf("%d", &T); T--; ) {
		scanf("%d", &N);
		for (i = 1; i <= N; i++) {
			adj[i].clear();
			deg[i] = 0;
		}
		for (i = 0; i < N - 1; i++) {
			scanf("%d%d", &u, &v);
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		if (N == 2) {
			puts("NO");
			continue;
		}
		
		len = 0;
		dfs(1, 0, 0);
		for (i = 1; i <= N; i++) len = max(len, dp[i]);
		for (i = 1; i <= N; i++) if (dp[i] == len) {
			dfs(i, 0, 0);
			break;
		}
		
		for (i = 1; i <= N; i++) len = max(len, dp[i]);
		
		k = len / 2;
		for (i = 1; i <= N; i++) if (dp[i] == len) {
			u = i;
			while (k--) u = pr[u];
			break;
		}
		if (len & 1) {
			v = pr[u];
			calc(u, v, 0);
			calc(v, u, 0);
			if (deg[u] == 1 || deg[v] == 1) puts("YES");
			else puts("NO");
		} else {
			calc(u, 0, 0);
			if (deg[u] <= 2) puts("YES");
			else puts("NO");
		}
	}
	return 0;
}
0