生活随笔
收集整理的這篇文章主要介紹了
Party at Hali-Bula UVA - 1220（树形dp）
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
題目鏈接：傳送門
思路：求最多參與人數(shù)是樹形dp的入門題，和沒有上司的舞會是一個題目，但是這個題目還要求答案是否唯一。我們開設一個標記數(shù)組vis，標記就可以了。具體解釋看代碼：
#include<bits/stdc++.h>
#define ll long long
using namespace std
;const int maxx
=2e2+100;
struct edge
{int next
,to
;
}e
[maxx
<<1];
int head
[maxx
<<1],dp
[maxx
][2],vis
[maxx
][2];
map
<string
,int> mp
;
string s1
,s2
;
int n
,tot
;inline void init()
{memset(head
,-1,sizeof(head
));memset(dp
,0,sizeof(dp
));memset(vis
,0,sizeof(vis
));mp
.clear();tot
=0;
}
inline void add(int u
,int v
)
{e
[tot
].next
=head
[u
],e
[tot
].to
=v
,head
[u
]=tot
++;
}
inline void dfs(int u
,int f
)
{dp
[u
][0]=0;dp
[u
][1]=1;vis
[u
][0]=vis
[u
][1]=0;for(int i
=head
[u
];i
!=-1;i
=e
[i
].next
){int to
=e
[i
].to
;if(to
==f
) continue;dfs(to
,u
);dp
[u
][0]+=max(dp
[to
][1],dp
[to
][0]);dp
[u
][1]+=dp
[to
][0];if(vis
[to
][0]) vis
[u
][1]=1;if(dp
[to
][0]==dp
[to
][1]) vis
[u
][0]=1;if(dp
[to
][0]>dp
[to
][1]&&vis
[to
][0]) vis
[u
][0]=1;if(dp
[to
][0]<dp
[to
][1]&&vis
[to
][1]) vis
[u
][0]=1;}
}
int main()
{while(scanf("%d",&n
),n
){init();cin
>>s1
;mp
[s1
]=1;int cnt
=1;for(int i
=1;i
<n
;i
++){cin
>>s1
>>s2
;if(mp
[s1
]==0) mp
[s1
]=++cnt
;if(mp
[s2
]==0) mp
[s2
]=++cnt
;add(mp
[s1
],mp
[s2
]);add(mp
[s2
],mp
[s1
]);}dfs(1,0);printf("%d ",max(dp
[1][0],dp
[1][1]));if(dp
[1][0]==dp
[1][1]) printf("%s\n","No");else if((dp
[1][0]>dp
[1][1]&&vis
[1][0])||(dp
[1][0]<dp
[1][1]&&vis
[1][1])) printf("%s\n","No");else printf("%s\n","Yes");}return 0;
}
努力加油a啊，(o)/~
總結(jié)
以上是生活随笔為你收集整理的Party at Hali-Bula UVA - 1220（树形dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
