QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#412992#6745. Delete the TreeSaviorWA 1ms3456kbC++201.4kb2024-05-16 23:18:252024-05-16 23:18:25

Judging History

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

  • [2024-05-16 23:18:25]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3456kb
  • [2024-05-16 23:18:25]
  • 提交

answer

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
#define int long long
using ll = long long;
const int inf = 1e17+7;
const int N=505;
const int mod =1e9+7;
typedef pair<int,int>P;
int mn=inf,rt=0,n=0;
int tot=0;
int sz[N];
vector<int>ans[N];
int vis[N],mx[N];
vector<int>e[N];
void get(int u,int fa){
    sz[u]=1;mx[u]=0;
    for(auto v:e[u]){
        if(v==fa||vis[v]) continue;
        get(v,u);
        mx[u]=max(mx[u],sz[v]);
        sz[u]+=sz[v];
    }
    mx[u]=max(mx[u],n-sz[u]);
    if(mx[u]<mx[rt]) rt=u;
    return;
}
void dfs(int u,int fa,int w){
    if(vis[u]) return;
    ans[w].push_back(u);
    tot=max(tot,w);    
    vis[u]=1;
    for(auto v:e[u]){
        if(v==fa||vis[v]) continue;
        mn=inf;
        if(sz[u]>sz[v])n=sz[v];
        else n=sz[u]-sz[v];
        get(v,u);        
        dfs(rt,0,w+1);
    }
}

void solve(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    get(1,0);
    dfs(rt,0,1);
    cout<<tot<<endl;
    for(int i=tot;i>=0;i--){
        cout<<ans[i].size()<<' ';
        for(auto it:ans[i])
            cout<<it<<' ';
        cout<<endl;
    }
    return;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t=1;//cin>>t;
    while(t--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3456kb

input:

5
1 2
1 3
1 4
4 5

output:

1
1 0 
0 

result:

wrong answer Integer 0 violates the range [1, 5]