【二分+树形DP】吉吉王国

布满荆棘的人生 2024-03-22 17:37 77阅读 0赞

[吉吉王国 (nowcoder.com)][_nowcoder.com]

题意：

![7987f6f657d5460381662dce144d767a.png][]

![8190a8a5966741838ab8b904f997b3cd.png][]

思路：

因为要求的是最小的最大值，因此可以考虑二分删掉的边的最大值

然后考虑求在删掉不超过mid的边的情况下让叶子结点和根节点不连通的最小总权值

考虑树形DP

状态设计：

设dp\[u\]为以u为根节点的子树，在删掉不超过mid的边的情况下让叶子结点和根节点不连通的最小总权值

转移真的很巧妙，挺难想到的感觉

如果此边超过了mid，那么一定就不能选，直接dp\[u\]+=dp\[v\]

否则就是两种决策：选or不选，**如果选的话最小总权值就是此边权值w，**因为此边被删了，子树中其他边就没有必要删了，这样就是最小的总权值

dp数组的初始化就是在叶子结点，当u为叶子结点时，dp\[u\]=Inf

Code：

#include <bits/stdc++.h>
    
    #define int long long
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    
    using namespace std;
    
    const int mxn=3e6+10;
    const int mxe=3e5+10;
    const int mod=1e9+7;
    const int Inf=1e9;
    
    struct ty{
    	int to,next,w;
    }edge[mxe<<2];
    
    int N,M,tot=0,u,v,w,ans=Inf,w_min=1e9,w_max=0;
    int head[mxn],dp[mxn],d[mxn];
    
    void add(int u,int v,int w){
    	edge[tot].w=w;
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void G_init(){
    	tot=0;
    	for(int i=0;i<=N;i++){
    		head[i]=-1;
    	}
    }
    void dfs(int u,int fa,int q){
    	for(int i=head[u];~i;i=edge[i].next){
    		if(edge[i].to==fa) continue;
    		dfs(edge[i].to,u,q);
    		if(edge[i].w<=q) dp[u]+=min(edge[i].w,dp[edge[i].to]);
    		else dp[u]+=dp[edge[i].to];
    	}
    	if(d[u]==1&&u!=1) dp[u]=Inf;
    }
    bool check(int mid){
    	for(int i=0;i<=N;i++) dp[i]=0;
    	dfs(1,0,mid);
    	return dp[1]<=M;
    }
    void solve(){
    	cin>>N>>M;
    	G_init();
    	for(int i=1;i<=N-1;i++){
    		cin>>u>>v>>w;
    		add(u,v,w);
    		add(v,u,w);
    		d[u]++;
    		d[v]++;
    		w_max=max(w_max,w);
    		w_min=min(w_min,w);
    	}
    	int l=w_min,r=w_max;
    	while(l<=r){
    		int mid=l+r>>1;
    		if(check(mid)){
    			ans=mid;
    			r=mid-1;
    		}else l=mid+1;
    	}
    	if(ans==Inf) cout<<-1<<'\n';
    	else cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[_nowcoder.com]: https://ac.nowcoder.com/acm/problem/210473
[7987f6f657d5460381662dce144d767a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/9cae178006ae43a59fc586607e868086.png
[8190a8a5966741838ab8b904f997b3cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/0b182ca20a9d4c3387fac697145e4acd.png