Party at Hali-Bula

http://acm.pku.edu.cn/JudgeOnline/problem?id=3342

Description

Dear Contestant,

I'm going to have a party at my villa at Hali-Bula to celebrate my retirement from BCM. I wish I could invite all my co-workers, but imagine how an employee can enjoy a party when he finds his boss among the guests! So, I decide not to invite both an employee and his/her boss. The organizational hierarchy at BCM is such that nobody has more than one boss, and there is one and only one employee with no boss at all (the Big Boss)! Can I ask you to please write a program to determine the maximum number of guests so that no employee is invited when his/her boss is invited too? I've attached the list of employees and the organizational hierarchy of BCM.

Best,
--Brian Bennett

P.S. I would be very grateful if your program can indicate whether the list of people is uniquely determined if I choose to invite the maximum number of guests with that condition.

Input

The input consists of multiple test cases. Each test case is started with a line containing an integer n (1 ≤ n ≤ 200), the number of BCM employees. The next line contains the name of the Big Boss only. Each of the following n-1 lines contains the name of an employee together with the name of his/her boss. All names are strings of at least one and at most 100 letters and are separated by blanks. The last line of each test case contains a single 0.

Output

For each test case, write a single line containing a number indicating the maximum number of guests that can be invited according to the required condition, and a word Yes or No, depending on whether the list of guests is unique in that case.

Source

Tehran 2006


Solving

파티에 직장동료들을 초대하려 한다. 이 회사는 조직체계가 트리처럼 구성되어 있다. 즉 한 사람의 상사가 두 명이 될 수 없고 상사가 없는 사람은 딱 한 명 있다(사장정도??). 어느 누구도 자신의 바로 위 상사와 같이 파티에 참석하고 싶어하지 않기 때문에 파티에는 어떤 사람을 그 사람의 직속상사와 같이 초대하지 않는다. 조직도가 주어졌을 때, 이 파티에 초대할 수 있는 최대한의 사람 수와 그 경우 초대가능한 형태가 유일한지를 구하라.

각 사원을 노드로 두고 직속상사와 부하사이에 연결성이 있다고 보면 이 문제를 트리의 형태로 변환할 수 있다.

우선 초대할 수 있는 최대한의 사람 수를 구하자.

각 노드(사원)는 정보로 그 노드를 포함 시켰을 때 그 노드를 루트로 하는 서브트리의 최대값과 노드를 포함 시키지 않았을 때의 최대값을 값는다. 어떤 노드를 포함시켰다면, 그 자식노드는 무조건 포함 시킬 수 없고, 어떤 노드를 포함시키지 않았다면 그 자식노드를 포함시킬 수도 있고 포함시키지 않을 수도 있다. 수식을 세워보자
어떤 노드 n1을 포함시켰을 때의 최대값을 v1, 포함시키지 않았을 때의 최대값을 v2라 하면, v1과 v2는 다음과 같이 구할 수 있다.

v1 = sum(n1의 자식노드.v2)
v2 = sum(max(n1의 자식노드.v1, n1의 자식노드.v2))

위의 점화식을 DP나 재귀호출로 수행하여 트리의 루트노드의 v1과 v2중 더 큰 값이 초대할 수 있는 수가 된다.

이제 초대할 수 있는 경우가 유일한지 아닌지 생각해보자.

노드 n의 v1과 v2가 같은 경우 루트노드를 포함시킨 결과와 포함시키지 않은 결과의 초대할 수 있는 최대값이 같기 때문에 유일하게 결정되지 않는다. v1 > v2의 경우 노드 n을 포함시켜야 하며, v1 < v2의 경우 r을 포함시키지 않아야 한다. n을 포함시키는 경우 n의 자식은 선택의 여지 없이 포함되지 않으며, n이 포함되지 않는 경우 n의 자식은 포함시킬 수 도 있고 포함시키지 않을 수도 있다. n의 자식에 대해서 똑같은 연산을 반복하면서 포함 시킬 수 있는 노드 중 v1 == v2인 경우가 있는지 검사한다.

#include <cstdlib> #include <cstdio> #include <iostream> #include <string> #include <map> #include <vector> #include <memory> using namespace std; #define max(a,b) (((a) > (b)) ? (a) : (b)) struct INVITE { int yes; int no; }; int n; int mem[201][201] = {0}; INVITE invite[201]; bool isunique = true; INVITE go(int index) { int i = 0; invite[index].yes = 0; invite[index].no = 0; for (i = 0; i < n; i++) { if (mem[index][i] != -1) { INVITE temp = go(i); invite[index].yes += temp.no; invite[index].no += max(temp.yes, temp.no); } } ++invite[index].yes; return invite[index]; } void Unique(int index, bool yesno) { if (isunique == false) return; int i = 0; for (i = 0; i < n; i++) { if (mem[index][i] != -1) { if (yesno == true) { Unique(i, false); } else { if (invite[i].yes == invite[i].no) { isunique = false; return; } else if (invite[i].yes > invite[i].no) Unique(i, true); else Unique(i, false); } } } } int main() { int i, j; string buffer1, buffer2; while ((cin >> n)) { if (n == 0) break; map<string, string> cmap; vector<string> emps; int count = 0; memset(mem, 0xFF, sizeof(mem)); memset(invite, 0x00, sizeof(invite)); isunique = true; cin >> buffer1; cmap[buffer1] = ""; emps.push_back(buffer1); for (i = 1; i < n; i++) { cin >> buffer1 >> buffer2; cmap[buffer1] = buffer2; emps.push_back(buffer1); } for (i = 0; i < n; i++) { for (j = 0; j < n; j++) if (cmap[emps[i]] == emps[j]) break; mem[j][i] = 1; } INVITE result = go(0); if (result.yes == result.no) isunique = false; else if (result.yes > result.no) Unique(0, true); else Unique(0, false); cout << max(result.yes, result.no) << " "; cout << (isunique?"Yes":"No") << endl; } return 0; }