2500.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 2500 on 2007-06-05 at 10:12:22 */
#include <cstdio>
#include <map>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 512, L = 128;

class cmp {
public:
	bool operator ()(const char* s1, const char* s2) const
		{ return strcmp(s1, s2) < 0; }
};

vector<int> g[N];
int n, maxv[N][2], kn[N][2];
char name[N][L];
map<const char*, int, cmp> dict;

int cnt(const char*);
void dfs(int, int);

int main()
{
	int m;
	while(scanf("%d", &m) != EOF && m != 0) {
		n = 0; dict.clear();
		char nm1[L], nm2[L]; scanf("%s", nm1);
		int root = cnt(nm1);
		for(int i = 0; i < N; i++) g[i].clear();
		for(int i = 1; i < m; i++) {
			scanf("%s %s", nm1, nm2);
			int a1 = cnt(nm1), a2 = cnt(nm2);
			g[a1].push_back(a2); g[a2].push_back(a1);
		}
		dfs(root, -1);
		int opt = max(maxv[root][0], maxv[root][1]), kcn = 1;
		if(maxv[root][0] == opt && kn[root][0] > 1) kcn = 2;
		if(maxv[root][1] == opt && kn[root][1] > 1) kcn = 2;
		if(maxv[root][0] == maxv[root][1]) kcn = 2;
		printf("%d %s\n", opt, kcn == 1 ? "Yes" : "No");
	}
	return 0;
}

int cnt(const char* str)
{
	if(!dict.count(str)) {
		strcpy(name[n], str);
		dict[name[n]] = n; n++;
	}
	return dict[str];
}
void dfs(int v, int p)
{
	maxv[v][0] = 0; maxv[v][1] = 1;
	kn[v][0] = kn[v][1] = 1;
	for(int i = 0; i < (int)g[v].size(); i++) {
		int u = g[v][i];
		if(u == p) continue;
		dfs(u, v);
		int all = max(maxv[u][0], maxv[u][1]);
		maxv[v][0] += all;
		if(maxv[u][0] == all && kn[u][0] > 1) kn[v][0] = 2;
		if(maxv[u][1] == all && kn[u][1] > 1) kn[v][0] = 2;
		if(maxv[u][0] == maxv[u][1]) kn[v][0] = 2;
		maxv[v][1] += maxv[u][0];
		if(maxv[u][0] == all && kn[u][0] > 1) kn[v][1] = 2;
	}
}