QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#124732#5157. High-quality Treejzh#WA 101ms50428kbC++141.3kb2023-07-15 14:57:352023-07-15 14:57:46

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-15 14:57:46]
  • 评测
  • 测评结果:WA
  • 用时:101ms
  • 内存:50428kb
  • [2023-07-15 14:57:35]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

const int N = 2e5 + 5;
int dep[N];
int dp[N];
vector<int> G[N];
vector<int> H[N];
int cnt = 0;

void cal(int u) {
    if (dp[u] <= 0)cnt++;
    if (H[u].size() == 1) {
        int to = H[u][0];
        dp[to] = min({dep[to], dp[u] - 1, 1});
        cal(to);
    } else if (H[u].size() == 2) {
        for (int i = 0; i < 2; i++) {
            int r = H[u][i ^ 1];
            int to = H[u][i];
            dp[to] = min({dep[to], dep[r] + 1, dp[u] - 1});
            cal(to);
        }
    }
}

int dfs(int u, int fa) {
    int ans = 0;
    int ans2 = 1e9;
    for (int to: G[u]) {
        if (to == fa)continue;

        H[u].push_back(to);
        int ret = dfs(to, u);
        ans = max(ans, ret);
        ans2 = min(ans2, ret);
        dep[u] = max(dep[u], dep[to]);
    }
    dep[u]++;
    if (H[u].size() == 1) {
        return 2;
    } else if (H[u].size() == 0) {
        return 1;
    } else if (H[u].size() == 2) {
        return min(ans, ans2 + 1);
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int ans = dfs(1, 0);
    dp[1] = 4;
    cal(1);

    cout << cnt << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 13108kb

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: 0ms
memory: 12808kb

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: 0
Accepted
time: 101ms
memory: 37796kb

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:

199998

result:

ok single line: '199998'

Test #4:

score: 0
Accepted
time: 97ms
memory: 50428kb

input:

200000
144434 24107
75087 108465
38670 156657
31235 30143
40544 44213
51188 21788
170574 164351
14169 155909
120876 119956
196361 140453
197958 142813
23944 62568
12098 71652
162226 122184
123783 86178
70076 115586
74439 94246
83296 36713
182500 16937
174946 154091
97484 194764
179943 61793
114439 1...

output:

199998

result:

ok single line: '199998'

Test #5:

score: 0
Accepted
time: 85ms
memory: 25092kb

input:

200000
42469 8516
3910 143673
129125 150433
170053 160404
147325 66173
130784 195620
183508 43943
90940 88012
187183 803
139576 36677
190280 71191
107959 177664
14308 20402
93449 130555
80315 75413
178265 104526
4428 8875
151397 91172
181321 47276
105060 81973
196326 19584
44364 56143
187070 195424
...

output:

199998

result:

ok single line: '199998'

Test #6:

score: -100
Wrong Answer
time: 42ms
memory: 20208kb

input:

131071
94531 87688
119005 53065
70725 126770
61026 82294
114384 270
98205 38915
61461 14652
123122 36872
37639 52311
17774 89648
79899 59785
6033 52465
15449 93250
43849 18174
2665 82543
26740 15199
71645 14339
45549 119270
22896 70677
126250 23614
5796 85715
92715 25280
119740 8911
17923 5547
47703...

output:

131056

result:

wrong answer 1st lines differ - expected: '0', found: '131056'