Codeforces - Chloe and pleasant prizes

9315 단어 Codeforces트리동적 기획
제목 링크: Codeforces - Chloe and pleasant prizes
두 개의 자수에는 반드시 하나의 공공 조상이 존재하므로 공공 조상을 일일이 열거하면 된다.
그리고 공조상의 아들 중에서 가장 큰 두 개의 나무를 골랐다.
AC 코드:
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include
#define int long long
using namespace std;
const int N=2e5+10;
int n,a[N],mx[N],sum[N],res=-1e18;
vector<int> g[N];
void dfs(int x,int fa){
	sum[x]=a[x]; int mx1=-1e18,mx2=-1e18;
	for(int to:g[x]) if(to!=fa){
		dfs(to,x); sum[x]+=sum[to];
		if(mx[to]>mx1) mx2=mx1,mx1=mx[to];
		else if(mx[to]>mx2) mx2=mx[to];
		mx[x]=max(mx[x],mx[to]);
	}
	mx[x]=max(mx[x],sum[x]);
	res=max(res,mx1+mx2);
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>a[i],mx[i]=-1e18;
	for(int i=1,a,b;i<n;i++) cin>>a>>b,g[a].push_back(b),g[b].push_back(a);
	dfs(1,0);
	if(res<-1e17)	return puts("Impossible"),0;
	cout<<res;
	return 0;
}
상용 알고리즘 정리: 동적 기획 중편
취미 알고리즘 - 친밀 수

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage