PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: satyam_343
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
2540
PREREQUISITES:
DFS, finding a tree’s centroid
PROBLEM:
You’re given a tree on N vertices.
For a fixed root r and permutation P of the vertices, the score of the tree is defined to be the size of the set \{\text{lca}(P_i, P_{i+1}) \mid 1 \leq i \lt N\}.
Find the minimum possible score, and also values of r and P that attain this minimum.
EXPLANATION:
For a fixed root r and permutation P of the vertices, let S(r, P) denote the set \{\text{lca}(P_i, P_{i+1}) \mid 1 \leq i \lt N\}, and |S(r, P)| denote its size.
The best we can hope to do is to achieve a score of 1, so let’s check if that’s possible.
Suppose we root the tree at r.
Then, \text{lca}(r, x) = r for any vertex x, so no matter which P we choose, the set S(r, P) will contain r.
Thus, if we want |S(r, P)| = 1, we have to check whether there exists a permutation P such that \text{lca}(P_i, P_{i+1}) = r for every i.
Let the children of r be vertices c_1, c_2, \ldots, c_k, and their corresponding subtrees be T_1, T_2, \ldots, T_k.
Note that if two adjacent elements of P are from the same T_i, then their \text{lca} can never be r.
So, we need to check whether there exists an ordering such that adjacent vertices are from distinct subtrees.
Intuitively, if one of the subtrees is too large, this is not possible.
In particular, if some subtree has size \gt \left\lceil \frac{N}{2}\right\rceil, then any ordering will have some two vertices of this subtree adjacent to each other.
What about the case when all the subtrees have sizes \leq \left\lceil \frac{N}{2}\right\rceil?
In fact, we can always find a valid ordering in that case!
There are many constructions, here’s one.
Let’s sort the subtrees T_1, T_2, \ldots, T_k in descending order of size, i.e, size(T_i) \geq size(T_{i+1}).
We’ll place all vertices from T_1 first, then T_2, then T_3, and so on.
To ensure that no two from the same subtree are adjacent, place vertices at positions 1, 3, 5, 7, \ldots followed by 2, 4, 6, 8, \ldots
That is, fill the odd positions first, and then fill the even positions.
Of course, this construction hinges on the fact that all children of the root have subtree sizes not exceeding \frac{N}{2}, so we need to find such a root r first.
The simplest way to do this is to choose a vertex that minimizes the value of its maximum child subtree size — it can be proved that for such a vertex, the maximum subtree size will be \leq \left\lfloor \frac{N}{2} \right\rfloor.
Such a vertex is also called a centroid of the tree, and can easily be found in \mathcal{O}(N). See the first section of this page, for example.
TIME COMPLEXITY
\mathcal{O}(N\log N) per test case.
CODE:
Setter's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
void _print(ll x){cerr<<x;}
void _print(int x){cerr<<x;}
void _print(char x){cerr<<x;}
void _print(string x){cerr<<x;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";}
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=1e9+7;
const ll MAX=100100;
ll root,n;
vector<ll> adj[MAX];
vector<ll> subtree(MAX);
ll now=0,till=log2(MAX)+1;
vector<ll> tin(MAX,0),tout(MAX,0),depth(MAX,0);
vector<vector<ll>> jump(MAX,vector<ll>(till+1,0));
void dfs(ll cur,ll par){
jump[cur][0]=par;
for(ll i=1;i<=till;i++)
jump[cur][i]=jump[jump[cur][i-1]][i-1];
tin[cur]=++now;
for(ll chld:adj[cur]){
if(chld!=par){
depth[chld]=depth[cur]+1;
dfs(chld,cur);
}
}
tout[cur]=++now;
}
bool is_ancestor(ll a,ll b){
if((tin[a]<=tin[b])&&(tout[a]>=tout[b]))
return 1;
return 0;
}
ll lca(ll a,ll b){
if(is_ancestor(a,b))
return a;
for(ll i=till;i>=0;i--){
if(!is_ancestor(jump[a][i],b))
a=jump[a][i];
}
return jump[a][0];
}
void dfs_1(ll cur,ll par){
subtree[cur]=1;
ll nax=0;
for(auto chld:adj[cur]){
if(chld!=par){
dfs_1(chld,cur);
nax=max(nax,subtree[chld]);
subtree[cur]+=subtree[chld];
}
}
nax=max(nax,n-subtree[cur]);
if(2*nax <= n){
root=cur;
}
}
vector<ll> track(MAX,0);
void dfs_2(ll cur,ll par){
for(auto chld:adj[cur]){
if(chld!=par){
if(cur==root){
track[chld]=chld;
}
else{
track[chld]=track[cur];
}
dfs_2(chld,cur);
}
}
}
void solve(){
cin>>n;
for(ll i=1;i<n;i++){
ll u,v; cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs_1(1,-1);
track[root]=root;
dfs_2(root,-1);
dfs(root,root);
vector<pair<ll,ll>> order;
for(ll i=1;i<=n;i++){
order.push_back({track[i],i});
}
sort(all(order));
cout<<root<<nline;
vector<set<ll>> use(n+5);
for(ll i=1;i<=n;i++){
use[track[i]].insert(i);
}
set<pair<ll,ll>> comp;
for(ll i=1;i<=n;i++){
comp.insert({use[i].size(),i});
adj[i].clear();
}
debug(comp);
ll prv=-1;
for(ll i=1;i<=n;i++){
auto it=--comp.end();
ll node;
while(1){
if((*it).s!=prv){
break;
}
it--;
}
node=(*it).s;
debug(mp(i,node));
comp.erase({use[node].size(),node});
cout<<*use[node].begin()<<" \n"[i==n];
use[node].erase(use[node].begin());
comp.insert({use[node].size(),node});
prv=node;
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
Tester's code (C++)
//clear adj and visited vector declared globally after each test case
//check for long long overflow
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Incase of close mle change language to c++17 or c++14
//Check ans for n=1
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 1000000007ll //998244353ll
#define lld long double
#define mii map<int, int>
#define pii pair<int, int>
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
typedef std::numeric_limits< double > dbl;
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
const long long N=200005, INF=2000000000000000000;
const int inf=2e9 + 5;
lld pi=3.1415926535897932;
int lcm(int a, int b)
{
int g=__gcd(a, b);
return a/g*b;
}
int power(int a, int b, int p)
{
if(a==0)
return 0;
int res=1;
a%=p;
while(b>0)
{
if(b&1)
res=(1ll*res*a)%p;
b>>=1;
a=(1ll*a*a)%p;
}
return res;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int getRand(int l, int r)
{
uniform_int_distribution<int> uid(l, r);
return uid(rng);
}
vi v[N];
int siz[N];
void dfs1(int u, int p)
{
siz[u]=1;
for(auto to:v[u])
{
if(to==p)
continue;
dfs1(to, u);
siz[u]+=siz[to];
}
}
int dfs2(int u, int p, int tot)
{
for(auto to:v[u])
{
if(to==p)
continue;
if(siz[to]>(tot/2))
return dfs2(to, u, tot);
}
return u;
}
vi ord;
void dfs3(int u, int p)
{
ord.pb(u);
for(auto to:v[u])
{
if(to==p)
continue;
dfs3(to, u);
}
}
int centroid(int x)
{
dfs1(x, 0);
return dfs2(x, 0, siz[x]);
}
int32_t main()
{
IOS;
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
rep(i,1,n+1)
v[i].clear();
rep(i,0,n-1)
{
int a, b;
cin>>a>>b;
v[a].pb(b);
v[b].pb(a);
}
int x=centroid(1);
assert(siz[1]==n);
vector <vector <int> > sub;
sub.pb({x});
cout<<x<<"\n";
for(auto to:v[x])
{
ord.clear();
dfs3(to, x);
sub.pb(ord);
}
int sz=sub.size();
set <pii> s;
rep(i,0,sz)
s.insert({sub[i].size(), i});
vi res;
while(res.size()<n)
{
pii p=*s.rbegin();
s.erase(p);
res.pb(sub[p.ss].back());
sub[p.ss].pop_back();
if(res.size()<n)
{
pii p1=*s.rbegin();
s.erase(p1);
res.pb(sub[p1.ss].back());
sub[p1.ss].pop_back();
p1.ff--;
s.insert(p1);
}
p.ff--;
s.insert(p);
}
for(auto num:res)
cout<<num<<" ";
cout<<"\n";
}
}
Editorialist's code (C++)
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector adj(n+1, vector<int> ());
for (int i = 0; i < n-1; ++i) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector subsz(n+1, 0), par(n+1, 0);
vector<int> order, ans(n);
int centroid = 1;
auto dfs_sz = [&] (const auto &self, int u) -> void {
subsz[u] = 1;
for (int v : adj[u]) {
if (v == par[u]) continue;
par[v] = u;
self(self, v);
subsz[u] += subsz[v];
}
};
auto dfs_order = [&] (const auto &self, int u, int p) -> void {
if (u == centroid) sort(begin(adj[u]), end(adj[u]), [&] (int x, int y) { // Sorting subtrees by size
int v = x == par[u] ? n - subsz[u] : subsz[x];
int w = y == par[u] ? n - subsz[u] : subsz[y];
return v > w;
});
for (int v : adj[u]) {
if (v == p) continue;
self(self, v, u);
}
order.push_back(u);
};
dfs_sz(dfs_sz, 1);
for (int i = 1; i <= n; ++i) {
int mx = n - subsz[i];
for (int v : adj[i]) {
if (v == par[i]) continue;
mx = max(mx, subsz[v]);
}
if (mx <= n/2) centroid = i;
}
cout << centroid << '\n';
dfs_order(dfs_order, centroid, -1);
int pos = 0;
for (int x : order) {
ans[pos] = x;
pos += 2;
if (pos >= n) pos = 1;
}
for (int x : ans) cout << x << ' ';
cout << '\n';
}
}