[백준 16437]양 구출 작전

문제 https://www.acmicpc.net/problem/16437

1)문제 분류

-트리

2)문제 해결

- 재귀로 후위순회 방법으로 구현한다.

#include <iostream>

#include<vector>

using namespace std;

int N;

vector<int>vt[123458];

typedef struct Data

{

char T;

long long int Cnt;

}Data;

Data arr[123458];

long long int dfs(int idx)

{

long long int sum = 0;

for (int i = 0; i < vt[idx].size(); i++)

{

sum += dfs(vt[idx][i]);

}

if (arr[idx].T == 'S')

return arr[idx].Cnt + sum;

else

return (sum - arr[idx].Cnt >= 0) ? sum - arr[idx].Cnt : 0;

}

int main()

{

char a; int b, c;

cin >> N;

arr[1].T = 'S';

for (int i = 2; i <= N; i++)

{

cin >> a >> b >> c;

vt[c].push_back(i);

arr[i].T = a;

arr[i].Cnt = b;

}

cout<<dfs(1)<<endl;

}