D. The Fair Nut and the Best Path

题意：给出一张图点有权值边也要权值从任意点出发到任意点结束到每个点的时候都可以获得每个点的权值，而从边走的时候都要消耗改边的边权，如果当前值小于边的边权，就走不通，问从任意点出发到任意点结束的可以获得的最大权多少（其中到一个点结束的时候也能获得改点的值）

思路：一个很明显的树上dp的问题 \(dp[i]\)表示以i为起点的可以获得的最高的权值是多少

\(dp[i]=w[i]+max(son(dp[j]))\) 其中j为i的儿子节点

表示的是以i为起点得到的最大权通过以其儿子位起点的最大权来更新

而答案等于 \(max(w[i]+firstmax+secondmax)\)表示以i的权值加以i为起点的路径的最大的两条可以获得的权值

#include<bits/stdc++.h>

#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)

#define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr))

#define F first

#define S second

#define pii pair<int ,int >

#define mkp make_pair

#define pb push_back

#define arr(zzz) array<ll,zzz>

using namespace std;

typedef long long ll;

#define int ll

const int maxn=3e5+5;

struct Node{

int to,next,value;

}edge[maxn*10];

int head[maxn],w[maxn];

int dp[maxn];

int size=0;

ll ans=0;

void add(int x,int y,int v){

	edge[size].to=y;

	edge[size].next=head[x];

	edge[size].value=v;

	head[x]=size++;

}

void dfs(int now,int fa){

	dp[now]+=w[now];

	//cout<<dp[now]<<" "<<now<<endl;

	ll firstmax=0,secondmax=0;

	for(int i=head[now];i!=-1;i=edge[i].next){

		int y=edge[i].to;

		int v=edge[i].value;

		if(y!=fa){

			dfs(y,now);

			if(dp[y]-v>=firstmax){

				secondmax=firstmax;

				firstmax=dp[y]-v;

			}

			else if(dp[y]-v>secondmax){

				secondmax=dp[y]-v;

			}

		}

		//cout<<dp[now]<<" "<<firstmax<<" "<<secondmax<<" "<<now<<" "<<endl;

		//dp[now]+=firstmax;

	}

		ans=max(ans,dp[now]+secondmax+firstmax);

	dp[now]+=firstmax;

	//cout<<dp[now]<<" "<<w[now]<<" "<<ans<<" "<<firstmax<<" "<<secondmax<<" "<<now<<endl;

}

int32_t main(){

	int n;

	memset(head,-1,sizeof(head));

	scanf("%lld",&n);

	for(int i=1;i<=n;i++){

		scanf("%lld",&w[i]);

	}

	int x,y,v;

	for(int i=1;i<n;i++)

	{

		scanf("%lld%lld%lld",&x,&y,&v);

		add(x,y,v);

		add(y,x,v);

	}

	dfs(1,-1);

	cout<<ans<<endl;

	return 0;

}

巴特西

Codeforces Round #526 (Div. 2) D. The Fair Nut and the Best Path 树上dp

D. The Fair Nut and the Best Path

最新文章

热门文章