/*
树形dp!
判重思路:
当dp[v][0]==dp[v][1]时,很自然,flag[u][0]必然是有两种方案的。flag[u][1]则不然,
因为它只和dp[v][0]有关系。而若flag[v][0]不唯一时,则必然flag[u][1]也不唯一
也就是u的子节点有dp[v][1]==dp[v][0](选与不选都一样),那么父节点u不选的时候一定会有
多种方案!也就是flag[u][0]=false; 否则如果flag[v][0]==flase(子节点不选的时候有多种方案),
那么父节点u选择的时候一定有多种方案,则flag[u][1]=false;
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<map>
#include<algorithm>
#define N 205
using namespace std; map<string, int>mp;
int n;
int cnt;
int g[N][N];
int dp[N][];
bool flag[N][];
map<string, int>::iterator it; void dfs(int u){
for(int v=; v<=n; ++v)
if(g[u][v]){
dfs(v);
dp[u][]+=dp[v][];
dp[u][]+=max(dp[v][], dp[v][]);
if(dp[v][]==dp[v][]) flag[u][]=false;
if(flag[v][]==false) flag[u][]=false;
}
} int main(){
string na1, na2;
while(scanf("%d", &n) && n){
mp.clear();
memset(g, , sizeof(g));
cnt=;
cin>>na1;
mp[na1]=++cnt;
for(int i=; i<n; ++i){
dp[i][]=;
dp[i][]=;
flag[i][]=flag[i][]=true;
cin>>na1>>na2;
it=mp.find(na1);
if(it==mp.end())
mp[na1]=++cnt;
it=mp.find(na2);
if(it==mp.end())
mp[na2]=++cnt;
g[mp[na2]][mp[na1]]=;
}
dp[n][]=;
dp[n][]=;
flag[n][]=flag[n][]=true;
dfs();
if(dp[][]>dp[][] && flag[][]) printf("%d %s\n", dp[][], "Yes");
else if(dp[][]>dp[][] && flag[][]) printf("%d %s\n", dp[][], "Yes");
else printf("%d %s\n", max(dp[][], dp[][]), "No");
}
return ;
}

最新文章

  1. Swift来的正是时候
  2. scala多个构造函数的定义方法
  3. Python3基础 assert关键字 成功啥事没有,失败了就报错
  4. 【web】web欢迎页面执行servlet
  5. FKCL-OS&mdash;&mdash;自主的操作系统
  6. web安全之SQL注入
  7. 微信小程序 Request faild 请求后台失败
  8. DWR第二篇之逆向Ajax
  9. weblogic/tomcat Get乱码【转】
  10. 各种梯度下降 bgd sgd mbgd adam
  11. Jmeter分离登录事务的另一种方式
  12. Android软件开发之盘点全部Dialog对话框大合集(一)
  13. (object) array
  14. Android APP 分享图片文字到微信刚開始正常,后面就不弹出分享框了
  15. Beta阶段第三次网络会议
  16. Android系统移植与调试之------->如何修改Android手机NFC模块,使黑屏时候能够使用NFC
  17. 字符编码:WideCharToMultiByte
  18. C#.net制作验证码(英文与数字组成的4位随机数),以及MD5值的使用
  19. iOS 总结网页常用的东西
  20. 百亿级企业级 RPC 框架开源了!

热门文章

  1. spring AOP应用
  2. link2001错误无法解析外部符号metaObject
  3. PHP, LDAPS and Apache
  4. php CLI 模式下的传参方法
  5. (转)将win7电脑无线网变身WiFi热点,让手机、笔记本共享上网
  6. samba server install
  7. Tableau:数据可视化之急速BI
  8. Java多线程20:多线程下的其他组件之CountDownLatch、Semaphore、Exchanger
  9. WPF,Silverlight与XAML读书笔记第四十八 - Silverlight网络与通讯
  10. TDD(测试驱动开发)培训录