/ SeriousOJ /

Record Detail

Compile Error

foo.c:1:10: fatal error: bits/stdc++.h: No such file or directory
    1 | #include <bits/stdc++.h>
      |          ^~~~~~~~~~~~~~~
compilation terminated.

Code

#include <bits/stdc++.h>
using namespace std;

#define all(v) v.begin(), v.end()

using LL = long long;

const int N = 2e5 + 69;

vector <int> adj[N];
int n, active_node, isApple[N], dist[N];

int dfs (int cur, int par) {
  int ret = isApple[cur];    
  if (par != -1) dist[cur] = dist[par] + 1;
  for (auto next : adj[cur]) {
    if (next != par) ret += dfs (next, cur);
  }
  if (ret == 0) active_node--;
  return ret;
}

int main() {
  cin.tie (nullptr) -> ios_base :: sync_with_stdio (false);

  int tests;
  cin >> tests;
  while (tests--) {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> isApple[i], adj[i].clear (), dist[i] = 0;
    for (int i = 1; i < n; i++) {
      int a, b;
      cin >> a >> b;
      adj[a].push_back (b);
      adj[b].push_back (a);
    }
    if (accumulate (isApple + 1, isApple + n + 1, 0) < 2) {
      cout << 0 << '\n';
      continue;
    }
    active_node = n;
    int src = find (isApple + 1, isApple + n + 1, 1) - isApple;
    dfs (src, -1);
    int mx = 0;
    for (int i = 1; i <= n; i++) {
      if (isApple[i] and dist[i] > mx) {
        mx = dist[i];
        src = i;
      }
    }
    fill (dist + 1, dist + n + 1, 0);
    int ans = 2 * (active_node - 1);
    dfs (src, -1);
    mx = 0;
    for (int i = 1; i <= n; i++) {
      if (isApple[i]) mx = max (mx, dist[i]);
    }
    cout << ans - mx << '\n';
  }

  return 0;
}

Information

Submit By
Type
Submission
Problem
P1078 Apple on Tree
Language
C99 (GCC 13.2.0)
Submit At
2024-08-16 19:25:01
Judged At
2024-11-11 03:10:27
Judged By
Score
0
Total Time
0ms
Peak Memory
0 Bytes