别样的碰碰车大战题解

· · 题解

别样的碰碰车大战

太典了

不是我说，这几乎就是树型DP板子题吧

20pts

枚举每一个点选/不选，再统计答案

时间复杂度 O(2^NN)

100pts

考虑树型DP

设 f[u][0/1] 表示以 u 为根的子树中， u 不选/选的最大边权和

很明显：如果不选 u ，那么连接 u 和其子结点的边就不会被选中。因此最大值为：

\sum_{v\in son_u}\max(f[v][0],f[v][1])

如果选 u ，那么当其子节点也被选中时，就会获得该边边权，因此最大值为:

\sum_{v\in son_u}\max(f[v][0],f[v][1]+w)

其中 w 为连接 u 和 v 的边的边权

Code

#include<bits/stdc++.h>
namespace Kards{
    using namespace std;
    typedef long long ll;
    ll n,f[100005][2];
    vector<pair<ll,ll> >a[100005];
    void dfs(ll x,ll fa){
        for(auto [v,w]:a[x]){
            if(v==fa)continue;
            dfs(v,x);
            f[x][0]+=max(f[v][0],max(f[v][1],0ll));
            f[x][1]+=max(f[v][0],max(f[v][1]+w,0ll));
        }
    }
    int main(){
        ios::sync_with_stdio(0);
        cin.tie(nullptr);
        cout.tie(nullptr);
        cin>>n;
        for(int i=1,u,v,w;i<n;i++){
            cin>>u>>v>>w;
            a[u].emplace_back(v,w);
            a[v].emplace_back(u,w);
        }
        dfs(1,0);
        cout<<max(f[1][0],f[1][1]);
        return 0;
    }
}
int main(){return Kards::main();}

注意：