모두 0으로 만들기

https://programmers.co.kr/learn/courses/30/lessons/76503

내가 지금껏 못풀어본 트리 + dfs 문제 유형
못풀었음.

#include <string>
#include <vector>

using namespace std;
long long answer(0);

void dfs(vector<long long> &sum, vector<vector<int>> &edges, int now, int parent)
{
	for (int i = 0; i < edges[now].size(); i++)//현재부터 연결된 곳둘
	{
		if (edges[now][i] != parent)//연결되어 있는 곳이 부모 노드가 아닌 경우에만 dfs로 파고든다. 
		{
			dfs(sum, edges, edges[now][i], now);//dfs로 트리를 파고 들어간다.
		}
	}

	sum[parent] += sum[now];//더이상 파고들어갈 곳이 없음.
	answer += abs(sum[now]);
	
	return;//타고들어간 dfs 마지막일경우 반환한다. 트리구조이기 때문에 chk배열이 애초에 필요하지 않다. 
}


long long solution(vector<int> a, vector<vector<int>> edges) {
	

	vector<long long> sum(a.size());
	for (int i = 0; i < a.size(); i++)
	{
		sum[i] = a[i];
	}

	vector<vector<int>> tree(a.size());

	for (int i = 0; i < edges.size(); i++)
	{
		tree[edges[i][0]].emplace_back(edges[i][1]);
		tree[edges[i][1]].emplace_back(edges[i][0]);
	}

	dfs(sum, tree, 0, 0 );//처음 시작하는 노드를 0으로 잡고 시작한다. 

	int flag(0);
	if(sum[0]!=0)	return -1;



	return answer;
}

int main()
{


	//vector<int> vTemp = { 1,5,8,4,6 };
	//vector<int> vTemp1;
	//vTemp1.assign(vTemp.begin(), vTemp.end());
	//장르 100개 미만.

	vector<int> vTemp = { -5,0,2,1,2 };
	vector<vector<int>> vvTemp = { {0, 1},{3,4},{2,3},{0,3} };

	vector<int> vTemp1 = { 0,1,0 };
	vector<vector<int>> vvTemp1 = { { 0,1 },{ 1,2 }};

	long long lTemp= solution(vTemp, vvTemp);



	return 0;

}

[트리]
1. 루트 노드의 부모는 자기 자신
2. 루트 노드는 정해져있지 않음.(0으로 잡고 시작한다)
3. 방문 체크를 할 필요가 없음
왜냐면 트리형태 자체가 재방문을 하지 않기 때문이다.
다만, 연결된 노드에 부모 노드가 포함되므로, 부모 노드가 아닌 노드들만 DFS 에 들어가는 것이 핵심이다.
4. 먼저 최대한 깊이 들어가고, 자식 노드로부터 되돌아가는 과정의 노드에서 문제 요구사항의 업데이트를 한다.