QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#706011#5157. High-quality Treemagicman1235RE 2ms11336kbC++141.7kb2024-11-03 05:33:582024-11-03 05:33:58

Judging History

你现在查看的是最新测评结果

  • [2024-11-03 05:33:58]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:11336kb
  • [2024-11-03 05:33:58]
  • 提交

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...

output:


result: