# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
268005402 |
Practice:
Mhn_Neek |
1521D
- 43
|
C++20 (GCC 13-64)
|
Wrong answer on test 2
|
187 ms
|
22320 KB
|
2024-06-29 16:34:37 |
2024-06-29 16:34:37 |
|
//In the name of God
#include<bits/stdc++.h>
/*MHN*/
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
using namespace std;
typedef long long int lli;
typedef long double ld;
typedef pair<lli,lli> pii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N=4e5+100;
const lli mod=1e9+7;//998244353;
const lli INF=1e18;
lli power(lli x,lli y){lli res = 1;x = x % mod;while(y>0){if( y & 1 ){res = (res * x) % mod;}y = y >> 1;x = (x * x)%mod;}return res;}
lli modinv(lli x){return power(x,mod-2);}
lli divide(lli x,lli y){return ((x%mod) * modinv(y))%mod;}
lli Tarkib(lli n, lli r){if(n<r)return 0;if(r==0)return 1;if(n-r < r)return Tarkib(n,n-r);lli res = 1;for(lli i = r; i >= 1; i--)res = divide(((res%mod) * (n-i+1))%mod,i);return res;}
#define all(v) v.begin(),v.end()
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define migmig ios_base::sync_with_stdio(false),cout.tie(0), cin.tie(0);
#define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define set_preci(x) cout << fixed << setprecision(x);
#define debug(x) cerr << (#x) << " " << (x) << endl
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define SUM(v) accumulate(v.begin(),v.end(), 0LL)
#define FOR(x,n) for(lli x = 0; x < n; x++)
#define FORS(x,n) for(lli x = 1; x <= n; x++)
#define TEST int T; cin>>T;while(T--)
#define BN(l,a) while(l){a.PB(l%2);l/=2;}
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define sep " "
lli tmp;
set<lli> v[N];
lli deg[N];
lli n;
bool vis[N];
ve leaf;
void dfs(lli u){
vis[u] = 1;
if(deg[u]==1 && tmp < 2){
leaf.PB(u);
tmp ++;
}
if(deg[u]==0){
leaf.PB(u);
leaf.PB(u);
}
for(auto i : v[u]){
if(vis[i])
continue;
dfs(i);
}
}
int main(){
migmig;
TEST{
cin>>n;
FOR(i,n-1){
lli a,b;
cin>>a>>b;
v[a].insert(b);
v[b].insert(a);
deg[a]++;
deg[b]++;
}
lli del = 0;
vp p1;
FORS(i,n){
vp g;
for(auto u : v[i]){
if(deg[i]<=2)
break;
if(deg[u]<=2)
break;
del++;
deg[i]--;
deg[u]--;
g.PB(MP(i,u));
p1.PB(MP(i,u));
}
for(auto u : g){
v[u.fi].erase(v[u.fi].find(u.se));
v[u.se].erase(v[u.se].find(u.fi));
}
}
FORS(i,n){
vp g;
for(auto u : v[i]){
if(deg[i]<=2)
break;
if(deg[u]<=1)
break;
del++;
deg[i]--;
deg[u]--;
g.PB(MP(i,u));
p1.PB(MP(i,u));
}
for(auto u : g){
v[u.fi].erase(v[u.fi].find(u.se));
v[u.se].erase(v[u.se].find(u.fi));
}
}
FORS(i,n){
vp g;
for(auto u : v[i]){
if(deg[i]<=2)
break;
del++;
deg[i]--;
deg[u]--;
g.PB(MP(i,u));
p1.PB(MP(i,u));
}
for(auto u : g){
v[u.fi].erase(v[u.fi].find(u.se));
v[u.se].erase(v[u.se].find(u.fi));
}
}
FORS(i,n){
if(vis[i])
continue;
dfs(i);
tmp = 0;
}
vp p2;
lli s = leaf.size();
FORS(i,s-2){
p2.PB(MP(leaf[i],leaf[i+1]));
i ++;
}
cout<<del<<endl;
FOR(i,del){
cout<<p1[i].fi<<sep<<p1[i].se<<sep<<p2[i].fi<<sep<<p2[i].se<<endl;
}
FORS(i,n){
v[i].clear();
vis[i] = 0;
deg[i] = 0;
}
leaf.clear();
}
}
Click to see test details