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

D e s c r i p t i o n \mathcal{Description} Description


S o l u t i o n \mathcal{Solution} Solution
根据题意,我们知道
根节点深度为1,深度为 奇数 的节点由 D a v i d David David移动,我们称为 D D D点,深度为 偶数 的节点由 V i n c e n t Vincent Vincent移动,我们称为 V V V
b i g [ i ] , s m a [ i ] big[i],sma[i] big[i],sma[i]表示 i i i节点以为根节点,由 i i i开始移动,最后到叶子节点时的数字由 D a v i d David David放数字 最大是第几大的数字 ,由 V i n c e n t Vincent Vincent放数字__最小是第几小的数字__
假如 i i i节点是 D D D
那么对于 i i i的儿子 v v v,有

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

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

  • b i g [ i ] + = b i g [ v ] big[i]+=big[v] big[i]+=big[v]
  • s m a [ i ] = m i n { s m a [ i ] , s m a [ v ] } sma[i]=min\{sma[i],sma[v]\} 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;
}

全部评论

相关推荐

就前几天旅游的时候,打开抖音就经常刷到这类视频:以前是高学历学生、老师、主持人,现在做着团播、擦边主播的工作,以及那些经过精心包装的“职业转型”故事——从铺天盖地的VLOG到所谓的“04年夜场工作日记”,这些内容在初中升学、高考放榜等关键时间节点持续发酵。可以说非常直接且精准地在潜移默化地影响着心智尚未成熟的青少年,使其对特殊行业逐渐脱敏。那我就想问了:某些传播公司、平台运营者甚至某些夜场的老板,你们究竟在传递怎样的价值观?点开那些视频,评论区里也是呈现明显的两极分化:一种是​​经济下行论​​:“现在就业市场已经艰难到这种程度了吗?”​​一种是事实反驳派​​:这些创作者往往拥有名校背景,从事着...
牛客刘北:被环境教育的,为了能拿到足够的钱养活自己,不甘心也得甘心,现在的短视频传播的思想的确很扭曲,但是很明显,互联网玩上一年你就能全款提A6,但你全心全意不吃不喝工作一年未必能提A6,但是在高考中考出现这个的确很扭曲,在向大家传播“不上学,玩互联网也可以轻松年入百万”,不是人变了,是社会在变
预测一下26届秋招形势
点赞 评论 收藏
分享
陈逸轩1205:才105 哥们在养生呢
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-03 18:13
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务