/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 4ms 580.0 KiB
#2 Accepted 4ms 584.0 KiB
#3 Accepted 4ms 580.0 KiB
#4 Accepted 5ms 576.0 KiB
#5 Accepted 33ms 2.199 MiB
#6 Accepted 54ms 2.457 MiB
#7 Accepted 37ms 2.285 MiB
#8 Accepted 20ms 600.0 KiB
#9 Accepted 45ms 840.0 KiB
#10 Accepted 64ms 2.297 MiB
#11 Accepted 48ms 2.414 MiB
#12 Accepted 52ms 2.379 MiB
#13 Accepted 26ms 2.57 MiB
#14 Accepted 70ms 2.59 MiB
#15 Accepted 31ms 936.0 KiB
#16 Accepted 21ms 2.418 MiB
#17 Accepted 25ms 2.422 MiB
#18 Accepted 23ms 2.25 MiB
#19 Accepted 73ms 13.477 MiB
#20 Accepted 80ms 13.34 MiB
#21 Accepted 69ms 13.316 MiB
#22 Accepted 91ms 21.691 MiB
#23 Accepted 151ms 12.918 MiB
#24 Accepted 153ms 12.828 MiB
#25 Accepted 87ms 12.773 MiB
#26 Accepted 8ms 1.289 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-11-11 03:10:26
Judged By
Score
100
Total Time
153ms
Peak Memory
21.691 MiB