QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#359973#5157. High-quality Treekevinyang#WA 91ms44448kbC++171.5kb2024-03-21 07:33:402024-03-21 07:33:41

Judging History

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

  • [2024-03-21 07:33:41]
  • 评测
  • 测评结果:WA
  • 用时:91ms
  • 内存:44448kb
  • [2024-03-21 07:33:40]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxn = 200005;
vector<vector<int>>adj(mxn);
int n;

int ans = 0;
vector<int>lvl(mxn);
vector<int>dp(mxn);
map<int,int> dfs(int u, int p){
    lvl[u] = lvl[p]+1;
    map<int,int>hm;
    vector<int>nodes;
    for(int nxt: adj[u]){
        if(nxt==p)continue;
        nodes.push_back(nxt);
    }
    if(nodes.size() == 0){
        hm[lvl[u]] = 1;
        dp[u] = lvl[u];
        return hm;
    }
    if(nodes.size() == 1){
        hm = dfs(nodes[0],u);
        hm[lvl[u]] = 1;
        while(dp[nodes[0]] > lvl[u]+1){
            ans+=hm[dp[nodes[0]]];
            hm.erase(dp[nodes[0]]);
            dp[nodes[0]]--;
        }
        dp[u] = lvl[u]+1;
        return hm;
    }
    hm = dfs(nodes[0],u);
    map<int,int>hm2 = dfs(nodes[1],u);
    if(dp[nodes[0]] > dp[nodes[1]]){
        swap(nodes[0],nodes[1]);
    }
    if(hm.size() < hm2.size()){
        swap(hm,hm2);
    }
    for(auto [a,b] : hm2){
        hm[a]+=b;
    }
    while(dp[nodes[1]] > dp[nodes[0]]+1){
        ans+=hm[dp[nodes[1]]];
        hm.erase(dp[nodes[1]]);
        dp[nodes[1]]--;
    }
    dp[u] = dp[nodes[1]];
    return hm;
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i<n; i++){
        int x,y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(1,0);
    cout << ans << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 10936kb

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: 3ms
memory: 10916kb

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
Wrong Answer
time: 91ms
memory: 44448kb

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:

149999

result:

wrong answer 1st lines differ - expected: '199998', found: '149999'