CodeForce - Maximum White Subtree(1324F)

문제(링크)

두 번의 dfs로 해결했습니다.

첫 번째 dfs에선 각 노드마다 그 노드를 root로 했을 때 나올 수 있는 최댓값을 구해 배열에 저장합니다.

두 번째 dfs에선 root노드부터 leaf노드까지 탐색하는데, 부모의 최댓값을 전파하며 내려갑니다.

자식 노드의 최댓값이 0 이상일 경우 -> max(자식 노드의 최댓값, 부모 노드의 최댓값) 을 전파합니다.
자식 노드의 최댓값이 0 보다 작을 경우 -> max(자식 노드의 최댓값 - 1, 부모 노드의 최댓값) 을 전파합니다.
(자식 노드의 최댓값이 0보다 작다는 건 아무리 최대여도 -1을 해줘야 한다는 뜻입니다.)

#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
#include<queue>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pii pair<int, int>
#define ll long long

int N;
int color[200001];
vector<int> vt[200001];
bool visit[200001];
int maxV[200001];
int out[200001];

int dfs(int now) {

 int v = color[now];

 for (int i = 0; i < vt[now].size(); i++)
 {
  int next = vt[now][i];
  
  if (!visit[next]) {
   visit[next] = true;
   v = max(v, dfs(next) + v);
  }
 }

 return maxV[now] = v;
 //now 노드가 root일 때 가질 수 있는 최댓값
}

void dfs2(int now, int prevV) {

 out[now] = prevV;
 //최종 결과값을 배열에 저장

 for (int i = 0; i < vt[now].size(); i++)
 {
  int next = vt[now][i];

  if (!visit[next]) {

   visit[next] = true;

   if(maxV[next] >= 0)
    dfs2(next, max(prevV, maxV[next]));
   //자식 vs 부모 중 큰 값을 전파
   else
    dfs2(next, max(prevV - 1, maxV[next]));
  }
 }
}

int main(void) {
 FIO;

 cin >> N;

 for (int i = 1; i <= N; i++)
 {
  int v;
  cin >> v;
  if (v == 0)
   color[i] = -1;
  else
   color[i] = 1;
 }

 for (int i = 0; i < N - 1; i++)
 {
  int a, b;
  cin >> a >> b;

  vt[a].push_back(b);
  vt[b].push_back(a);
 }

 visit[1] = true;
 dfs(1);
 for (int i = 0; i < 200001; i++)
 {
  visit[i] = false;
 }
 visit[1] = true;
 dfs2(1, maxV[1]);

 for (int i = 1; i <= N; i++)
 {
  cout << out[i] << " ";
 }
}