PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: tamminaina_y
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
DFS
PROBLEM:
A tree is said to be good if it has a coloring satisfying the following properties:
- Every color that’s present occurs at least two times.
- For each edge e of the tree, there should be a unique unordered pair of vertices (u, v) such that C_u = C_v and e lies on the path between u and v.
You’re given a tree. Check if it’s good; and if it is, find a valid coloring that uses as few colors as possible.
EXPLANATION:
First off, it can be observed that any coloring where some color appears more than two times will definitely be invalid: there will always exist an edge that’s on the paths of (at least) two different pairs of same-colored vertices.
Proof
Let u, v, w all have the same color.
Consider the path between u and v, and delete all these edges from the tree.
This will create several connected components; and in particular u and v won’t be in the same component (because there’s a unique path between them in the tree, and we deleted this path).Since u and v are not in the same component, w can be in the same component as at most one of them.
So, suppose u and w are in different components.
This means the path from u to w includes some deleted edges: but this means the deleted edges in question lie on both the (u, v) and (u, w) paths, which is not allowed.
So, in a valid coloring, each color must appear either zero times or two times.
One way of thinking about this is that we’re pairing up vertices of the tree; with each pair-up “marking” all edges on the path between them — and every edge should be marked exactly once.
In particular, this immediately tells us that if a tree has an odd number of vertices, it can never be good, so we only need to care about even-sized trees.
Further, it means the number of colors used is always half the number of vertices; so we don’t need to worry about minimizing the number of colors used at all: it’s enough to just find any valid coloring.
Now, we need to analyze when exactly a tree can have a valid coloring.
So, let’s assume that a tree (of even size) has a valid coloring, and see what that tells us.
Consider some edge e of the tree.
If this edge is deleted, the tree breaks into two connected components; say of sizes k and N-k.
Note that we’re dealing with even N here, so both parts have the same parity (i.e. both are even or both are odd).
Now, let’s look at some color c, with the vertices u_c and v_c having this color.
Note that if u_c and v_c lie inside the same connected component, they won’t mark the edge e.
On the other hand, if they lie in different components, they will mark e.
We want e to be marked exactly once.
This is only possible if k (and N-k) are both odd, because every color will add 2 to the sizes of exactly one of the components; except one color which will add 1 to both sizes.
However, observe that there was nothing special about the edge e at all, so this condition applies to every single edge of the tree.
That is, we have the following criterion:
If a valid coloring exists, then deleting any single edge from the tree must result in two odd-sized components.
This is a nice condition, but also a bit unwieldy for our purposes: it’s not immediately obvious how one can construct a valid coloring using it, for example.
Instead, let’s look at it from a different angle.
Suppose we root the tree at vertex 1.
Then, for every vertex u \neq 1, the subtree of u is one of the components obtained when deleting the edge between u and its parent, and hence must have odd size.
So, every subtree of the tree (aside from the entire tree) must have odd size.
This is possible if and only if every vertex has an even number of children (except the root, which will have an odd number of children).
Proof
Further, it’s not hard to actually construct a valid coloring, given that this condition is followed.
Construction
Every (non-root) subtree has odd size, meaning it will have one vertex that isn’t paired.
We’ll try to ensure that this unpaired vertex is always the root of the subtree.Perform a DFS starting at vertex 1.
When at vertex u,
- First, recursively solve for all of its children.
Assuming we’ve done this successfully, only the children of u will be unpaired; and only the edges connecting u to its children will be unsatisfied.- If u is not the root, then it will have an even number of children.
Simply form pairs out of them, and give each pair the same color.
This will ensure that all the children of u are paired up, and all edges between u and its children are satisfied. Only u hasn’t been colored yet, as desired.- if u is the root, it will have an odd number of children.
Once again, pair up the children - and there will be one extra, which should be left alone.
This one extra vertex should then be given the same color as the root, and everything will be satisfied.
This solves the easy version of the task, where we only need to construct a valid coloring if it exists.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #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, vector<int>());
vector<int> ch(n);
string ans = "";
int bad = 0;
for (int i = 1; i < n; ++i) {
int x; cin >> x;
ch[--x] ^= 1;
adj[x].push_back(i);
if (x) {
bad += ch[x] == 1;
bad -= ch[x] == 0;
}
if (i%2 == 0 or bad > 0) ans += "0";
else ans += "1";
}
cout << ans << '\n';
if (ans.back() == '1') {
vector col(n, 0);
int cur = 1;
auto dfs = [&] (const auto &self, int u) -> void {
int prv = -1;
for (int v : adj[u]) {
self(self, v);
if (prv != -1) {
col[prv] = col[v] = cur;
++cur;
prv = -1;
}
else prv = v;
}
if (u == 0) col[u] = col[prv] = cur;
};
dfs(dfs, 0);
for (int x : col) cout << x << ' ';
cout << '\n';
}
}
}