别样的碰碰车大战

太典了

不是我说，这几乎就是树型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

CPP

#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();}

注意：

开long long
由于可以不选，因此DP时要与0取最大值

别样的碰碰车大战题解

文章操作

别样的碰碰车大战

20pts

100pts

Code

注意：

相关推荐

评论

别样的碰碰车大战题解