1.树形dp
题目描述:每个公司开party,但是开party的时候,和老板呆在一起会很不自在(每个人仅有一个老板,自己老板的老板不是老板),现在给出员工关系.
Now your task is to find the maximum number of employees that may attend the party with the above conditions and the number of different ways to achieve that goal. Two ways are considered different if the list of guests invited are not all the same.
Input
The first line of the input contains an integer T (1 ≤ T ≤ 10), which indicates the number of test cases. Then follows T cases.
Each test case is started with a line containing an integer n (1 ≤ n ≤ 100), then follows n lines, each contains 2 strings P (the name of an employee) and T (the name of his boss), both with less than 30 characters.
It is guaranteed that all of the employees are in the description, every employee has a unique name and have no more than one boss.
Output
For each test case, please output the maximum number of employees to attend the party and the number of different ways modulo 1000000007.
Sample Input
2
1
Person Boss
3
Tom David
Jim David
Sam Tom
这里有几个问题:
1.map的一些使用方式(有助于把字符映射到整数上去);
2.树形dp(决定最优决策和决策树)
这个问题本质上会变成一个并查集问题:
2.二分图的最大匹配问题: