专栏文章

题解：P4572 [JSOI2013] 哈利波特与死亡圣器

aabc1856896
P4572题解参与者 7已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@mip4jzfe
此快照首次捕获于
2025/12/03 06:03
3 个月前
此快照最后确认于
2025/12/03 06:03
3 个月前
查看原文

Solution

第一眼看上去答案应该是所有同一深度节点个数的最大值。但这样是错的。因为同一层的点不一定要一次染完，可以借助上一层多出来的去染颜色。
例如：
此时答案应该是 22，第一次染 22 和 33，第二次染 44 和 55，最后一次染 66 和 77。因为前几个节点同一深度只有一个节点，所以可以把下面的也染了。
此时我们注意到这种做法的问题在于不单单看同一深度的情况，也可以借助祖先。不妨定义 dpudp_u 表示 uu 节点要祖先帮他染多少次，则 dpu=max⁡(∑u⊂son⁡u(dpv+1)−m,0)dp_u= \max(\sum _ {u \sub \operatorname {son}_u} (dp_{v}+1)-m,0)，含义为子儿子需求量之和，mm 表示一次染的节点个数。如果该情况合法，即不用找 11 的祖先帮忙，则 dp1dp_1 为 00。
此时问题转化为最小的 mm 使得 dp1dp_1 为 00，注意到答案有单调性，二分即可。

Code

CPP
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define debug(x) cout<<x<<" "
#define debug2(x) cout<<x<<endl
#define mem(a,x) memset(a,x,sizeof(a))
#define endl '\n'
#define ll long long
#define Min(a,b) a=a<b?a:b
#define Max(a,b) a=a>b?a:b
#define Add(a,b) a=(a+b)%mod
#define Minus(a,b) a=((a-b)%mod+mod)%mod
#define Mul(a,b) a=a*b%mod
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a)/gcd(a,b)*(b)
#define vi vector<int>
#define pi pair<int,int>
#define pb push_back
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
using namespace std;
int head[600005],Gcnt;
struct data{
	int to;
	int next;
};
data edge[600005];
void add_edge(int from,int to){
	Gcnt++;
	edge[Gcnt].to=to;
	edge[Gcnt].next=head[from];
	head[from]=Gcnt;
}
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int dp[300005];
void dfs(int u,int fa,int k) {
	int sum=0;
	for(int i=head[u];i;i=edge[i].next) {
		int v=edge[i].to;
		if(v==fa) continue;
		dfs(v,u,k);
		sum+=dp[v]+1;
	}
	dp[u]=max((long long)(0),sum-k);
}
bool check(int mid) {
	memset(dp,0,sizeof(dp));
	dfs(1,0,mid);
	return !dp[1];
}
void solve() {
	int n=read();
	for(int i=1;i<n;i++) {
		int u=read(),v=read();
		add_edge(u,v),add_edge(v,u);
	}	
    if(!n || n==1) {
        cout<<0;
        return;
    }
	int l=0,r=n+1;
	while(l+1<r) {
		int mid=l+r>>1;
		if(check(mid)) r=mid;
		else l=mid;
	}
	cout<<r;
}
signed main(){
	int T=1;
	//cin>>T;
	while(T--) solve(); 
	return 0;
}

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...