QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#387242 | #6745. Delete the Tree | Lackofgod | WA | 0ms | 3912kb | C++14 | 1.9kb | 2024-04-12 10:46:39 | 2024-04-12 10:46:39 |
Judging History
answer
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <map>
#include <bitset>
#include <stack>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <queue>
#define forn(i,aa,bb) for(int i=aa;i<=bb;++i)
#define LL long long
using namespace std;
const int N=500+5;
const LL mod=998244353;
const int MAXX=1e9;
int n;
vector<int> ed[N];
int sub[N];
int fa[N];
bool vis[N];
void dfs1(int x){
vis[x]=1;
for(int y:ed[x]) {
if (vis[y]) continue;
fa[y]=x;
dfs1(y);
}
}
void dfs(int x,int minm,int &id){
sub[x]=1;
int maxm=0;
for(int y:ed[x]) {
if (y==fa[x]) continue;
fa[x]=y;
dfs(y,minm,id);
sub[x]+=sub[y];
maxm=max(maxm,sub[y]);
}
maxm=max(maxm,n-sub[x]);
if (maxm<=minm) minm=maxm,id=x;
}
vector<int> ed1[N];
queue<int> q;
bool vis1[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
//cin>>T;
T=1;
while (T--) {
cin>>n;
forn(i,1,n-1) {
int x,y;
cin>>x>>y;
ed[x].push_back(y);
ed[y].push_back(x);
}
int root,num=0;
q.push(1);
while (!q.empty()) {
int cnt=q.size();
num++;
while (cnt) {
int k=q.front(); q.pop();
dfs(k,MAXX,root);
dfs1(root);
ed1[num].push_back(root);
vis1[root]=1;
for(int y:ed[root]) {
if (vis1[y]) continue;
q.push(y);
}
cnt--;
}
forn(i,1,n)
vis[i]=0;
}
cout<<num<<'\n';
for(int i=num;i>=1;--i) {
for(int x:ed1[i])
cout<<x<<' ';
cout<<'\n';
}
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3912kb
input:
5 1 2 1 3 1 4 4 5
output:
3 5 2 3 4 1
result:
wrong output format Unexpected end of file - int32 expected