[백준/BOJ] 백준 21759번 : 두 개의 팀

https://www.acmicpc.net/problem/21759

21759번: 두 개의 팀

 

트리에 대해서

max_team에 "[정점] = 해당 정점이 팀장인 팀의 점수"를 저장하고 이를 이용해서,

max_sub에 "[정점] = 해당 정점이 루트인 서브트리에 속한 팀 중 점수의 최댓값"을 저장하고 이를 이용해서,

max_out_team에 "[정점] = 해당 정점이 루트인 서브트리에서 해당 정점이 팀장인 팀에 속한 정점들(max_team[정점]값을 만드는데 포함되는 정점들)을 제외한 정점으로 구성될 수 있는 팀 중 팀 점수의 최댓값"을 저장했다.

 

저장한 값들을 이용해 루트 노드부터 here 노드로 지정해 나아가면서 확인하며 "here을 팀장으로 팀을 구성하는 값 + here을 루트로 한 서브트리에서 here을 팀장으로 팀을 구성하는 정점들을 제외한 정점들로 만들 수 있는 팀 점수의 최댓값"과 "자식노드 max_sub 값 중 가장 큰 값 + 자식노드 max_sub 값 중 두 번째로 큰 값"을 비교하여 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;

int n;
vector<long long> score(200005, 0);
vector<int> adj[200005];
vector<long long> max_team(200005, 0); //[정점] = 해당 정점이 팀장인 팀의 점수
vector<long long> max_sub(200005, 0); //[정점] = 해당 정점이 루트인 서브트리에 속한 팀 중 점수의 최댓값
vector<long long> max_out_team(200005, numeric_limits<long long>::min()); //[정점] = 해당 정점이 루트인 서브트리에서 해당 정점이 팀장인 팀에 속한 정점들(max_team[정점]값을 만드는데 포함되는 정점들)을 제외한 정점로 구성될 수 있는 팀 중 팀 점수의 최댓값
long long result = numeric_limits<long long>::min();

//here가 팀장인 팀의 최대 점수 구하기
long long MakeMaxTeam(int here) {
	long long& ret = max_team[here];
	ret += score[here];

	for (int i = 0; i < adj[here].size(); i++) {
		int there = adj[here][i];
		ret += max((long long)0, MakeMaxTeam(there)); //there 노드 쪽을 팀원으로 고르는게 이득일때만 더한다
	}

	return ret;
}

//here가 루트인 서브트리에 속한 팀 중 점수의 최대값
long long MakeMaxSub(int here) {
	long long& ret = max_sub[here];
	ret = max_team[here];

	for (int i = 0; i < adj[here].size(); i++) {
		int there = adj[here][i];
		ret = max(ret, MakeMaxSub(there));
	}

	return ret;
}

long long MakeMaxOutTeam(int here) {
	long long& ret = max_out_team[here];

	for (int i = 0; i < adj[here].size(); i++) {
		int there = adj[here][i];
		long long there_max_out_team = MakeMaxOutTeam(there);

		if (max_team[there] <= 0) { //max_team[here]을 만드는데 there쪽을 쓰지 않는 경우일때
			ret = max(ret, max_sub[there]); //there을 루트로 하는 서브트리에 속하는 팀 중 팀 점수 최댓값을 가져온다 (there쪽을 max_team[here]을 만드는데 사용하지 않았으므로 자유롭게 사용 가능)
		}

		else { //max_team[here]을 만드는데 there쪽을 쓰는 경우 일때
			ret = max(ret, there_max_out_team); //max_team[there]을 만드는데 안쓰는 정점들로 이루어진 최댓값을 가져온다 
		}
	}

	return ret;
}

void Solve(long long here) {

	//here을 팀장으로 팀을 구성하는 값 + here을 루트로 한 서브트리에서 here을 팀장으로 팀을 구성하는 정점들을 제외한 정점들로 만들 수 있는 팀 점수의 최댓값
	if (max_out_team[here] != numeric_limits<long long>::min()) { //here을 루트로 한 서브트리에서 here을 팀장으로 팀을 구성하는 정점들을 제외한 정점들로 만들 수 있는 팀이 있을 때
		result = max(result, max_team[here] + max_out_team[here]);
	}

	long long here_max_sub1 = numeric_limits<long long>::min(); //자식노드 max_sub 값 중 가장 큰 값
	long long here_max_sub2 = numeric_limits<long long>::min(); //자식노드 max_sub 값 중 두번째로 큰 값
	for (int i = 0; i < adj[here].size(); i++) {
		int there = adj[here][i];
		Solve(there);

		if (here_max_sub1 < max_sub[there]) {
			here_max_sub2 = here_max_sub1;
			here_max_sub1 = max_sub[there];
		}

		else if (here_max_sub2 < max_sub[there]) {
			here_max_sub2 = max_sub[there];
		}
	}

	if (here_max_sub1 != numeric_limits<long long>::min() && here_max_sub2 != numeric_limits<long long>::min()) {
		result = max(result, here_max_sub1 + here_max_sub2);
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 1; i <= n; i++) {
		long long this_score;
		int this_parent;
		int here = i;

		cin >> this_score >> this_parent;

		score[here] = this_score;

		if (this_parent == -1) {
			continue;
		}

		adj[this_parent].push_back(here);
	}

	MakeMaxTeam(1);
	MakeMaxSub(1);
	MakeMaxOutTeam(1);
	Solve(1);

	cout << result;

	return 0;
}