David与Vincent的博弈游戏[树型DP]

$Description$Description

$Solution$Solution
根据题意，我们知道
根节点深度为1，深度为 奇数 的节点由 $David$David移动，我们称为 $D$D点，深度为 偶数 的节点由 $Vincent$Vincent移动，我们称为 $V$V点
记 $big\left[i\right],sma\left[i\right]$big[i],sma[i]表示 $i$i节点以为根节点，由 $i$i开始移动，最后到叶子节点时的数字由 $David$David放数字 最大是第几大的数字 ，由 $Vincent$Vincent放数字__最小是第几小的数字__
假如 $i$i节点是 $D$D点
那么对于 $i$i的儿子 $v$v,有

• $big\left[i\right]=min\left\{big\right[i],big[v\left]\right\}$big[i]=min{big[i],big[v]}
  因为 $David$David移动到叶子节点时尽量要最大的数字，显然往儿子节点移动时，往到叶子节点时能得到最大数的排名最高的儿子移动最好，由于是 $David$David放数字，所以 $David$David不会将最优的数字浪费在他不会移动到的点
• $sma\left[i\right]+=sma\left[v\right]$sma[i]+=sma[v]
  我们知道 $sma\left[v\right]$sma[v]，若由 $D$D向 $V$V移动，那么此时 $sma\left[i\right]$sma[i]就至少是 $sma\left[v\right]$sma[v]
  若 $D$D向另外的儿子 $V^{\prime }$V′移动，考虑为什么不往 $V$V移动：
  因为向 $V$V移动后 $Vincent$Vincent肯定会尽量使结果对其最优，所以 $Vincent$Vincent会把对他而言最优的数字放在那边，聪明的 $David$David发现后就不会往这边走了，那为什么要把最优数字放在 $V$V呢，同理， $David$David会发现往其他地方移动没有往 $V$V更优，就会往 $V$V移动了，而为什么 $Vincent$Vincent要让 $David$David只能往 $V^{\prime }$V′移动呢，因为如果 $Vincent$Vincent让 $David$David往 $V$V移动的话得到的最终结果对 $Vincent$Vincent就不是最优的了。这么说可能有点绕，但都是必然的因果关系，主要我们要在为 $David$David考虑时，还要换位思考 $Vincent$Vincent的想法，可以画个图想想。
  所以 $David$David会把最优的一些数字放在 $V$V之类的其他点，而这样 $Vincent$Vincent就会往 $V^{\prime }$V′走，所以就会浪费掉除 $sma\left[v^{\prime }\right]$sma[v′]以外个 $sma\left[v\right]$sma[v]个大数字，又此时往 $V^{\prime }$V′移动得到的最优数字是第 $big\left[v^{\prime }\right]$big[v′]，所以要加上所有儿子的 $sma$sma

假如 $i$i节点是 $V$V点
那么此时的情况和 $D$D点相反，因为他们的目的相反，所以
对于 $i$i的儿子 $v$v有

• $big\left[i\right]+=big\left[v\right]$big[i]+=big[v]
• $sma\left[i\right]=min\left\{sma\right[i],sma[v\left]\right\}$sma[i]=min{sma[i],sma[v]}

代码

/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年06月20日 星期四 15时27分03秒 *******************************/
#include <cstdio>
#include <fstream>
using namespace std;
const int maxn = 100005;
//{{{cin 快读
struct IO{
	template<typename T>
	IO & operator>>(T&res){
		res=0;
		bool flag=false;
		char ch;
		while((ch=getchar())>'9'||ch<'0')	 flag|=ch=='-';
		while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();
		if (flag)	 res=~res+1;
		return *this;
	}
}cin;
//}}}
int n,m,u,v,root,cnt;
int head[maxn],to[maxn],nxt[maxn];
int big[maxn],sma[maxn],fa[maxn],col[maxn];//col[i]=1 -> David
//{{{add
void add (int u,int v)
{
	nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v,fa[v]=u;
}
//}}}
void dfs (int x)
{
	col[x]=!col[fa[x]];
	if (!head[x]){
		++m;
		big[x]=sma[x]=1;
		return;
	}
	if (col[x])	big[x]=n+1;
	else	sma[x]=n+1;
	for (int e=head[x];e;e=nxt[e]){
		dfs(to[e]);
		if (col[x]){
			big[x]=min(big[x],big[to[e]]);
			sma[x]+=sma[to[e]];
		}
		else{
			big[x]+=big[to[e]];
			sma[x]=min(sma[x],sma[to[e]]);
		}
	}
}
int main()
{
	cin>>n;
	for (int i=1;i<=n-1;++i){
		cin>>u>>v;
		add(u,v);
	}
	for (int i=1;i<=n&&!root;++i)
		if (!fa[i])	root=i;
	dfs(root);
	printf("%d %d\n",m-big[root]+1,sma[root]);
	return 0;
}