QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#878504 | #7936. Eliminate Tree | fractal# | WA | 1ms | 13296kb | C++17 | 982b | 2025-02-01 15:43:42 | 2025-02-01 15:43:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
const int N = 2e5 + 200;
int n, d[N], used[N], anc[N];
vector<int> g[N], is[N];
void dfs(int v, int p) {
is[d[v]].push_back(v);
for (int u : g[v]) {
if (u == p) continue;
d[u] = d[v] + 1;
anc[u] = v;
dfs(u, v);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1, v, u; i < n; ++i) {
cin >> v >> u;
g[v].push_back(u);
g[u].push_back(v);
}
dfs(1, 0);
int ans = 0;
used[0] = 1;
for (int i = n; i >= 0; --i) {
for (auto v : is[i]) {
if (used[v]) continue;
if (used[anc[v]] == 0) {
used[anc[v]] = 1;
used[v] = 1;
ans++;
}
}
}
cout << n + (n - (2 * ans)) << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 13296kb
input:
5 1 2 2 3 3 4 3 5
output:
6
result:
wrong answer 1st numbers differ - expected: '4', found: '6'