[백준 16437] 양 구출 작전

DFS 재귀로 풀어주면 된다.
 
맨 밑 leaf node까지 재귀로 내려가준 다음에, 해당 노드부터 생존수를 계산하여 루트노드까지 올려보내면 된다
 

 
일단 조건을 보면 한 섬에는 양 또는 늑대가 삼.
즉 둘 중 하나임. 조건 상 뭐든 살아
 
그래서 양이면 num을 +값으로 놓고
늑대면 num을 음수로 놓으면 됨
부호가 양/늑대 구분하는 기준인거임
 
그리고 양이 다 죽으면 0이지 -200 이런 숫자는 말이 안되니까
sum<0 이면 sum = 0 으로 예외케이스 처리해주자
 
여기서도 visited는 bitset으로
bitset이 개꿀임
 

---

#include <iostream>
#include <stack>
#include <bitset>
#include <vector>

#define SIZE 123457

using namespace std;

// 노드가 S인지 W인지
// 노드 동물이 몇 개인지
// 무조건 뭐가 살긴함 -> 조건 상 이게 늑대든 양이든 뭐든 살아

int arr[SIZE];

vector<int> tree[SIZE];
bitset<SIZE> visited;

long long DFS(int v) {
	visited[v] = 1;
	long long sum = 0;

	for (auto it = tree[v].begin(); it != tree[v].end(); it++) {
		if (!visited[*it]) {
			visited[*it] = 1;
			sum += DFS(*it);
		}
	}

	sum += arr[v];
	
	if (sum < 0) sum = 0;

	return sum;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N; cin >> N;
	char ch;
	int num, to;

	for (int i = 2; i <= N;i++) {
		cin >> ch >> num >> to;
		arr[i] = num;
		if (ch == 'W') arr[i] *= -1;

		tree[to].push_back(i);
		tree[i].push_back(to);
	}
	cout << DFS(1);

	return 0;
}