結果

問題 No.5000 特殊ジャッジテスト（テスト用）
ユーザー asdasd
提出日時 2015-06-13 05:06:29
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,436 bytes
コンパイル時間 7,039 ms
実行使用メモリ 2,500 KB
スコア -872
最終ジャッジ日時 2018-03-12 00:01:28
ジャッジサーバーID
（参考情報） 		judge6 /
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 TLE -
権限があれば一括ダウンロードができます

ソースコード

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