Submission #2503121

---

Source Code Expand

#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cout << #x << " = " << x << endl
#define _ << " _ " <<

typedef long long llint;

const int MAX = 100100;

struct Dp {
  int loop, stay;
  bool all_black;
};

Dp fdown[MAX];
Dp fup[MAX];

char colors[MAX];
int parent[MAX];
vector<int> E[MAX];

Dp compute(int color, int total_loop, int min_diff, int cnt) {
  if (cnt == 0) {
    if (color) return {0, 0, true};
    else return {0, 0, false};
  } else {
    int nloop_color = color ^ 1 ^ (cnt % 2);
    int loop = total_loop + (nloop_color == 0) + 2*cnt;
    int stay = total_loop + min_diff + (nloop_color == 1) + 2*cnt - 1;
    return {loop, stay, false};
  }
}

int computeRoot(int color, int total_loop, int min_diff, int cnt) {
  if (cnt == 0) return color == 0 ? 1 : 0;

  int nloop_color = color ^ (cnt % 2);
  int loop = total_loop + (nloop_color == 0) + 2*cnt;
  int stay = total_loop + min_diff + (nloop_color == 1) + 2*cnt - 1;
  return min(stay, loop);
}

void dfs_down(int x, int dad) {
  int total_loop = 0;
  int min_diff = 0;
  int cnt = 0;
  for (int y: E[x]) {
    if (y != dad) {
      dfs_down(y, x);

      if (!fdown[y].all_black) {
        cnt++;
        total_loop += fdown[y].loop;
        assert(fdown[y].stay <= fdown[y].loop);
        min_diff = min(min_diff, fdown[y].stay - fdown[y].loop);
      }
    }
  }

  fdown[x] = compute(colors[x], total_loop, min_diff, cnt);
}

int dfs_up(int x, int dad) {
  int min_diff1 = 0, min_diff2 = 0, cnt = 0, total_loop = 0;

  auto update = [&] (Dp f) {
    if (!f.all_black) {
      cnt++;
      total_loop += f.loop;
      int diff = f.stay - f.loop;
      if (diff <= min_diff1) min_diff2 = min_diff1, min_diff1 = diff;
      else if (diff < min_diff2) min_diff2 = diff;
    }
  };

  update(fup[x]);

  for (int y: E[x]) {
    if (y != dad) {
      update(fdown[y]);
    }
  }

  int ret = computeRoot(colors[x], total_loop, min_diff1, cnt);

  for (int y: E[x]) {
    if (y != dad) {
      if (fdown[y].all_black) {
        fup[y] = compute(colors[x], total_loop, min_diff1, cnt);
      } else {
        int diff = fdown[y].stay - fdown[y].loop;
        fup[y] = compute(colors[x], total_loop - fdown[y].loop, min_diff1 == diff ? min_diff2 : min_diff1, cnt - 1);
      }

      ret = min(ret, dfs_up(y, x));
    }
  }

  return ret;
}

int main(void) {
  int N;
  scanf("%d", &N);

  REP(i, N-1) {
    int a, b;
    scanf("%d %d", &a, &b);
    --a, --b;
    E[a].push_back(b);
    E[b].push_back(a);
  }
  scanf("%s", colors);
  REP(i, N) colors[i] = colors[i] == 'B';

  dfs_down(0, -1);

  fup[0] = {0, 0, true};
  int ret = dfs_up(0, -1);
  printf("%d\n", ret);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:112:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
                  ^
./Main.cpp:116:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &a, &b);
                           ^
./Main.cpp:121:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", colors);
                      ^

Judge Result