[백준] 17831 대기업 승범이네

문제

㈜승범이네는 사장 승범이를 포함한 N명의 직원이 모두 판매원인 다단계 회사이다. 사장 승범이를 제외한 모든 판매원에게는 사수가 한 명씩 배정된다. 만약 판매원 A가 B의 사수라면, B를 A의 부사수라고 부른다.

작년에 창설된 ㈜승범이네는 큰 수익률을 기록하고 대기업으로 거듭났다. ㈜승범이네의 더 큰 성장을 위해 멘토링 제도를 도입하려고 한다. 승범이는 사수와 부사수 관계에 있는 두 판매원을 각각 서로의 멘토와 멘티로 만들 수 있으며, 이 경우 두 판매원이 멘토링 관계에 있다고 한다. 한 판매원은 최대 1개의 멘토링 관계에만 속할 수 있다. 즉, 한 판매원이 여러 명의 멘토가 되거나, 여러 명의 멘티가 되거나, 멘토인 동시에 멘티가 될 수는 없다. 물론 멘토링 관계에 속하지 않는 직원이 있을 수도 있다.

이렇게 만들어진 멘토링 관계에서는 시너지 효과가 발생한다. 승범이는 모든 판매원의 실력을 수치화시켰으며, 한 멘토링 관계에서 발생하는 시너지는 멘토와 멘티의 실력의 곱과 같다는 것을 발견했다. 승범이는 적절하게 멘토링 관계를 만들어, 모든 멘토링 관계에서 발생하는 시너지의 합을 최대로 만들려고 한다.

  

위 그림은 ㈜승범이네의 회사 구조와 멘토링 관계를 나타낸 예시이다. 각 원은 한 명의 판매원을 의미하며, 원 안에 쓰인 숫자는 그 판매원의 실력이다. 화살표는 사수-부사수 관계를 나타낸다. 이 경우 가능한 시너지의 최대 합은 5×7 + 4×3 + 3×3 + 4×5 + 3×1 = 79이다.

입력

첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다.

두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대로 공백으로 구분되어 주어진다. 

세 번째 줄에 i번 판매원의 실력을 나타내는 정수 A1, A2, …, AN (0 ≤ Ai ≤ 100)이 순서대로 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 모든 멘토링 관계에서 발생하는 시너지의 합의 최댓값을 출력한다. 만약 멘토링 관계가 하나도 성립될 수 없을 경우, 0을 출력한다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int N, c[200001], dp[200001][2];
vi p[200001];
void dfs(int k) {
	if (p[k].size() == 0)return;

	for (int r : p[k]) {
		dfs(r);
	}
	int idx = 0, t = 0;
	vi temp;
	for (int r : p[k]) {
		temp.push_back(c[k] * c[r] + dp[r][0] - max(dp[r][0], dp[r][1]));
		dp[k][0] += max(dp[r][0], dp[r][1]);
	}
	idx = max_element(temp.begin(),temp.end()) - temp.begin();
	for (int r : p[k]) {
		t += max(dp[r][0], dp[r][1]);
	}
	dp[k][1] = temp[idx] + t;
	return;
}
int main() {
	FAST;
	cin >> N;
	int x;
	for (int i = 2; i <= N; i++) {
		cin >> x;
		p[x].push_back(i);
	}
	REP(i, N)cin >> c[i];
	dfs(1);
	cout << max(dp[1][0], dp[1][1]);
}

2차원 배열의 DP입니다.

dp[n][0] : n번째 직원이 멘토가 아닌경우

dp[n][1] : n번째 직원이 멘토인 경우

 

n번째 직원이 멘토가 아닌경우, dp[n][0]은 멘티 c에 한해 max(dp[c][0],dp[c][1])를 모두 더해주면 됩니다.

n번째 직원이 멘토인 dp[n][1]은 어떤 멘티c와 멘토멘티인 관계에서 최대여야합니다. 나머지는  max(dp[c][0],dp[c][1])를 모두 더해주면 됩니다.