QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#226011 | #6745. Delete the Tree | swz | WA | 0ms | 3784kb | C++20 | 1.6kb | 2023-10-25 14:29:00 | 2023-10-25 14:29:00 |
Judging History
answer
//#pragma GCC optimize(3,"Ofast","inline")
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int N = 505 + 5;
vector<int>ed[N];
vector<int>ans[N];
struct TreeD{
ll sz[N], maxp[N], vis[N], sum, rt, cnt; //点分治必备
ll tmp[N];
ll dis[N];
void getrt(ll fa, ll u) //求重心
{
sz[u] = 1, maxp[u] = 0;
for (auto v : ed[u])
{
if (vis[v] || v == fa)
continue;
getrt(u, v);
sz[u] += sz[v];
if (maxp[u] < sz[v])
maxp[u] = sz[v];
}
maxp[u] = max(sum - sz[u], maxp[u]);
if (maxp[u] < maxp[rt])
rt = u;
}
void divide(ll u,ll dep) //点分部分
{
vis[u] = 1;
ans[dep].push_back(u);
for (auto v : ed[u])
{
if (vis[v])
continue;
maxp[rt = 0] = sum = sz[v];
getrt(0, v);
getrt(0, rt);
divide(rt, dep + 1);
}
}
void init(ll n) //点分治,启动!
{
sum = maxp[rt = 0] = n;
getrt(0, 1);
getrt(0, rt);
divide(rt, 1);
}
};
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
ll n;
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
ed[u].push_back(v);
ed[v].push_back(u);
}
TreeD x;
x.init(n);
for(int i=n;i>=1;i--){
if(ans[i].size()){
cout<<ans[i].size()<<" ";
for(auto v:ans[i]){
cout<<v<<" ";
}
cout<<"\n";
}
}
}
}
/*
5
1 2
1 3
1 4
4 5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3784kb
input:
5 1 2 1 3 1 4 4 5
output:
1 4 3 2 3 5 1 1
result:
wrong answer