cf 551 div2 D - Serval and Rooted Tree (tree, dp, 발상)

https://codeforces.com/contest/1153/problem/D

문제를 재정의하는 방법이 새로워서 리뷰

 

<문제설명>

루트가 1인 트리가 주어진다. 리프노드가 k개 있다면 각 리프노드에 1~k의 순열을 저장할 수 있다.

 

각 노드마다 min또는 max 성질이 주어지는데, 자식노드의 값중 최소 또는 최대를 값으로 갖는다는 의미다.

 

리프노드에 적절한 값을 넣어 루트에 저장될 수 있는 값 중 최대를 구하라.

 

<풀이>

현재 정점 u가 max 성질이 있다면, 그냥 자식 정점 값중 최대를 갖으면 된다.

 

문제가되는건 min성질이다.

 

예를들어서 min성질을 갖는 정점 u가 리프노드 3개를 자식으로 둔다면, 가장 작은 하나를 제외하고 2개의 숫자를 잃는다고 생각할 수 있다.(잘 생각해보면 u의 자식이 리프노드가 아니더라도 일반화 가능하다)

 

dp[u] : u를 루트로 하는 서브트르에서 가장 적은 리프노드를 버리는 경우의 수

(u~max) : min dp[v] (v in childernof(u))

(u~min) :

 

답은 numofLeaf - dp[1]

 

<코드>

int n, dp[MAX],leaf;
bool mxmn[MAX];
vector<int> g[MAX];

int dfs(int u) {
	if (g[u].empty()) return 0;
	int ret = mxmn[u] ? MAX : g[u].size()-1;
	for (int v : g[u]){
		if (mxmn[u]) ret = min(ret, dfs(v));
		else ret += dfs(v);
	}
	return ret;
}

int main() {
	FAST; cin >> n;
	for (int i = 1; i <= n; i++) cin >> mxmn[i];
	for (int i = 2, inp; i <= n; i++) {
		cin >> inp;
		g[inp].push_back(i);
	}
	for (int i = 2; i <= n; i++) if (g[i].size() == 0)	leaf++;
	
	cout << leaf - dfs(1) << '\n';
}