codeforces 1083 A. The Fair Nut and the Best Path(树形dp)
程序员文章站
2022-06-26 18:37:31
题目大意:每个节点都给定一个值a[i],从一个节点走到另一个节点会消耗固定值w,但也会得到这个节点的价值,问怎样走才能得到最大的价值。解题思路:这个题和树形dp求树的直径差不多(树形DP基本都是相通的),f[X] 代表以x点为根节点,到子树叶子点可以获得的最大权值Code:#include #include #include#include #include
题目大意:
每个节点都给定一个值a[i],从一个节点走到另一个节点会消耗固定值w,但也会得到这个节点的价值,问怎样走才能得到最大的价值。
解题思路:
这个题和树形dp求树的直径差不多(树形DP基本都是相通的),f[X] 代表以x点为根节点,到子树叶子点可以获得的最大权值
Code:
#include <iostream>
#include <cstdio>
#include<cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#define inf 9654234
#define ll long long
using namespace std;
const int maxn=300007;
vector<pair<ll,ll>> ve[maxn];
ll a[maxn],f[maxn],ans=0;
void dfs(int u,int fa){
f[u]=a[u];
ans=max(ans,f[u]); //到子树可能获得的值为负数,那么就不去了
for(auto v:ve[u]){
int x=v.first;
int y=v.second;
if(x==fa) continue;
dfs(x,u);
ans=max(ans,f[u]+f[x]-y); // f[x]-y 是到达子树可以获得的最大权值,f[u]是从另一条边过来可以获得的最大权值
f[u]=max(f[u],a[u]+f[x]-y); //更新f[u]的值
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>f[i];
for(int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
ve[u].push_back(make_pair(v,w));
ve[v].push_back(make_pair(u,w));
}
dfs(1,0);
cout<<ans<<"\n";
return 0;
}
本文地址:https://blog.csdn.net/weixin_43872264/article/details/107891173
上一篇: 一堆不靠谱的话,常听也常说