PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: sushil2006
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
DFS/BFS
PROBLEM:
You’re given a tree of N vertices. Perform the following process:
- Let X = 0 initially.
- N-1 times, choose an existing edge (u, v) and delete it.
Then, update X to either X\oplus \text{siz}(u) or X\oplus \text{siz}(v).
\text{siz}(u) denotes the size of the connected component containing u.
Find the minimum possible final value of X, and a sequence of operations that achieves this minimum.
EXPLANATION:
Let’s look at a few small cases to build intuition.
If N = 2, there is only one possible tree, and we have only one possible move, which will leave X at 1.
If N = 3, there is again only one possible tree (up to isomorphism), and as showcased in the sample we can attain X = 0.
One way of doing is, is to delete any edge and XOR X with 1 (the component size of the isolated vertex), then repeat for the other edge.
It’s not hard to see that the above strategy extends to all odd N: repeatedly choose an edge that disconnects a single vertex, and XOR X with 1.
Since N is odd (and N-1 is even), we do this an even number of times in total; and XOR-ing 1 an even number of times leaves X as 0 in the end.
Since our aim is to minimize X, this is clearly optimal.
That leaves us with even values of N.
It can be observed that the same strategy of disconnecting one vertex at a time will give us X = 1 in the end, which is pretty good.
The only thing better would be if we can obtain X = 0.
That is indeed possible!
Let’s look at N = 4.
Pick an edge that disconnects a single vertex; but now, choose the component with size 3 instead.
Again disconnect a single vertex; and this time choose the component with size 2.
Finally, remove the last edge and choose either component (both of which will have size 1).
This puts the value of X at 3\oplus 2\oplus 1 = 0.
To solve for larger even N, simply keep disconnecting single vertices and XOR-ing X with 1 till you are left with a tree of size 4, then apply the above construction for N = 4.
Note that no matter whether N is even or odd, we need to find a sequence of edges such that each time we remove one, only a single vertex is disconnected.
One easy way of finding such a sequence is to perform a DFS (or BFS) on the tree, and simply take edges in the reverse order of their usage.
To know which connected component to choose upon deleting an edge, track the degrees of every vertex. This is easy to update upon deleting an edge, and finding which vertex got isolated after an edge deletion is simple too: just check which endpoint has degree 0.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
vector<ll> adj[N];
void solve(int test_case)
{
ll n; cin >> n;
rep1(i,n){
adj[i].clear();
}
rep1(i,n-1){
ll u,v; cin >> u >> v;
adj[u].pb(v), adj[v].pb(u);
}
if(n == 2){
cout << 1 << endl;
cout << 1 << " " << 2 << " " << 1 << endl;
return;
}
vector<ll> ord;
queue<ll> q;
vector<ll> par(n+5,-1);
vector<bool> vis(n+5);
q.push(1);
vis[1] = 1;
while(!q.empty()){
ll u = q.front();
q.pop();
ord.pb(u);
trav(v,adj[u]){
if(vis[v]) conts;
q.push(v);
vis[v] = 1;
par[v] = u;
}
}
cout << 0 << endl;
if(n&1){
rev(i,n-1,1){
int u = ord[i], p = par[u];
cout << u << " " << p << " " << u << endl;
}
return;
}
rev(i,n-1,1){
int u = ord[i], p = par[u];
int x = u;
if(i <= 3) x = p;
cout << u << " " << p << " " << x << endl;
}
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
adj = [ [] for _ in range(n) ]
deg = [0]*n
for i in range(n-1):
u, v = map(int, input().split())
adj[u-1].append(v-1)
adj[v-1].append(u-1)
deg[u-1] += 1
deg[v-1] += 1
eord, stk, mark = [], [0]*n, [0]*n
ptr = 0
while ptr >= 0:
u = stk[ptr]
ptr -= 1
mark[u] = 1
for v in adj[u]:
if mark[v] == 0:
eord.append((u, v))
ptr += 1
stk[ptr] = v
if n == 2: print(1)
else: print(0)
x = 0
for u, v in reversed(eord):
who = u if deg[u] == 1 else v
if (n == 4 and x == 0) or (n == 3 and x != 0):
who = u+v - who
x ^= n-1
else: x ^= 1
print(u+1, v+1, who+1)
n -= 1
deg[u] -= 1
deg[v] -= 1