【bzoj5174】[Jsoi2013]哈利波特与死亡圣器二分+树形dp

淩亂°似流年 2021-10-01 03:42 244阅读 0赞

[题目描述][Link 1]

给你一棵以1为根的有根树，初始除了1号点为黑色外其余点均为白色。Bob初始在1号点。每次Alice将其中至多k个点染黑，然后Bob移动到任意一个相邻节点，重复这个过程。求最小的k，使得无论Bob怎样移动，经过的节点都是黑色节点。

输入

第一行，包含1个整数，n，表示建筑的数量。

接下来n-1行，每行两个整数u、v（1≤u,v≤n，u≠v），表示建筑u和建筑v之间有一条魔法道路。

数据保证任意两个建筑连通。

1≤n≤300000。

输出

输出一个整数k，表示最少需要派出施用咒语的成员数。

样例输入

7  
1 2  
1 3  
2 5  
2 6  
7 2  
4 1

样例输出

--------------------

题解

二分+树形dp

建议大家读读原题面 = =

读懂题后可以发现：

Bob（伏地魔）的移动路线一定是从根节点到一个叶子节点的一条路径，因为走回头路实在是太傻逼了...   
Alice（凤凰社）只需要每次将每次移动的叶子节点染黑即可，每次一定是优先染叶子节点（因为下一步就要走到），多余的补后面的部分。

答案显然具有单调性，考虑二分答案。

对于二分的 $k=mid$ ，使用树形dp判定：

设 $f\[x\]$ 表示Bob走到了 $x$ 节点，仅有 $x$ 染黑，需要额外染多少个黑点才能够完成（也就是说之前需要多出多少个剩余操作次数才能够满足条件）。

那么对于 $x$ ，显然 $f\[x\]=\\text\{max\}(\\sum\\limits\_\{fa\[y\]=x\}f\[y\]+son\[x\]-mid,0)$ （$son\[x\]$ 表示 $x$ 的儿子个数），因为子节点需要染黑，每个儿子都需要补全（否则Bob可以选择该儿子）。而这一个点多余的的不能补给路径上之前的点，因此和 $0$ 取 $\\text\{max\}$ 。

如果 $f\[1\]=0$ ，说明不需要额外补充节点，$mid$ 可行；否则 $mid$ 不可行。

时间复杂度 $O(n\\log n)$ 。

#include <cstdio>
    #include <algorithm>
    #define N 300010
    using namespace std;
    int head[N] , to[N << 1] , next[N << 1] , cnt , son[N] , f[N] , mid;
    inline void add(int x , int y)
    {
    	to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;
    }
    void init(int x , int fa)
    {
    	int i;
    	for(i = head[x] ; i ; i = next[i])
    		if(to[i] != fa)
    			son[x] ++ , init(to[i] , x);
    }
    void dfs(int x , int fa)
    {
    	int i;
    	f[x] = son[x] - mid;
    	for(i = head[x] ; i ; i = next[i])
    		if(to[i] != fa)
    			dfs(to[i] , x) , f[x] += f[to[i]];
    	if(f[x] < 0) f[x] = 0;
    }
    int main()
    {
    	int n , i , x , y , l , r , ans;
    	scanf("%d" , &n);
    	for(i = 1 ; i < n ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x);
    	init(1 , 0);
    	l = 0 , r = n;
    	while(l <= r)
    	{
    		mid = (l + r) >> 1 , dfs(1 , 0);
    		if(f[1] == 0) ans = mid , r = mid - 1;
    		else l = mid + 1;
    	}
    	printf("%d\n" , ans);
    	return 0;
    }

转载于:https://www.cnblogs.com/GXZlegend/p/8484588.html

[Link 1]: http://www.lydsy.com/JudgeOnline/problem.php?id=5174