18.2 Поддеревья и пути¶

В этом разделе мы разберём очень важную идею для задач на деревья: как превратить запросы на дереве в запросы на массиве.

Это один из самых полезных приёмов в олимпиадном программировании. После него многие задачи на деревья начинают выглядеть как обычные задачи на отрезки: обновление значения, сумма на отрезке, прибавление на диапазоне, запрос в точке и так далее.

Основная мысль такая:

если выполнить обход дерева в глубину, то вершины каждого поддерева будут идти подряд;
значит, поддерево можно представить отрезком массива;
а некоторые запросы по путям от корня можно свести к операциям над этим же DFS-порядком.

Ниже мы подробно разберём обе идеи.

1. DFS-порядок дерева¶

Пусть дерево укоренено в вершине 1. Выполним обход DFS и будем записывать вершину в массив в момент первого входа в неё.

Рассмотрим дерево:

1
├─ 2
│  └─ 6
├─ 3
├─ 4
│  ├─ 7
│  ├─ 8
│  └─ 9
└─ 5

Если обходить детей слева направо, порядок первого посещения будет таким:

1, 2, 6, 3, 4, 7, 8, 9, 5

Этот массив часто называют:

DFS order,
Euler tour entry order,
traversal array,
массив времени входа.

Для каждой вершины удобно хранить:

tin[v] — позицию вершины в DFS-порядке;
sz[v] — размер её поддерева.

Тогда все вершины поддерева v лежат на непрерывном отрезке:

[ tin[v], tin[v] + sz[v] - 1 ]

Это и есть главный факт раздела.

2. Почему поддерево — это непрерывный отрезок¶

Когда DFS заходит в вершину v, он:

записывает v в массив,
полностью обходит всех потомков v,
только после этого выходит из v.

Значит, пока обход не покинул v, он не может попасть в вершины вне поддерева v.

Следовательно, все вершины поддерева v записываются подряд.

Это очень важное наблюдение, потому что теперь задача

«найти сумму в поддереве вершины v»

превращается в задачу

«найти сумму на отрезке массива».

3. Как построить `tin` и `sz`¶

Во время DFS делаем таймер:

timer = 0

При входе в вершину v:

увеличиваем таймер,
записываем tin[v] = timer,
кладём вершину v в массив DFS-порядка.

После обхода всех детей считаем размер поддерева:

sz[v] = 1 + сумма размеров поддеревьев детей

Код построения DFS-порядка¶

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

vector<int> g[MAXN];
int tin[MAXN], sz[MAXN], order[MAXN];
int timer = 0;

void dfs(int v, int p) {
    tin[v] = timer;
    order[timer] = v;
    timer++;

    sz[v] = 1;
    for (int to : g[v]) {
        if (to == p) continue;
        dfs(to, v);
        sz[v] += sz[to];
    }
}

Здесь используется нумерация массива order с нуля. Тогда поддерево вершины v соответствует отрезку:

[ tin[v], tin[v] + sz[v] - 1 ]

4. Запросы по поддереву¶

Рассмотрим задачу:

изменить значение вершины;
найти сумму значений во всём поддереве вершины.

Пусть у каждой вершины есть значение val[v].

После DFS построим массив a, где:

a[tin[v]] = val[v]

Тогда сумма по поддереву v станет суммой по отрезку:

sum( tin[v], tin[v] + sz[v] - 1 )

То есть нам нужна структура данных, которая умеет:

менять один элемент;
находить сумму на отрезке.

Подойдут:

дерево Фенвика,
дерево отрезков.

5. Решение запросов по поддереву через Fenwick¶

Дерево Фенвика особенно удобно, если запрос — это сумма на отрезке и обновление в одной точке.

Идея¶

Делаем DFS.
Переносим значения вершин в массив по времени входа.
Храним этот массив в Fenwick Tree.
Сумму поддерева получаем как сумму на отрезке.

Полный код на C++¶

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int n, q;
vector<int> g[MAXN];
int tin[MAXN], sz[MAXN], timer;
long long val[MAXN];

