QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#706011 | #5157. High-quality Tree | magicman1235 | RE | 2ms | 11336kb | C++14 | 1.7kb | 2024-11-03 05:33:58 | 2024-11-03 05:33:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
int n, ans;
vector<int> adj[MAXN];
int l[MAXN], r[MAXN];
int depth[MAXN], subtreeSize[MAXN];
void update(int node)
{
depth[node] = max(depth[l[node]], depth[r[node]]) + 1;
subtreeSize[node] = subtreeSize[l[node]] + subtreeSize[r[node]] + 1;
}
void dfs(int node, int parent)
{
depth[node] = 1;
subtreeSize[node] = 1;
for (int v : adj[node])
{
if (v == parent)
{
continue;
}
if (!l[node])
{
l[node] = v;
}
else
{
r[node] = v;
}
dfs(v, node);
update(node);
}
}
void remove(int node, int dep)
{
if (!node)
{
return;
}
if (dep == 0)
{
ans -= subtreeSize[l[node]] + subtreeSize[r[node]];
l[node] = 0;
r[node] = 0;
depth[node] = 1;
subtreeSize[node] = 1;
return;
}
remove(l[node], dep - 1);
remove(r[node], dep - 1);
update(node);
}
void solve(int node)
{
if (!node)
{
return;
}
solve(l[node]);
solve(r[node]);
if (depth[l[node]] > depth[r[node]])
{
swap(l[node], r[node]);
}
if (depth[r[node]] - depth[l[node]] > 1)
{
remove(r[node], depth[l[node]]);
}
update(node);
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n;
ans = n;
for (int i = 1; i < n; ++i)
{
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1, 0);
solve(1);
cout << n - ans << "\n";
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 11336kb
input:
6 1 2 1 3 3 4 3 5 5 6
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 2ms
memory: 11212kb
input:
12 1 2 2 3 3 4 3 5 1 6 6 7 7 8 7 9 9 10 6 11 11 12
output:
3
result:
ok single line: '3'
Test #3:
score: -100
Runtime Error
input:
200000 167246 158246 40931 40296 178588 27974 35171 899 4204 163250 101422 9230 55420 93371 16012 140142 28866 154497 33519 180725 50361 52348 46923 175364 126599 169575 15138 34958 164256 64770 63123 130169 154172 168301 127476 54744 199964 81879 173765 69220 178225 73653 59861 46415 138112 17507 8...