BZOJ 4169 LＭC的游戏 （博弈+树dp）

发表于 |
字数统计: 849字 | 阅读时长 ≈ 4min

4169 LMC的游戏

【题目描述】

RHL 有一天看到 lmc 在玩一个游戏。
“愚蠢的人类哟,what are you doing”,RHL 说。
“我在玩一个游戏。现在这里有一个有 n 个结点的有根树,其中有 m 个叶子结点。这 m个叶子从 1 到 m 分别被给予了一个号码,每个叶子的号码都是独一无二的。一开始根节点有一个棋子,两个玩家每次行动将棋子移动到当前节点的一个儿子节点。当棋子被移动到某个叶节点的时候游戏结束,这个叶节点的号码即为该局游戏的 result。先手的玩家要最大化result,后手的玩家要最小化这个 result。”
“你不先问一下我是谁吗 = =”
“那么,who are you”
“我是这个世界的创造者,维护者和毁灭者,整个宇宙的主宰,无所不知,无所不能的,三个字母都大写的 RHL。”
“既然你这么厉害,那你一定知道,在两个玩家都无限聪明的情况下,在树的形态已知的情况下,在叶子的编号可以任意安排的情况下,游戏的 result 最大是多少咯。”

【输入格式】

输入数据第一行有一个正整数 n,表示结点的数量。
接下来 n-1 行,每行有两个正整数 u 和 v,表示的父亲节点是 u。

【输出格式】

输出一行 2 个非负整数,分别表示 result 的最大值和最小值。

【样例输入】

5
1 2
1 3
2 4
2 5

【样例输出】

3 2

【样例解释】

有 3,4,5 三个叶子。若令 3 号叶子的编号是 3,则先手可以移到 3 号结点,故 result
最大是 3。若 3 号叶子的编号是 2,则先手可以移到 3 号结点,故 result 最小是 2.

【数据范围】

30%,n<=10
100%,n<=200000

有意思的博弈题。只考虑最大值的情况，最小值是类似的。
令$F[i]$表示在$i$号点能取得子树中第$F[i]$大的叶子。
如果$i$号点是先手移动，那么$F[i]=min(F[son_i])$，这个转移是显然的。
如果$i$号点是后手移动，那么$F[i]=\sum F[son_i]$，这个转移是因为后手肯定会选择第$F[son_i]$大的值最小的子树移动，因此最后取得的一定是第$\sum F[son_i]$大的。

如果$i$号点是叶子，那么$F[i]=1$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 200005
using namespace std;
int n,m,dp[2][N],rt;
int TOT,LA[N],NE[N],EN[N];
bool mark[N],mmark[N];
void ADD(int x,int y)
{
	TOT++;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void DFS(int x,int ty)
{
	if(!mmark[x]){dp[0][x]=dp[1][x]=1;return;}
	dp[ty][x]=1e9;
	for(int i=LA[x];i;i=NE[i])
	{
		int  y=EN[i];DFS(y,ty^1);
		dp[ty][x]=min(dp[ty][x],dp[ty][y]);
		dp[ty^1][x]+=dp[ty^1][y];
	}
}
int main()
{
	int i,j,k,x,y;
	scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		mark[y]=1;
		mmark[x]=1;
		ADD(x,y);
	}
	for(i=1;i<=n;i++)if(!mark[i])rt=i;
	for(i=1;i<=n;i++)if(!mmark[i])m++;
	DFS(rt,0);
	printf("%d %d",m-dp[0][rt]+1,dp[1][rt]);
}