「HNMTC2015_#3」Lmc的游戏 - 博弈论+烧脑贪心

题目大意

lmc在玩一个游戏。现在这里有一个有n个结点的有根树，其中有m个叶子结点。这m个叶子从1到m分别被给予了一个号码，每个叶子的号码都是独一无二的。一开始根节点有一个棋子，两个玩家每次行动将棋子移动到当前节点的一个儿子节点。当棋子被移动到某个叶节点的时候游戏结束，这个叶节点的号码即为该局游戏的result。先手的玩家要最大化result，后手的玩家要最小化这个result。
在两个玩家都无限聪明的情况下，在树的形态已知的情况下，在叶子的编号可以任意安排的情况下，游戏的result最大最小是多少。

题目分析

与其说是博弈论，不如说这是对抗搜索。
题目给的树实际上是对抗搜索中的搜索树。

先考虑答案最大值。
先手要最大化答案，后手要最小化答案。
设$Max[x]表示当前状态$x$可以达到的最大值在$x$子树中的排名,Min[x]$表示当前状态$x$可以达到的最小值在$x$子树中的排名。

先手一定选择后继状态中可以到达的最小值最大的状态移动。
后手类似，选择后继状态中可以到达的最大值最小的状态移动。
由于开始的编号不确定，因此代码实现中使用的是取$\min$，与定义的意义稍有不同。
这样我们就可以求出先手的$Max$与后手的$Min$。

若要答案最小化，先手和后手的移动策略是没有变化的。
直接给出结论，先手会往编号排名为$\sum_y Min[y]$（记为$a+b+c$）所在位置移动，后手类似。
尝试证明这个结论。

首先证明不能取到$\sum_y Min[y]-1$。
若往$\sum_y Min[y]-1$方向移动，说明$\sum_y Min[y]-1$一定是当前子树的最坏情况的最大值，排名就是某个$Min[y]$（记为$a$）。
若排名为$\sum_y Min[y]$与$\sum_y Min[y]-1$在同一棵子树中，说明当前子树有了$a+1$个元素，那么其余子树必定少了一个元素，故使用比$\sum_y Min[y]$更大的元素填充，这样从一开始的时候就不会选择这个子树而会选择有更大元素的方向移动了，与假设矛盾。
若$\sum_y Min[y]$不与$\sum_y Min[y]-1$在同一棵子树中，同样均可以取到最坏情况的最大值，那么一定不会往$\sum_y Min[y]-1$方向移动。
接着证明可以取到$sum_y Min[y]$。
因为$sum_y Min[y]$一定是某个$Min[y]$，即最坏情况的最大值，故显然能够取到。

证毕，但好像讲得不太清楚。

代码

#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
	while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
	return num*bj;
}

const int maxn=200005;

vector<int> edges[maxn];
int n,Min[maxn],Max[maxn],sum=0;

void Dfs(int Now,int depth) {
	if(!edges[Now].size()) {sum++;Max[Now]=Min[Now]=1;return;}
	for(int Next:edges[Now])Dfs(Next,depth^1);
	if(!depth) { //先手
		Max[Now]=n;
		for(int Next:edges[Now]) {
			Max[Now]=min(Max[Now],Max[Next]);
			Min[Now]+=Min[Next];
		}
	} else {
		Min[Now]=n;
		for(int Next:edges[Now]) {
			Min[Now]=min(Min[Now],Min[Next]);
			Max[Now]+=Max[Next];
		}
	}
}

int main() {
	n=Get_Int();
	for(int i=1; i<n; i++) {
		int x=Get_Int(),y=Get_Int();
		edges[x].push_back(y);
	}
	Dfs(1,0);
	printf("%d %d\n",sum-Max[1]+1,Min[1]);
	return 0;
}