/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 4ms 532.0 KiB
#2 Accepted 4ms 580.0 KiB
#3 Accepted 4ms 576.0 KiB
#4 Accepted 5ms 576.0 KiB
#5 Accepted 38ms 2.316 MiB
#6 Accepted 43ms 2.32 MiB
#7 Accepted 34ms 2.273 MiB
#8 Accepted 19ms 576.0 KiB
#9 Accepted 42ms 772.0 KiB
#10 Accepted 61ms 2.227 MiB
#11 Accepted 44ms 2.562 MiB
#12 Accepted 55ms 2.398 MiB
#13 Accepted 25ms 2.562 MiB
#14 Accepted 63ms 2.574 MiB
#15 Accepted 27ms 944.0 KiB
#16 Accepted 20ms 2.273 MiB
#17 Accepted 19ms 2.32 MiB
#18 Accepted 18ms 2.414 MiB
#19 Accepted 70ms 13.34 MiB
#20 Accepted 70ms 13.328 MiB
#21 Accepted 66ms 13.484 MiB
#22 Accepted 85ms 21.941 MiB
#23 Accepted 147ms 12.988 MiB
#24 Accepted 146ms 12.984 MiB
#25 Accepted 81ms 12.672 MiB
#26 Accepted 8ms 1.316 MiB

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
C++20 (G++ 13.2.0)
Submit At
2024-08-16 19:25:09
Judged At
2024-10-03 13:20:10
Judged By
Score
100
Total Time
147ms
Peak Memory
21.941 MiB