struct Fenwick {
    int n;
    vector<long long> bit;

    Fenwick() {}
    Fenwick(int n) : n(n), bit(n + 1, 0) {}

    void add(int idx, long long delta) {
        idx++;
        while (idx <= n) {
            bit[idx] += delta;
            idx += idx & -idx;
        }
    }

    long long sumPrefix(int idx) {
        idx++;
        long long res = 0;
        while (idx > 0) {
            res += bit[idx];
            idx -= idx & -idx;
        }
        return res;
    }

    long long sumRange(int l, int r) {
        if (l > r) return 0;
        return sumPrefix(r) - (l ? sumPrefix(l - 1) : 0);
    }
} fw;

void dfs(int v, int p) {
    tin[v] = timer++;
    sz[v] = 1;
    for (int to : g[v]) {
        if (to == p) continue;
        dfs(to, v);
        sz[v] += sz[to];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    for (int v = 1; v <= n; v++) cin >> val[v];

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    timer = 0;
    dfs(1, 0);

    fw = Fenwick(n);
    for (int v = 1; v <= n; v++) {
        fw.add(tin[v], val[v]);
    }

    while (q--) {
        int type;
        cin >> type;

        if (type == 1) {
            int v;
            long long x;
            cin >> v >> x;
            long long delta = x - val[v];
            val[v] = x;
            fw.add(tin[v], delta);
        } else {
            int v;
            cin >> v;
            int l = tin[v];
            int r = tin[v] + sz[v] - 1;
            cout << fw.sumRange(l, r) << '\n';
        }
    }
}

Формат запросов в этом примере¶

1 v x — присвоить вершине v новое значение x;
2 v — вывести сумму в поддереве вершины v.

Сложность¶

DFS-подготовка: O(n)
каждый запрос: O(log n)

6. Небольшой пример для поддерева¶

Пусть дерево такое:

1
├─ 2
│  └─ 6
├─ 3
├─ 4
│  ├─ 7
│  ├─ 8
│  └─ 9
└─ 5

Пусть значения вершин:

val[1]=2
val[2]=3
val[3]=5
val[4]=3
val[5]=1
val[6]=4
val[7]=4
val[8]=3
val[9]=1

DFS-порядок:

1, 2, 6, 3, 4, 7, 8, 9, 5

Тогда массив значений в DFS-порядке:

2, 3, 4, 5, 3, 4, 3, 1, 1

Поддерево вершины 4 — это вершины:

4, 7, 8, 9

В массиве это непрерывный отрезок:

3, 4, 3, 1

Сумма равна:

Именно поэтому подход работает.

7. Запросы по пути от корня до вершины¶

Теперь рассмотрим другую задачу:

изменить значение вершины;
найти сумму на пути от корня до вершины v.

На первый взгляд это уже не похоже на запрос по отрезку. Но здесь есть очень красивая идея.

Наблюдение¶

Пусть path[v] — сумма значений на пути от корня до v.

Если значение вершины u увеличилось на x, то:

сумма пути увеличится на x для всех вершин из поддерева u;
для остальных вершин ничего не изменится.

Почему?

Потому что путь от корня к вершине v проходит через u тогда и только тогда, когда v лежит в поддереве u.

А поддерево u — это отрезок DFS-порядка.

Значит, изменение одной вершины превращается в:

прибавление x ко всему отрезку поддерева.

А запрос суммы пути до вершины v превращается в:

получение значения в одной точке tin[v].

Итак, задача свелась к другой классической постановке:

range add
point query

8. Как это устроено¶

Пусть мы заранее посчитали:

path[v] = path[parent[v]] + val[v]

И записали эти суммы в массив по DFS-порядку:

base[tin[v]] = path[v]

Если вершина u изменилась на delta, то надо сделать:

прибавить delta ко всем base[tin[x]], где x лежит в поддереве u

То есть:

add delta на отрезке [ tin[u], tin[u] + sz[u] - 1 ]

После этого значение в точке tin[v] снова будет равно сумме на пути от корня до v.

9. Реализация через Fenwick: range add + point query¶

Для этого удобно использовать разностный подход.

Если нужно прибавить x на отрезке [l, r], то в Fenwick можно сделать:

add(l, x)
add(r+1, -x)

Тогда значение в точке pos равно префиксной сумме до pos.

Полный код на C++¶

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int n, q;
vector<int> g[MAXN];
int tin[MAXN], sz[MAXN], timer;
long long val[MAXN];
long long pathSum[MAXN];

struct Fenwick {
    int n;
    vector<long long> bit;

    Fenwick() {}
    Fenwick(int n) : n(n), bit(n + 1, 0) {}

    void add(int idx, long long delta) {
        idx++;
        while (idx <= n) {
            bit[idx] += delta;
            idx += idx & -idx;
        }
    }

    long long sumPrefix(int idx) {
        idx++;
        long long res = 0;
        while (idx > 0) {
            res += bit[idx];
            idx -= idx & -idx;
        }
        return res;
    }
} fw;

void dfs(int v, int p, long long cur) {
    tin[v] = timer++;
    pathSum[v] = cur + val[v];
    sz[v] = 1;

    for (int to : g[v]) {
        if (to == p) continue;
        dfs(to, v, pathSum[v]);
        sz[v] += sz[to];
    }
}

void rangeAdd(int l, int r, long long x) {
    fw.add(l, x);
    if (r + 1 < n) fw.add(r + 1, -x);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    for (int v = 1; v <= n; v++) cin >> val[v];

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    timer = 0;
    dfs(1, 0, 0);

    fw = Fenwick(n);

    for (int v = 1; v <= n; v++) {
        rangeAdd(tin[v], tin[v], pathSum[v]);
    }

    while (q--) {
        int type;
        cin >> type;

        if (type == 1) {
            int v;
            long long x;
            cin >> v >> x;
            long long delta = x - val[v];
            val[v] = x;
            int l = tin[v];
            int r = tin[v] + sz[v] - 1;
            rangeAdd(l, r, delta);
        } else {
            int v;
            cin >> v;
            cout << fw.sumPrefix(tin[v]) << '\n';
        }
    }
}

Формат запросов в этом примере¶

1 v x — изменить значение вершины v на x;
2 v — вывести сумму на пути от корня до вершины v.

Сложность¶

подготовка: O(n)
каждый запрос: O(log n)

10. Пример для путей от корня¶

Пусть дерево такое:

1
├─ 2
│  └─ 6
├─ 3
├─ 4
│  ├─ 7
│  ├─ 8
│  └─ 9
└─ 5

Пусть значения:

val[1]=4
val[2]=5
val[3]=3
val[4]=5
val[5]=2
val[6]=3
val[7]=5
val[8]=3
val[9]=1

Тогда:

сумма на пути к 7 равна 4 + 5 + 5 = 14, если путь идёт через вершины 1 -> 4 -> 7;
сумма на пути к 8 равна 4 + 5 + 3 = 12;
сумма на пути к 9 равна 4 + 5 + 1 = 10.

Если увеличить значение вершины 4 на 1, то увеличатся суммы ко всем вершинам её поддерева:

для 4,
для 7,
для 8,
для 9.

Именно это и делает range add по отрезку поддерева вершины 4.

11. Что именно нужно запомнить¶

В этом разделе есть две опорные идеи.

Идея 1. Поддерево = отрезок¶

Если вершина записывается в DFS-порядок при первом входе, то её поддерево — это непрерывный отрезок.

Это позволяет переводить:

сумма по поддереву,
минимум по поддереву,
количество отмеченных вершин в поддереве,
прибавление ко всему поддереву

в обычные запросы по массиву.

Идея 2. Изменение вершины влияет на все пути через неё¶

Если спрашивают суммы на пути от корня до вершины, то изменение вершины u влияет на все вершины её поддерева.

Поэтому:

обновление вершины превращается в обновление отрезка поддерева;
ответ для вершины получается запросом в одной точке.

12. Где это применяется¶

Эти идеи регулярно встречаются в задачах такого вида:

сумма значений в поддереве;
количество чёрных вершин в поддереве;
прибавить число всем вершинам поддерева;
найти значение в вершине после серии обновлений по поддеревьям;
сумма на пути от корня;
количество активных предков вершины.

Это также база для более продвинутых тем:

LCA,
heavy-light decomposition,
Euler tour technique,
offline-запросы на деревьях,
segment tree на дереве.

13. Типичные ошибки¶

Ошибка 1. Перепутать, когда вершина записывается в массив¶

В этой технике обычно вершина записывается один раз — в момент входа.

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

Ошибка 2. Неверно посчитать размер поддерева¶

Нужно помнить:

sz[v] = 1 + сумма sz[child]

Ошибка 3. Ошибка в границах отрезка¶

Поддерево вершины v — это:

[ tin[v], tin[v] + sz[v] - 1 ]

Очень часто забывают -1.

Ошибка 4. Смешать два разных типа запросов¶

для поддеревьев обычно нужен point update + range query;
для путей от корня обычно нужен range update + point query.

Это похожие идеи, но структуры используются по-разному.

14. Минимальный шаблон, который стоит помнить¶

Для суммы в поддереве¶

DFS считаем tin, sz.
В массив a[tin[v]] кладём val[v].
Ответ для v:

sum( tin[v], tin[v] + sz[v] - 1 )

Для суммы на пути от корня¶

DFS считаем tin, sz, path[v].
В массив по времени входа кладём path[v].
При изменении v на delta:

add delta на всём отрезке поддерева v

Ответ для вершины u:

значение в точке tin[u]

15. Дополнение: как перейти к запросам по произвольному пути¶

В этой секции речь идёт только о путях от корня до вершины. Для произвольного пути между двумя вершинами этого уже недостаточно.

Там обычно нужны:

LCA,
heavy-light decomposition,
иногда двоичные подъёмы,
иногда префиксные суммы по глубине.

Но понимание текущего раздела — это обязательная база перед этими темами.

16. Краткий итог¶

Раздел «Subtrees and paths» учит двум фундаментальным преобразованиям:

поддерево вершины превращается в отрезок массива;
обновление вершины для запросов вида «путь от корня» превращается в обновление всего поддерева.

Именно благодаря этому дерево можно обрабатывать стандартными структурами данных для массивов.

Если сформулировать совсем коротко:

DFS нумерация выпрямляет дерево;
Fenwick или segment tree отвечают на запросы уже на массиве.

18.2 Поддеревья и пути¶

1. DFS-порядок дерева¶

2. Почему поддерево — это непрерывный отрезок¶

3. Как построить tin и sz¶

Код построения DFS-порядка¶

4. Запросы по поддереву¶

5. Решение запросов по поддереву через Fenwick¶

Идея¶

Полный код на C++¶

Формат запросов в этом примере¶

Сложность¶

6. Небольшой пример для поддерева¶

7. Запросы по пути от корня до вершины¶

Наблюдение¶

8. Как это устроено¶

9. Реализация через Fenwick: range add + point query¶

Полный код на C++¶

Формат запросов в этом примере¶

Сложность¶

10. Пример для путей от корня¶

11. Что именно нужно запомнить¶

Идея 1. Поддерево = отрезок¶

Идея 2. Изменение вершины влияет на все пути через неё¶

12. Где это применяется¶

13. Типичные ошибки¶

Ошибка 1. Перепутать, когда вершина записывается в массив¶

Ошибка 2. Неверно посчитать размер поддерева¶

Ошибка 3. Ошибка в границах отрезка¶

Ошибка 4. Смешать два разных типа запросов¶

14. Минимальный шаблон, который стоит помнить¶

Для суммы в поддереве¶

Для суммы на пути от корня¶

15. Дополнение: как перейти к запросам по произвольному пути¶

16. Краткий итог¶

3. Как построить `tin` и `sz`¶