D

• 树上dp,dp[i]表示i号点染或者不染的最大权值。
• u点如果不选的话，其权值等于所有儿子选或不选的最大值。
• u点如果选的话，其权值等于选择一条边+其他儿子选或不选的最大值
• 其他儿子选不选就是dp[u][0]-选的那条边选或不选的最大值。

代码如下

#include"bits/stdc++.h"
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define rpe(i,a,n) for(int i=a;i>=n;i--)
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
#define int long long

const int N=1e5+9;//数组大小由情况来改变
struct edge{
    int to;
    int w;
};
vector<edge> e[N];
ll ans=0;
ll dp[N][2];
void dfs(int u,int fa){
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i].to;
        if(v==fa)continue;
        dfs(v,u);
        dp[u][0]+=max(dp[v][1],dp[v][0]);
    }
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i].to;
        if(v==fa)continue;
        dp[u][1]=max(dp[u][1],e[u][i].w+dp[u][0] - max(dp[v][1],dp[v][0]) +dp[v][0]);
    }
}
void slove(){
    int n;
    cin>>n;
    rep(i,1,n-1){
        int a,b,c;
        cin>>a>>b>>c;
        e[a].push_back({b,c});
        e[b].push_back({a,c});
    }
    dfs(1,0);
    cout<<max(dp[1][0],dp[1][1]);
}

signed main(){
    js;
    int t=1;
    //cin>>t;
    while(t--)slove();
}

第一篇博客