Hello Codeforces!

A few months ago, I wrote a blog post about Random heavy light decomposition. Today, I want to discuss a powerful extension of this idea.

How do you usually solve problems where a tree grows online? That is, you process queries that attach a new vertex to the tree, while simultaneously answering queries on paths (e.g., finding the minimum on a path).

Let's try to solve this using Heavy-Light Decomposition (HLD).

The Flaw of Naive HLD

At first glance, one might try a naive approach: when a new vertex is added, simply extend the existing HLD path into it. However, this creates a major vulnerability.

Consider the following case:

Imagine we repeatedly attach new vertices to form a long path. We extend the HLD path into each of them. But then, we attach a new vertex directly to the root, and subsequently attach all future vertices into its subtree The heavy path we initially built is now useless, and for our new branches, we end up with $$$O(N)$$$ light edges instead of the guaranteed $$$O(\log N)$$$.

One way to fight this is to use query square root decomposition: we can completely rebuild the HLD every $$$\sqrt{Q}$$$ queries. However, this adds an extra $$$O(\sqrt{Q})$$$ factor to our complexity, which is quite unpleasant.

Moreover, intuitively, rebuild entire HLD seems like doing a lot of useless work: most paths aren't touched at all, and those that are touched usually only need updates on a short suffix. We want to rebuild the HLD incrementally, piece by piece, only when absolutely necessary.

An excellent way to achieve this is Randomized HLD.

The Elegance of rnd HLD

Let's assign each vertex a random priority $$$y_v$$$ (e.g., a random integer chosen from $$$[0, 10^9]$$$).

Let $$$smin_v$$$ be the minimum priority $$$y_u$$$ for all $$$u$$$ in the subtree of $$$v$$$, strictly excluding $$$v$$$ itself. We then direct the heavy edge from $$$v$$$ to the child $$$c$$$ whose subtree contains the vertex with priority $$$smin_v$$$.

Proof 1: Expected number of light edges is $$$O(\log N)$$$

Why does this work? Notice that the minimum of $$$S$$$ independent uniform random variables is equally likely to be any of them. Thus, the probability that the minimum priority in $$$v$$$'s subtree falls into the subtree of a specific child $$$u$$$ is exactly $$$\frac{sz_u}{sz_v - 1}$$$.

This means the probability of edge $$$(v, u)$$$ being heavy is exactly proportional to the subtree size! This perfectly reduces to the mathematical proof from my previous blog post:

Thus, the expected number of light edges on any path to the root remains bounded by $$$O(\log N)$$$.

Handling Online Tree Growth

Now, how do we implement the operation of attaching a new vertex new to a parent p?

We simply go up the parent pointers starting from p, as long as $$$smin_{ancestor} \gt y_{new}$$$. Let $$$u$$$ be the highest ancestor we reach where this condition holds. This means $$$y[new]$$$ is now the absolute minimum priority in the subtree of $$$u$$$. We completely rebuild the HLD for the entire subtree of $$$u$$$. For the path that previously went into $$$u$$$, we just update its suffix.

Is this fast enough? Absolutely.

Proof 2: The expected size of the rebuilt subtree is $$$O(\log N)$$$

Let the ancestors of new be $$$p_1, p_2, \dots, p_D$$$ (going up to the root), and let $$$W_k$$$ be the size of $$$p_k$$$'s subtree after adding the new vertex (so $$$W_1 \lt W_2 \lt \dots \lt W_D$$$).

We rebuild the subtree of $$$p_k$$$ if and only if $$$y[new]$$$ is the absolute minimum in the subtree of $$$p_k$$$, but not in the subtree of $$$p_{k+1}$$$. Since $$$y[new]$$$ is a random priority among $$$W_k$$$ vertices, the probability that it is the minimum is $$$\frac{1}{W_k}$$$.

The probability that we rebuild exactly the subtree of $$$p_k$$$ is:

The expected size $$$E$$$ of the rebuilt subtree is the sum of sizes multiplied by their probabilities:

Using the integral bounding technique ($$$\int \frac{1}{x} dx = \ln x$$$):

Therefore, the expected size of the completely rebuilt subtree is bounded by $$$\ln(N) + 1$$$!

Solving the Problem

Let's apply this to a specific task. I started talking about this technique while solving this problem.

Initially, there is a root $$$r$$$ with value $$$a_r$$$. We need to process 3 types of queries online:

1. hang p a_new — attach a new vertex to $$$p$$$ with value $$$a_{new}$$$

2. set v a_new — update $$$a_v := a_{new}$$$

3. get u v x — find the minimum $$$a_s \ge x$$$ where $$$s$$$ lies on the simple path between $$$u$$$ and $$$v$$$

We can solve this using our rnd HLD. To answer the get queries, we need a data structure on each heavy path. We will maintain a Segment Tree where each node contains a std::multiset (a Dynamic Merge Sort Tree).

Let's calculate the expected time complexity for each operation:

• set v a_new: The vertex $$$v$$$ belongs to exactly one heavy path. A point update in a Segment Tree of multisets requires updating $$$O(\log N)$$$ nodes. In each node, we erase the old value and insert the new one in $$$O(\log N)$$$ time. Time: $$$O(\log^2 N)$$$ expected.

• get u v x: Thanks to rnd HLD, the path is split into $$$O(\log N)$$$ expected heavy path segments. On each segment, we query the Segment Tree, covering $$$O(\log N)$$$ nodes. Inside each of these nodes, we find the answer via multiset::lower_bound in $$$O(\log N)$$$. Time: $$$O(\log^3 N)$$$ expected.

• hang p a_new: We just proved the expected size of the rebuilt subtree is $$$W \le \ln(N) + 1$$$. Rebuilding the HLD structure takes $$$O(W)$$$. Rebuilding the Segment Tree of multisets for paths of total length $$$W$$$ takes $$$O(W \log W)$$$ (if we build it bottom-up). The expected rebuild time is $$$ \sum P_k \cdot O(W_k \log W_k) \le O(\log N) \sum P_k W_k = O(\log N) \cdot O(\log N) $$$ Time: $$$O(\log^2 N)$$$ expected.

Compared to standard query square root decomposition which would work in $$$O(N \sqrt{Q} \log N + Q log ^ 3 N)$$$, our rnd HLD achieves a clean $$$O(Q \log^3 N)$$$ overall with excellent constant factors and avoids any blocking logic!

Thus, rnd HLD is indeed a very useful technique for growing tree problems.

Thank you for reading the post!

How do you usually build HLD?

Usually we calculate $$$sz_v$$$ — size of subtree of $$$v$$$. Then from $$$v$$$ we go to $$$u$$$ with largest $$$sz_u$$$ ($$$u$$$ is child of $$$v$$$). And this is still good way, but today I want to show you something different.

What if from $$$v$$$ we go to the random vertex $$$u$$$ in the whole subtree of $$$v$$$. It is the same as choosing to go to the $$$u$$$ ($$$u$$$ is child of $$$v$$$) with probability $$$\frac{sz_u}{sz_v - 1}$$$, so the probability of edge $$$v, u$$$ to be heavy is $$$\frac{sz_u}{sz_v - 1}$$$. Intuitively we should go the largest subtree.

Proof

Let's proof it works well. For vertex $$$v$$$ the expected value number of light edges on the way to root is $$$\sum_{i = 1}^{i \lt |u|}{1-\frac{sz_{u_i}}{sz_{u_{i + 1}} - 1}}$$$, where $$$u$$$ is vertexes on way from $$$v$$$ to root. Let $$$a_i$$$ be $$$sz_{u_i}$$$. Then $$$a$$$ is an increasing array and we know that $$$a_{h_v}$$$ equals to the size of the whole tree. $$$\sum_{i = 1}^{i \lt |a|}{1-\frac{a_i}{a_{i + 1} - 1}} \leq \sum_{i = 1}^{i \lt |a|}{\frac{a_{i + 1} - a_i}{a_{i + 1}}}$$$.

$$$\frac{a_{i+1} - a_i}{a_{i+1}} \le \int_{a_i}^{a_{i+1}} \frac{1}{x} \, dx = \ln(a_{i+1}) - \ln(a_i)$$$

$$$\sum_{i = 1}^{i \lt |a|}{1-\frac{a_i}{a_{i + 1} - 1}} \leq ln(a_{|a|})$$$.

So we have expected value number of light edges on the way is less than $$$ln(n)$$$.

Usages

remain to the reader

I hope everyone enjoyed the tasks, and thank you for participating.

2110A - Fashionable Array

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> x(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    sort(x.begin(), x.end());
    if (x[0] % 2 == x[n - 1] % 2) {
        cout << 0 << endl;
        return;
    }
    int left = n, right = n;
    for (int i = 1; i < n; ++i) {
        if (x[i] % 2 != x[0] % 2) {
            left = i;
            break;
        }
    }
    for (int i = 1; i < n; ++i) {
        if (x[n - i - 1] % 2 != x[n - 1] % 2) {
            right = i;
            break;
        }
    }
    cout << min(left, right) << '\n';
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

2110B - Down with Brackets

#include "bits/stdc++.h"
#define int long long
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define em emplace_back
#define mp make_pair
#define F first
#define S second

using namespace std;
template<class C>
using vec = vector<C>;
using vi = vector<int>;
using vpi = vector<pair<int, int>>;
using pii = pair<int, int>;

void solve() {
  string s;
  cin >> s;
  int n = s.size();
  int bal = 0;
  for (int i = 1; i + 1 < n; i++) {
    if (s[i] == '(') bal++;
    else bal--;
    if (bal < 0) {
      cout << "YES\n";
      return;
    }
  }
  if (bal == 0) {
    cout << "NO\n";
  } else {
    cout << "YES\n";
  }
}

signed main() {
  int tt;
  cin >> tt;
  while (tt--) {
    solve();
  }
}

2110C - Racing

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> d(n);
    for (auto &x : d) {
        cin >> x;
    }
    vector<int> l(n), r(n);
    for (int i = 0; i < n; ++i) {
        cin >> l[i] >> r[i];
    }
    int left = 0;
    vector<int> last;
    for (int i = 0; i < n; ++i) {
        if (d[i] == -1) {
            last.push_back(i);
        } else {
            left += d[i];
        }
        while (left < l[i]) {
            if (last.empty()) {
                cout << -1 << '\n';
                return;
            }
            d[last.back()] = 1;
            ++left;
            last.pop_back();
        }
        while (left + last.size() > r[i]) {
            if (last.empty()) {
                cout << -1 << '\n';
                return;
            }
            d[last.back()] = 0;
            last.pop_back();
        }
    }
    for (auto &x : d) {
        cout << max(0, x) << " ";
    }
    cout << "\n";
    return;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

2110D - Fewer Batteries

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9 + 11;

struct edge {
    int t, w;
    edge(int t, int w) : t(t), w(w) {}
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> b(n);
    for (auto &x : b) {
        cin >> x;
    }
    vector<vector<edge>> graph(n);
    for (int i = 0; i < m; ++i) {
        int s, t, w;
        cin >> s >> t >> w;
        --s; --t;
        graph[s].push_back(edge(t, w));
    }
    auto check = [&](int maxW) {
        vector<int> best(n, 0);
        for (int i = 0; i < n; ++i) {
            if (i > 0 && best[i] == 0) {
                continue;
            }
            best[i] += b[i];
            best[i] = min(best[i], maxW);
            for (auto p : graph[i]) {
                if (p.w <= best[i]) {
                    best[p.t] = max(best[p.t], best[i]);
                }
            }
        }
        return (best.back() > 0);
    };
    if (!check(INF)) {
        cout << -1 << endl;
        return;
    }
    int l = 0, r = INF;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    cout << r << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

2110E - Melody

#include <bits/stdc++.h>

using namespace std;

vector<set<int>> graph;
vector<int> ans;

void dfs(int v) {
    while (!graph[v].empty()) {
        int u = *graph[v].begin();
        graph[u].erase(v);
        graph[v].erase(u);
        dfs(u);
    }
    ans.push_back(v);
}

signed main() {
    int t;
    cin >> t;
    while (t--) {
        graph.clear();
        ans.clear();
        int n;
        cin >> n;
        map<int, int> p, v;
        map<pair<int, int>, int> toIndex;
        vector<pair<int, int>> part;
        for (int i = 1; i <= n; ++i) {
            int volume, pitch;
            cin >> volume >> pitch;
            toIndex[make_pair(volume, pitch)] = i;
            if (p.count(pitch) == 0) {
                p[pitch] = graph.size();
                graph.push_back(set<int>());
                part.push_back(make_pair(0, pitch));
            }
            if (v.count(volume) == 0) {
                v[volume] = graph.size();
                graph.push_back(set<int>());
                part.push_back(make_pair(volume, 0));
            }
            graph[v[volume]].insert(p[pitch]);
            graph[p[pitch]].insert(v[volume]);
        }
        int root = 0;
        int cnt = 0;
        for (int i = 0; i < graph.size(); ++i) {
            if (graph[i].size() % 2 == 1) {
                ++cnt;
                root = i;
            }
        }
        dfs(root);
        if (ans.size() != n + 1 || cnt > 2) {
            cout << "NO" << endl;
            continue;
        }
        vector<int> out;
        for (int i = 0; i < n; ++i) {
            auto p1 = part[ans[i]];
            auto p2 = part[ans[i + 1]];
            out.push_back(toIndex[make_pair(p1.first + p2.first, p1.second + p2.second)]);
            if (out[i] == 0) {
                out.clear();
                break;
            }
        }
        if (out.empty()) {
            cout << "NO" << endl;
        } else {
            cout << "YES" << endl;
            for (int i = 0; i < n; ++i) {
                cout << out[i] << " ";
            }
            cout << endl;
        }
    }
    return 0;
}

2110F - Faculty

#include <bits/stdc++.h>

using namespace std;

int f(int x, int y) {
    return (x % y) + (y % x);
}

void Solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int ans = 0;
    int mx = a[0];
    for (int i = 0; i < n; ++i) {
        ans = max(ans, f(mx, a[i]));
        if (a[i] > mx) {
            if (a[i] >= mx * 2) {
                mx = a[i];
                for (int j = 0; j < i; ++j) {
                    ans = max(ans, f(a[i], a[j]));
                }
            } else {
                mx = a[i];
                ans = mx;
            }
        }
        cout << ans << ' ';
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        Solve();
    }
    return 0;
}

Hello, codeforces!

We are glad to invite you to Codeforces Round 1026 (Div. 2), which will start at May/24/2025 17:35 (Moscow time). This round will be rated for all participants with a rating below 2100. You will have 2 hours to solve 6 problems. The problems were prepared by XaRDKoDblCH and PvPro.

We would like to thank everyone who made this round possible:

• FairyWinx, for coordinating our round and preparing the problems.

• MikeMirzayanov, KAN for the Codeforces and Polygon systems.

• Our army of testers: N_z__, BurnedChicken, triple__a, makrav, Noobish_Monk, mainyutin, k1r1t0, Nil2007, zhiganov_v, sputn1k, lewc, larionov_kirill, Kmes, Dimozavr, potalov.m, Mega_Plus, larush, mz1.

• All the participants.

Score distribution: 500 — 750 — 1500 — 2000 — 2250 — 3000

Our round will be dedicated to a cyberpunk theme, so get ready to save the world from robots! ;)

Good luck!

UPD: The contest is over! Congrats the winners:

via all participants:

1. maspy

2. Geothermal

3. 9ovem

4. peti1234

5. turmax

via div.2 participants:

1. 9ovem

2. still_still_stellar

3. Hellia

4. Badint

5. cuongaaaa

UPD: Editorial

Hello codeforces!

What is the easiest way to check if there is a perfect matching in the tree?

Maybe Kuhn's algorithm? :)

Most likely you are thinking about dynamics on subtrees. This is indeed a good way, because it works for the size of the input. However, there is an easier way to check if a tree has a perfect matching.

Let $$$sz_v$$$ be the subtree size of the $$$v$$$th vertex. Then I claim that there is a perfect matching iff exactly half of all $$$sz_v$$$ are even.

Proof:

Let $$$sz_{odd}$$$ be the number of odd subtrees, and $$$sz_{even}$$$ be the number of even subtrees.

We first prove that $$$sz_{even} \leq sz_{odd}$$$.

Note that $$$sz_v = \sum_{u}^{} sz_u + 1$$$ ($$$u$$$ — child of $$$v$$$). If $$$sz_v$$$ is even, then at least one of the children of $$$u$$$ has an odd subtree size, because their sum is odd. We pair each even $$$sz_v$$$ with an odd $$$sz_u$$$ ($$$u$$$ — child $$$v$$$). Thus $$$sz_{even} \leq sz_{odd}$$$. Moreover, we proved that if $$$sz_{even} = sz_{odd}$$$, then there is a perfect matchingg in the tree by explicitly choosing every even $$$sz_v$$$ to be a pair.

Now we prove that if $$$sz_{even} \neq sz_{odd}$$$, then there is no perfect matching in the tree. Suppose there is. Then it has an edge connecting $$$v, u$$$ such that $$$sz_v \equiv sz_u \equiv 1\space (mod\space 2)$$$. Let $$$v$$$ — be the parent of $$$u$$$. Then note that each edge is either entirely contained in a subtree of $$$v$$$ or not. In both cases, the edge takes an even number of vertices from subtree $$$v$$$, and hence they will also take an even number of vertices in total, but $$$sz_v \equiv 1\space(mod\space 2)$$$ — contradiction.

Furthermore, because of the inequality $$$sz_{even} \leq sz_{odd}$$$ it is true that $$$sz_{odd} = sz_{even}$$$ is equivalent to the presence of a perfect matching in the forest.

Thanks for reading!