CF1997D Maximize the Root_开发测试

CF1997D Maximize the Root

创始人

2024-11-13 20:41:01

0次

[Problem Discription] \color{blue}{\texttt{[Problem Discription]}} [Problem Discription]

在这里插入图片描述

感谢伟大的洛谷。

[Solution] \color{blue}{\texttt{[Solution]}} [Solution]

显然，这题直接求解非常麻烦。

考虑一些技巧，我们发现答案是有单调性的：如果存在一种方法能使 a 1 a_{1} a1 变成 u u u，那么对于任意的 a 1 ≤ v < u a_{1} \leq v 方案能使 a 1 a_{1} a1 变成 v v v。

有单调性就有可二分性，于是我们考虑使用二分答案的方法把这道题从求解性问题变成判断性问题。

一个经验的事实是：判断性问题的难度一般比同性质的求解性问题小。

现在让我们思考给定一个 k k k，如何判定这个 k k k 是否可行。

树上的问题，一般情况下首先就要考虑求解的方向：即从根到叶还是从叶到根。

显然从叶到根方法太多，不便于考虑。所以我们从根到叶考虑。

要想把 a 1 a_{1} a1 变成 k k k，就需要对 1 1 1 的每一棵子树进行 ( k − a 1 ) (k-a_{1}) (k−a1) 次操作。

现在考虑 1 1 1 的子树 u u u：

如果 a u ≥ k − a 1 a_{u} \geq k-a_{1} au≥k−a1，那么对于 u u u 的每一棵子树 v v v，只需要进行 ( k − a 1 ) (k-a_{1}) (k−a1) 次操作（这不是对 u u u 在操作导致的，而是对 1 1 1 操作导致的）。
如果 a u < k − a 1 a_{u}

接下来的过程具有重复性，dfs 即可。

[code] \color{blue}{\text{[code]}} [code]

bool dfs(int u,int Fa,ll k){ 	if (k>1e17) return false; 	 	bool ret=true,lef=true; 	 	for(int i=h[u];i;i=e[i].nxt){ 		int v=e[i].to; 		if (v==Fa) continue; 		 		lef=false; 		if (a[v]>=k) ret&=dfs(v,u,k); 		else ret&=dfs(v,u,k+(k-a[v])); 	} 	 	if (lef) return a[u]>=k; 	else return ret; }  bool check(ll mid){ 	return dfs(1,0,mid-a[1]); }  void initdata(){ 	for(int i=1;i<=(n<<1);i++) 		e[i]=(edge){0,0}; 	for(int i=1;i<=n+1;i++) 		a[i]=h[i]=0; 	ecnt=0;l=r=0; }  int main(){ 	T=read(); 	while (T--){ 		n=read(); 		 		initdata(); 		 		for(int i=1;i<=n;i++) 			a[i]=read(); 		for(int i=2;i<=n;i++) 			add(read(),i); 		 		l=ans=a[1];r=1e11; 		 		while (l<=r){ 			ll mid=(l+r)>>1; 			if (check(mid)){ 				l=mid+1; 				ans=mid; 			} 			else r=mid-1; 		} 		 		printf("%lld\n",ans); 	} 	 	return 0; }  read() 是快读，e 和 h 是链式前向星建的图 由于比较简单，代码就不给了

上一篇：前端面试：项目细节重难点问题分享（十五）

下一篇：不同类型游戏安全风险对抗概览（下）| FPS以及小游戏等外挂问题，一文读懂！

CF1997D Maximize the Root

相关内容

热门资讯