TREECOLOUR - Editorial

editorial
, , ,
1

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 start with a single vertex. N-1 times, a new vertex will be attached to an existing vertex of the tree.
After each operation, your task is to decide whether the tree is good or not.
In the end, if the final tree with N vertices is good, find a valid coloring of it as well, which uses as few colors as possible.

EXPLANATION:

From the solution to the easy version (which only needed us to construct a coloring for a single tree when it exists), we know the following:

A tree is good if and only if it has an even number of vertices, and when rooted at 1, every vertex other than 1 has an even number of children.

We know how to find a coloring of the final tree if it’s good, so the only part left is maintaining whether every intermediate tree is good or not.

For that, let’s define c_u to be the number of children of vertex u, and K to be the number of vertices (other than 1) with an odd number of children.

Initially, c_u = 0 for all u, and K = 0.
When adding a new vertex as a child of u,

  • c_u increases by 1.
  • If u = 0, K doesn’t need to be updated.
  • Otherwise,
    • If c_u is now odd, increase K by 1. This is because c_u would’ve been even before the addition.
    • Conversely, if c_u is now even, it was odd before the addition. So, reduce K by 1.

After the updates, if N is even and K = 0 the tree is good, otherwise it isn’t.
Each update is processed in constant time, and the final coloring is also found in linear time, so this is \mathcal{O}(N) overall.

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';
        }
    }
}