Submission #1070724

---

Source Code Expand

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

mt19937 mrand(random_device{} ()); 

int rnd(int x) {
  return mrand() % x;
}

typedef long double ld;
typedef long long ll;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define pb push_back
#define mp make_pair
#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const ld eps = 1e-9;
const ld pi = acos((ld) -1.0);

const int mod = (int) 1e9 + 7;

void add(int &x, int y) {
  if ((x += y) >= mod) {
    x -= mod;
  }
}

int mult(int x, int y) {
  return (long long) x * y % mod;
}

int myPower(int x, int pw) {
  int res = 1;
  for (; pw; pw >>= 1) {
    if (pw & 1) {
      res = mult(res, x);
    }
    x = mult(x, x);
  }
  return res;
}

void precalc() {
}


const int maxn = (int) 2e5 + 10;
string s;
int n;

vector<vector<int> > es, ds, mxds[2];

int read() {
  if (scanf("%d", &n) < 1) {
    return 0;
  }
  es = vector<vector<int> >(n);
  for (int i = 0; i < n - 1; ++i) {
    int s, t;
    scanf("%d%d", &s, &t);
    --s, --t;
    es[s].pb(t), es[t].pb(s);
  }
  cin >> s;
  return 1;
}

int cnt[maxn];

void dfs(int v, int p) {
  if (p != -1) {
    es[v].erase(find(es[v].begin(), es[v].end(), p));
  }
  ds[v].clear();

  cnt[v] = (s[v] == '1');
  for (int u : es[v]) {
    dfs(u, v);
    ds[v].pb(mxds[0][u].back() + 1);
    cnt[v] += cnt[u];
  }
  mxds[0][v].clear();
  mxds[0][v].pb(0);
  for (int i = 0; i < sz(es[v]); ++i) {
    mxds[0][v].pb(max(mxds[0][v].back(), ds[v][i]));
  }

  mxds[1][v].clear();
  mxds[1][v].pb(0);
  for (int i = sz(es[v]) - 1; i >= 0; --i) {
    mxds[1][v].pb(max(mxds[1][v].back(), ds[v][i]));
  }
}

int up[maxn];

long long res;

bool once;

void dfs2(int v) {
  int mxs[2] = {0, 0};
  for (int i = 0; i <= sz(es[v]); ++i) {
    int cur;
    if (i == sz(es[v])) {
      if (!v) {
        continue;
      }
      cur = up[v];
    } else {
      cur = ds[v][i];
    }
    if (mxs[1] < cur) {
      mxs[1] = cur;
      if (mxs[0] < mxs[1]) {
        swap(mxs[0], mxs[1]);
      }
    }
  }
  /*eprintf("v = %d, mxs = {%d>=%d}\n", v, mxs[0], mxs[1]);
  eprintf("up[%d] = %d\n", v, up[v]);
  for (int it = 0; it < sz(es[v]); ++it) {
    eprintf("%d(u=%d)%c", ds[v][it], es[v][it], " \n"[it == sz(es[v]) - 1]);
  }*/
  {
    int from = inf;
    if (s[v] == '1') {
      from = 0;
    } else {
      for (int it = 0; it < sz(es[v]); ++it) {
        int u = es[v][it];
        if (cnt[u]) {
          from = min(from, ds[v][it]);
        }
      }
      if (cnt[0] > cnt[v]) {
        from = min(from, up[v]);
      }
    }
    res += max(0, mxs[1] + 1 - from);
  }
  if (mxs[0] > mxs[1]) {
    bool can = s[v] == '1';
    for (int it = 0; it < sz(es[v]); ++it) {
      if (ds[v][it] < mxs[0] && cnt[es[v][it]]) {
        can = 1;
        break;
      }
    }
    if (cnt[0] > cnt[v] && up[v] < mxs[0]) {
      can = 1;
    }

    if (can) {
      if (mxs[0] == mxs[1] + 1) {
        once = 1;
      } else {
        ++res;
      }
    }
  }
  for (int it = 0; it < sz(es[v]); ++it) {
    int u = es[v][it];
    up[u] = 1 + max(up[v], max(mxds[0][v][it], mxds[1][v][sz(es[v]) - 1 - it]));
    dfs2(u);
  }
}

void solve() {
  ds.resize(n);
  mxds[0].resize(n);
  mxds[1].resize(n);
  dfs(0, -1);

  up[0] = 0;
  res = 0;
  once = 0;
  dfs2(0);
  res += once;
  printf("%lld\n", res);
  //exit(0);
}

int main() {
  precalc();
#ifdef LOCAL
  freopen(TASK ".out", "w", stdout);
  assert(freopen(TASK ".in", "r", stdin));
#endif

  while (1) {
    if (!read()) {
      break;
    }
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int read()’:
./Main.cpp:73:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &s, &t);
                          ^

Judge Result