【树形DP】ABC259 F - Select Edges

旧城等待， 2024-03-17 11:21 11阅读 0赞

**wc了，这道题用前向星一直过不了样例，用邻接表就能过，调了整整一个小时**

**然后才发现建图建错了....**

**好s b啊**

[F - Select Edges (atcoder.jp)][F - Select Edges _atcoder.jp]

题意：

![e75ab3833a33489f94d3b9ed5710129c.png][]

![0931a40662c64fb18276136860616c59.png][]

思路：

如果状态设成dp\[u\]\[j\]表示以u为根的子树，子树中选j条边的最大权值和 的话，会爆空间，因此树上背包是不可以的

注意到每条边都有选和不选两种决策，因此可以把决策放在状态里面

边的状态可以转化到点里

![12f3c9947eb947c7ab59f0e8425ccaa9.png][]

这里的贪心也有点难想到

因为儿子的顺序是无关紧要的，因此可以将儿子按贡献大小排序选，把最大权值和作为dp\[u\]\[1\]的状态

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=3e5+10;
    const int mxe=3e5+10;
    const int Inf=1e18;
    
    vector<pair<int,int> > G[mxn];
    
    struct ty{
        int to,next,w;
    }edge[mxe<<2];
    
    int N,u,v,w,tot=0;
    int d[mxn],dp[mxn][4];
    int head[mxn],vis[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){
    	for(int i=head[u];~i;i=edge[i].next){
    		if(edge[i].to==fa) continue;
    		dfs(edge[i].to,u);
    	}
        vector<int> V;
        int res=0;
        for(int i=head[u];~i;i=edge[i].next){
            if(edge[i].to==fa) continue;
            res+=dp[edge[i].to][0];
            V.push_back(dp[edge[i].to][1]+edge[i].w-dp[edge[i].to][0]);
        }
        sort(V.begin(),V.end());
        reverse(V.begin(),V.end());
        if(d[u]==0){
            dp[u][0]=res;
            dp[u][1]=-Inf;
        }else{
            dp[u][0]=dp[u][1]=res;
            for(int i=0;i<V.size();i++){
                if(V[i]<0ll) break;
                if(i<d[u]) dp[u][0]+=V[i];
                if(i<d[u]-1) dp[u][1]+=V[i];
            }
        }
    }
    void solve(){
        cin>>N;
        G_init();
        for(int i=1;i<=N;i++) cin>>d[i];
        for(int i=1;i<=N-1;i++){
            cin>>u>>v>>w;
    		add(u,v,w);
    		add(v,u,w);
        }
        dfs(1,0);
        cout<<max(dp[1][0],dp[1][1])<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[F - Select Edges _atcoder.jp]: https://atcoder.jp/contests/abc259/tasks/abc259_f
[e75ab3833a33489f94d3b9ed5710129c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/93e50d1f649c49d0b36a4d25a2a191b1.png
[0931a40662c64fb18276136860616c59.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/3980430f320e4d3cb2f6a7d5f261be69.png
[12f3c9947eb947c7ab59f0e8425ccaa9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/b49701ba336a463f9cefa8fb6aa3f54c.png