QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#225162#5502. Dazzling MountainGawor270RE 0ms3808kbC++141.7kb2023-10-24 01:54:112023-10-24 01:54:11

Judging History

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

  • [2023-10-24 01:54:11]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3808kb
  • [2023-10-24 01:54:11]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define debug(x) cout << "[" <<  #x << " " << x << "] ";

#define ar array
#define ll long long
#define ld long double
#define sz(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()

typedef vector<int> vi;
typedef pair<int,int> pi;

const int MAX_N = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
vector<vector<int>> tree;
vector<int> dh;
vector<bool> vis;
pi countleafes(int v){
    vis[v] = true;
    int count = 0;
    int countl = 0;
    int sum = 0;
    for(int u : tree[v]){
        if(!vis[u]){
            count++;
            pi res = countleafes(u);
            sum += res.first;
            countl += res.second;
        }
    }
    if(count){
        dh[sum] += countl;
        return {sum+1,countl};
    }
    else{
        return {1,1};
    }
}



void solve() {
    int n;
    cin >> n;
    tree.resize(n);
    dh.resize(n);
    vis.resize(n,false);
    for(int i=0; i<n-1; i++){
        int a,b;
        cin >> a >> b;
        tree[--a].push_back(--b);
        tree[b].push_back(a);
    }
    int no_leafes = countleafes(0).second;

    int count = 0;
    vi ans = {1};
    for(int i=0; i<n; i++){
        if(dh[i] == no_leafes){
            count++;
            ans.push_back(i+1);
        }
    }
    cout << ans.size() << "\n";
    for(int x : ans){
        cout << x << " ";
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int tc = 1;
    cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t << ": ";
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3808kb

input:

1
9
1 2
2 3
3 4
3 5
2 6
6 7
7 8
7 9

output:

4
1 3 8 9 

result:

ok 2 lines

Test #2:

score: -100
Runtime Error

input:

10000
906
675 189
555 889
491 97
791 419
175 694
713 842
788 513
159 354
670 815
652 546
253 87
89 278
563 429
522 900
202 657
331 865
35 605
735 532
612 471
657 386
7 886
856 164
224 777
73 534
481 631
711 698
240 465
115 181
191 825
311 155
709 501
207 849
294 546
591 682
96 405
210 696
861 13
781...

output:


result: