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

Надеюсь, задания всем понравились, и спасибо за участие.

2110A - Модный массив

#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 - Долой скобки

#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 - Гонки

#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 - Меньше батареек

#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 - Мелодия

#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 - Факультет

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

Привет, Codeforces!

Мы рады пригласить Вас на Codeforces Round 1026 (Div. 2), который состоится 24.05.2025 17:35 (Московское время). Этот раунд будет рейтинговым для всех участников с рейтингом меньше 2100. У вас будет 2 часа для решения 6 задач. Задачи были подготовлены XaRDKoDblCH и PvPro.

Мы хотели бы поблагодарить всех, кто сделал этот раунд возможным:

• FairyWinx, за координирование нашего раунда и подготовкой задач.

• MikeMirzayanov, KAN за системы Codeforces и Polygon.

• Нашу армию тестеров: 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.

• Всех участников

Разбалловка: 500 — 750 — 1500 — 2000 — 2250 — 3000

Наш раунд будет посвящен cyberpunk-тематике, поэтому приготовьтесь спасать мир от роботов! ;)

Удачи!

UPD: Контест закончился, поздравляем победителей!

среди всех участников:

1. maspy

2. Geothermal

3. 9ovem

4. peti1234

5. turmax

среди div.2 участников:

1. 9ovem

2. still_still_stellar

3. Hellia

4. Badint

5. cuongaaaa

UPD: Разбор

Привет codeforces!

Какой самый простой способ проверить есть ли в дереве совершенное паросочетание?

Может быть алгоритм Куна? :)

Скорее всго вы подумали про динамику по поддеревьям. Действительно это хороший способ, ведь он работает за размер ввода. Однако есть более простой способ проверить имеет ли дерево полное паросочетание.

Пусть $$$sz_v$$$ — размер поддерева $$$v$$$-й вершины. Тогда я утверждаю, что совершенное паросочетание есть тогда и только тогда, когда ровно половина всех $$$sz_v$$$ четная.

Доказательство:

Пусть $$$sz_{odd}$$$ — количество нечетных поддеревьев, а $$$sz_{even}$$$ — количетво четных поддеревьев.

Сначала докажем, что $$$sz_{even} \leq sz_{odd}$$$.

Заметим, что $$$sz_v = \sum_{u}^{} sz_u + 1$$$ ($$$u$$$ — ребенок $$$v$$$). Если $$$sz_v$$$ четно, то хотя-бы один из детей $$$u$$$ имеет нечетный размер поддерева, потому что их сумма нечетная. Сопоставим в пару каждому четному $$$sz_v$$$ нечетное $$$sz_u$$$ ($$$u$$$ — ребенок $$$v$$$). Таким образом $$$sz_{even} \leq sz_{odd}$$$. Более того, мы доказали, что если $$$sz_{even} = sz_{odd}$$$, то в дереве есть совершенное паросочетание, явно выбрав каждому четному $$$sz_v$$$ пару.

Теперь докажем, что если $$$sz_{even} \neq sz_{odd}$$$, то в дереве нет полного паросочетания. Допустим есть. Тогда в нем есть ребро, соединяющее $$$v, u$$$, такие что $$$sz_v \equiv sz_u \equiv 1\space (mod\space 2)$$$. Пусть $$$v$$$ — родитель $$$u$$$. Тогда заметим, что каждое ребро либо целиком содержится в поддереве $$$v$$$, либо нет. В обоих случаях ребро забирает из поддерева $$$v$$$ четное количество вершин, а значит и суммарно они заберут четное количество вершин, но $$$sz_v \equiv 1\space(mod\space 2)$$$ — противоречие.

Более того из-за неравенства $$$sz_{even} \leq sz_{odd}$$$ верно, что $$$sz_{odd} = sz_{even}$$$ равносильно наличию полного паросочетания в лесе.

Спасибо за прочтение!