【BZOJ 4169】 4169: Lmc的游戏 (树形DP)
1#include
2#include 3#include 4#include 5#include 6usingnamespace std;
7#defineINF 0xfffffff 8#defineMaxn 200010 910intmymax(intx,inty) {returnx>y?x:y;}
11intmymin(intx,inty) {returnxx:y;}
1213int mx[Maxn],mn[Maxn];
1415struct node
16{
17int x,y,next;
18}t[Maxn];
19int first[Maxn],len;
20voidins(intx,int y)
21{
22t[++len].x=x;t[len].y=y;
23t[len].next=first[x];first[x]=len;
24}
2526int sm[Maxn];
27voiddfs(intx,int dep)
28{
29sm[x]=0;
30if(first[x]==0)
31 {
32sm[x]=1;
33mn[x]=mx[x]=1;return;
34 }
35for(inti=first[x];i;i=t[i].next)
36 {
37inty=t[i].y;
38dfs(y,dep^1);
39sm[x]+=sm[y];
40 }
41mx[x]=0;mn[x]=0;
42if(dep) mx[x]=1,mn[x]=INF;
43for(inti=first[x];i;i=t[i].next)
44 {
45inty=t[i].y;
46if(!dep)
47 {
48mx[x]=mymax(mx[x],sm[x]-(sm[y]-mx[y]));
49mn[x]+=mn[y];
50 }
51else52 {
53mx[x]+=mx[y]-1;
54mn[x]=mymin(mn[x],mn[y]);
55 }
56 }
57}
5859int main()
60{
61int n;
62scanf("%d",&n);
63intrt=0;
64for(inti=1;i<=n;i++) rt+=i;
65len=0;
66memset(first,0,sizeof(first));
67for(inti=1;i)
68 {
69int x,y;
70scanf("%d%d",&x,&y);
71 ins(x,y);
72rt-=y;
73 }
74dfs(rt,0);
75printf("%d %d\n",mx[rt],mn[rt]);
76return0;
77}
来源: http://www.bubuko.com/infodetail-2019207.html