Los árboles de centroides dinámicos, también conocidos como Dynamic Centroid Decomposition Trees, son una estructura de datos utilizada para resolver problemas de caminos en árboles con modificaciones en los pesos. A diferencia del algoritmo de descomposición de centroides estático, este enfoque permite actualizaciones eficientes en los pesos de los nodos.

Construcción del Árbol de Centroides Dinámico

La idea principle es conectar los centroides de subárboles adyacentes. Este nuevo árbol se denomina árbol de centroides dinámico. La construcción se realiza de manera similar a la descomposición de centroides, pero añadiendo aristas entre los centroides encontrados.

void construirCentroide(int u) {
    visitado[u] = true;
    for (int v : adyacencias[u]) {
        if (!visitado[v]) {
            obtenerCentroide(v, 0, raiz = 0);
            padre[raiz] = u;
            construirCentroide(raiz);
        }
    }
}

Propiedades del Árbol de Centroides Dinámico

• La altura del árbol de centroides dinámico es \(\mathcal{O}(\log n)\).
• El grado de cada nodo en el árbol de centroides dinámico no supera su grado en el árbol original.
• La suma de los tamaños de los subárboles en el árbol de centroides dinámico es \(\mathcal{O}(n \log n)\).
• El LCA ( ancestro común más lejano ) en el árbol de centroides dinámico siempre está en el camino del árbol original.

Ejemplos de Problemas

Ejemplo 1: Plantilla de Árbol de Centroides Dinámico

Dado un árbol con pesos en los nodos, realizar operaciones de modificación y consulta de sumas de pesos en rangos de distancia.

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

const int maxn = 1e5 + 5;
int n, m, u, v, op, rt, all, res;
int d[maxn], fa[maxn], son[maxn], top[maxn];
int p[maxn], mx[maxn], sz[maxn];
bool vis[maxn];
vector<int> g[maxn];
int w[maxn];

struct SegmentTree {
    int tot, rt[maxn];
    struct node {
        int ls, rs, sum;
    } f[40 * maxn];

    void pushup(int p) {
        f[p].sum = f[f[p].ls].sum + f[f[p].rs].sum;
    }

    void modify(int &p, int l, int r, int pos, int val) {
        if (!p) p = ++tot;
        if (l == r) return f[p].sum += val, void();
        int mid = (l + r) / 2;
        if (pos <= mid) modify(f[p].ls, l, mid, pos, val);
        else modify(f[p].rs, mid + 1, r, pos, val);
        pushup(p);
    }

    int query(int p, int l, int r, int L, int R) {
        if (L <= l && r <= R) return f[p].sum;
        if (!p || l > R || r < L) return 0;
        int mid = (l + r) / 2;
        return query(f[p].ls, l, mid, L, R) + query(f[p].rs, mid + 1, r, L, R);
    }
} t1, t2;

void dfs1(int u, int father) {
    sz[u] = 1;
    for (auto v : g[u]) {
        if (v == father) continue;
        d[v] = d[u] + 1, fa[v] = u;
        dfs1(v, u), sz[u] += sz[v];
        if (sz[v] >= sz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int topf) {
    top[u] = topf;
    if (son[u]) dfs2(son[u], topf);
    for (auto v : g[u]) {
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (d[top[u]] < d[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return d[u] < d[v] ? u : v;
}

int getdis(int u, int v) {
    return d[u] + d[v] - 2 * d[lca(u, v)];
}

void getroot(int u, int fa) {
    sz[u] = 1, mx[u] = 0;
    for (auto v : g[u]) {
        if (vis[v] || v == fa) continue;
        getroot(v, u);
        sz[u] += sz[v], mx[u] = max(mx[u], sz[v]);
    }
    mx[u] = max(mx[u], all - sz[u]);
    if (mx[u] < mx[rt]) rt = u;
}

void solve(int u) {
    vis[u] = true;
    for (auto v : g[u]) {
        if (vis[v]) continue;
        all = sz[v], getroot(v, rt = 0), p[rt] = u, solve(rt);
    }
}

void modify(int x, int y) {
    for (int cur = x; cur; cur = p[cur]) {
        t1.modify(t1.rt[cur], 0, n, getdis(x, cur), y);
        if (p[cur]) t2.modify(t2.rt[cur], 0, n, getdis(x, p[cur]), y);
    }
}

int query(int x, int k) {
    int res = 0;
    for (int cur = x; cur; cur = p[cur]) {
        res += t1.query(t1.rt[cur], 0, n, 0, k - getdis(x, cur));
        if (p[cur]) res -= t2.query(t2.rt[cur], 0, n, 0, k - getdis(x, p[cur]));
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m), mx[0] = 1e9;
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    for (int i = 1; i <= n - 1; i++) {
        scanf("%d%d", &u, &v);
        g[u].push_back(v), g[v].push_back(u);
    }
    d[1] = 1, dfs1(1, 0), dfs2(1, 1);
    all = n, getroot(1, 0), solve(rt);
    for (int i = 1; i <= n; i++) modify(i, w[i]);
    while (m--) {
        scanf("%d%d%d", &op, &u, &v), u ^= res, v ^= res;
        if (!op) printf("%d\n", res = query(u, v));
        else modify(u, v - w[u]), w[u] = v;
    }
    return 0;
}
</int>

Ejemplo 2: Juego de Escondite

Dado un árbol con nodos de dos colores, realizar operaciones de cambio de color y consultas de la máxima distancia entre dos nodos de un color específico.

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

const int maxn = 1e5 + 5, inf = 1e9;
int n, q, u, v, rt, all, sum;
int d[maxn], fa[maxn], son[maxn], top[maxn];
int p[maxn], mx[maxn], sz[maxn];
bool vis[maxn];
vector<int> g[maxn];
int w[maxn];
char ch[2];

struct PriorityQueue {
    priority_queue<int> q1, q2;

    void clean() {
        while (q1.size() && q2.size() && q1.top() == q2.top()) q1.pop(), q2.pop();
    }

    int size() {
        return q1.size() - q2.size();
    }

    void push(int x) {
        q1.push(x), clean();
    }

    void del(int x) {
        q2.push(x), clean();
    }

    int top() {
        return q1.size() ? q1.top() : -inf;
    }

    int query() {
        static int x, y;
        x = top(), del(x);
        y = top(), push(x);
        return x + y;
    }
} a[maxn], b[maxn], c;

void dfs1(int u, int father) {
    sz[u] = 1;
    for (auto v : g[u]) {
        if (v == father) continue;
        d[v] = d[u] + 1, fa[v] = u;
        dfs1(v, u), sz[u] += sz[v];
        if (sz[v] >= sz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int topf) {
    top[u] = topf;
    if (son[u]) dfs2(son[u], topf);
    for (auto v : g[u]) {
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (d[top[u]] < d[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return d[u] < d[v] ? u : v;
}

int getdis(int u, int v) {
    return d[u] + d[v] - 2 * d[lca(u, v)];
}

void getroot(int u, int fa) {
    sz[u] = 1, mx[u] = 0;
    for (auto v : g[u]) {
        if (vis[v] || v == fa) continue;
        getroot(v, u);
        sz[u] += sz[v], mx[u] = max(mx[u], sz[v]);
    }
    mx[u] = max(mx[u], all - sz[u]);
    if (mx[u] < mx[rt]) rt = u;
}

void solve(int u) {
    vis[u] = true;
    for (auto v : g[u]) {
        if (vis[v]) continue;
        all = sz[v], getroot(v, rt = 0), p[rt] = u, solve(rt);
    }
}

void add(int x) {
    c.del(b[x].query());
    b[x].push(0);
    c.push(b[x].query());
    for (int i = x; p[i]; i = p[i]) {
        c.del(b[p[i]].query());
        b[p[i]].del(a[i].top());
        a[i].push(getdis(x, p[i]));
        b[p[i]].push(a[i].top());
        c.push(b[p[i]].query());
    }
}

void del(int x) {
    c.del(b[x].query());
    b[x].del(0);
    c.push(b[x].query());
    for (int i = x; p[i]; i = p[i]) {
        c.del(b[p[i]].query());
        b[p[i]].del(a[i].top());
        a[i].del(getdis(x, p[i]));
        b[p[i]].push(a[i].top());
        c.push(b[p[i]].query());
    }
}

int main() {
    scanf("%d", &n), mx[0] = inf;
    for (int i = 1; i <= n - 1; i++) {
        scanf("%d%d", &u, &v);
        g[u].push_back(v), g[v].push_back(u);
    }
    d[1] = 1, dfs1(1, 0), dfs2(1, 1);
    all = n, getroot(1, 0), solve(rt);
    for (int x = 1; x <= n; x++) {
        w[x] = 1, b[x].push(0);
        for (int i = x; i; i = p[i]) a[i].push(getdis(x, p[i]));
    }
    for (int i = 1; i <= n; i++) b[p[i]].push(a[i].top());
    for (int i = 1; i <= n; i++) c.push(b[i].query());
    scanf("%d", &q), sum = n;
    while (q--) {
        scanf("%s", ch);
        if (ch[0] == 'C') {
            scanf("%d", &u), sum += w[u] ? -1 : 1, w[u] ^= 1;
            w[u] ? add(u) : del(u);
        } else
            printf("%d\n", sum >= 2 ? c.top() : sum - 1);
    }
    return 0;
}
</int></int>

Ejemplo 3: Juego Estratégico de Fantasía

Dado un árbol con pesos en los nodos y en las aristas, realizar operaciones de modificación en los pesos de los nodos y calcular el mínimo de la suma ponderada de distancias.

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pii pair<int int="">
using namespace std;

const int maxn = 1e5 + 5;
int n, q, u, v, w, x, rt, all;
int c[maxn], d[maxn], fa[maxn], sz[maxn], son[maxn], top[maxn];
int p[maxn], mx[maxn];
bool vis[maxn];
vector<pii> g[maxn], h[maxn];
ll s1[maxn], s2[maxn], s3[maxn];

void dfs1(int u, int f) {
    sz[u] = 1;
    for (auto [v, w] : g[u]) {
        if (v == f) continue;
        c[v] = c[u] + w, d[v] = d[u] + 1, fa[v] = u, dfs1(v, u), sz[u] += sz[v];
        if (sz[v] >= sz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int f) {
    top[u] = f;
    if (son[u]) dfs2(son[u], f);
    for (auto [v, w] : g[u]) {
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (d[top[u]] < d[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return d[u] < d[v] ? u : v;
}

int getdis(int u, int v) {
    return c[u] + c[v] - 2 * c[lca(u, v)];
}

void getroot(int u, int fa) {
    sz[u] = 1, mx[u] = 0;
    for (auto [v, w] : g[u]) {
        if (vis[v] || v == fa) continue;
        getroot(v, u), sz[u] += sz[v], mx[u] = max(mx[u], sz[v]);
    }
    mx[u] = max(mx[u], all - sz[u]);
    if (!rt || mx[u] < mx[rt]) rt = u;
}

void solve(int u) {
    vis[u] = 1;
    for (auto [v, w] : g[u]) {
        if (vis[v]) continue;
        all = sz[v], getroot(v, rt = 0), p[rt] = u, h[u].push_back(mp(v, rt)), solve(rt);
    }
}

void modify(int u, int e) {
    for (int i = u; i; i = p[i]) {
        s1[i] += e, s2[i] += 1LL * getdis(u, i) * e;
        if (p[i]) s3[i] += 1LL * getdis(u, p[i]) * e;
    }
}

ll calc(int u) {
    ll res = 0;
    for (int i = u; i; i = p[i]) {
        res += s1[i] * getdis(u, i) + s2[i];
        if (p[i]) res -= s1[i] * getdis(u, p[i]) + s3[i];
    }
    return res;
}

ll query(int u) {
    ll res = calc(u);
    for (auto [v, w] : h[u]) if (calc(v) < res) return query(w);
    return res;
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n - 1; i++) {
        scanf("%d%d%d", &u, &v, &w);
        g[u].push_back(mp(v, w)), g[v].push_back(mp(u, w));
    }
    d[1] = 1, dfs1(1, 0), dfs2(1, 1);
    all = n, getroot(1, 0), solve(x = rt);
    while (q--) scanf("%d%d", &u, &w), modify(u, w), printf("%lld\n", query(x));
    return 0;
}
</pii></int>

Ejemplo 4: Problema de Estructuras de Datos Frescas

Dado un árbol con pesos en los nodos, realizar operaciones de modificación y consulta de la suma de cuadrados de las sumas de subárboles.

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

const int maxn = 2e5 + 5;
int n, q, u, v, op, rt, all;
ll cur, sum;
int d[maxn], fa[maxn], son[maxn], top[maxn];
int p[maxn], mx[maxn], sz[maxn];
bool vis[maxn];
vector<int> g[maxn];
int w[maxn];
ll s[maxn], s1[maxn], s2[maxn], s3[maxn];

void dfs1(int u, int father) {
    sz[u] = 1, s[u] = w[u];
    for (auto v : g[u]) {
        if (v == father) continue;
        d[v] = d[u] + 1, fa[v] = u;
        dfs1(v, u), sz[u] += sz[v], s[u] += s[v];
        if (sz[v] >= sz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int topf) {
    top[u] = topf;
    if (son[u]) dfs2(son[u], topf);
    for (auto v : g[u]) {
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (d[top[u]] < d[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return d[u] < d[v] ? u : v;
}

int getdis(int u, int v) {
    return d[u] + d[v] - 2 * d[lca(u, v)];
}

void getroot(int u, int fa) {
    sz[u] = 1, mx[u] = 0;
    for (auto v : g[u]) {
        if (vis[v] || v == fa) continue;
        getroot(v, u);
        sz[u] += sz[v], mx[u] = max(mx[u], sz[v]);
    }
    mx[u] = max(mx[u], all - sz[u]);
    if (mx[u] < mx[rt]) rt = u;
}

void solve(int u) {
    vis[u] = true;
    for (auto v : g[u]) {
        if (vis[v]) continue;
        all = sz[v], getroot(v, rt = 0), p[rt] = u, solve(rt);
    }
}

ll calc(int x) {
    ll res = 0;
    for (int i = x; i; i = p[i]) {
        res += s1[i] * getdis(x, i) + s2[i];
        if (p[i]) res -= s1[i] * getdis(x, p[i]) + s3[i];
    }
    return res;
}

void modify(int x, int y) {
    sum += y, cur += y * calc(x);
    for (int i = x; i; i = p[i]) {
        s1[i] += y, s2[i] += y * getdis(x, i);
        if (p[i]) s3[i] += y * getdis(x, p[i]);
    }
}

int main() {
    scanf("%d%d", &n, &q), mx[0] = 1e9;
    for (int i = 1; i <= n - 1; i++) {
        scanf("%d%d", &u, &v);
        g[u].push_back(v), g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    d[1] = 1, dfs1(1, 0), dfs2(1, 1);
    all = n, getroot(1, 0), solve(rt);
    sum = s[1];
    for (int x = 1; x <= n; x++) {
        cur += s[x] * (sum - s[x]);
        for (int i = x; i; i = p[i]) {
            s1[i] += w[x], s2[i] += w[x] * getdis(x, i);
            if (p[i]) s3[i] += w[x] * getdis(x, p[i]);
        }
    }
    while (q--) {
        scanf("%d", &op);
        if (op == 1) scanf("%d%d", &u, &v), modify(u, v - w[u]), w[u] = v;
        else scanf("%d", &u), printf("%lld\n", sum * (calc(u) + sum) - cur);
    }
    return 0;
}
</int>

Ejemplo 5: Apertura de Tiendas

Dado un árbol con pesos en los nodos y en las aristas, realizar consultas de la suma de distancias a nodos dentro de un rango de pesos, con restricciones en línea.

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

const int maxn = 1.5e5 + 5, maxm = 3e5 + 5;
int l, n, q, r, u, v, w, rt, all, lim, tot = 1;
ll res;
int head[maxn], to[maxm], val[maxm], nxt[maxm];
int x[maxn];
int d[maxn], fa[maxn], dis[maxn], son[maxn], top[maxn];
int p[maxn], mx[maxn], sz[maxn];
bool vis[maxn];

struct node {
    int x;
    ll dis[2];
};

bool operator<(const node &a, const node &b) {
    return a.x < b.x;
}

struct vec {
    vector<node> h;

    void init() {
        sort(h.begin() + 1, h.end());
        for (int i = 1; i < h.size(); i++)
            for (int j = 0; j <= 1; j++)
                h[i].dis[j] += h[i - 1].dis[j];
    }

    ll query(int op, int l, int r) {
        l = lower_bound(h.begin() + 1, h.end(), (node){l, 0, 0}) - h.begin();
        r = upper_bound(h.begin() + 1, h.end(), (node){r, 0, 0}) - h.begin() - 1;
        if (op == -1) return r - l + 1;
        else return h[r].dis[op] - h[l - 1].dis[op];
    }
} t[maxn];

void addedge(int u, int v, int w) {
    nxt[++tot] = head[u], to[tot] = v, val[tot] = w, head[u] = tot;
}

void dfs1(int u, int father) {
    sz[u] = 1;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i], w = val[i];
        if (v == father) continue;
        d[v] = d[u] + 1, dis[v] = dis[u] + w, fa[v] = u;
        dfs1(v, u), sz[u] += sz[v];
        if (sz[v] >= sz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int topf) {
    top[u] = topf;
    if (son[u]) dfs2(son[u], topf);
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (d[top[u]] < d[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return d[u] < d[v] ? u : v;
}

int getdis(int u, int v) {
    return dis[u] + dis[v] - 2 * dis[lca(u, v)];
}

void getroot(int u, int fa) {
    sz[u] = 1, mx[u] = 0;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (vis[v] || v == fa) continue;
        getroot(v, u);
        sz[u] += sz[v], mx[u] = max(mx[u], sz[v]);
    }
    mx[u] = max(mx[u], all - sz[u]);
    if (mx[u] < mx[rt]) rt = u;
}

void solve(int u) {
    vis[u] = true;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (vis[v]) continue;
        all = sz[v], getroot(v, rt = 0), p[rt] = u, solve(rt);
    }
}

int main() {
    scanf("%d%d%d", &n, &q, &lim), mx[0] = 1e9;
    for (int i = 1; i <= n; i++) scanf("%d", &x[i]);
    for (int i = 1; i <= n - 1; i++) {
        scanf("%d%d%d", &u, &v, &w);
        addedge(u, v, w), addedge(v, u, w);
    }
    d[1] = 1, dfs1(1, 0), dfs2(1, 1);
    all = n, getroot(1, 0), solve(rt);
    for (int i = 1; i <= n; i++) t[i].h.push_back({0, 0, 0});
    for (int u = 1; u <= n; u++)
        for (int i = u; i; i = p[i])
            t[i].h.push_back({x[u], getdis(u, i), getdis(u, p[i])});
    for (int i = 1; i <= n; i++) t[i].init();
    while (q--) {
        scanf("%d%d%d", &u, &l, &r), l = (l + res) % lim, r = (r + res) % lim, res = 0;
        if (l > r) swap(l, r);
        for (int i = u; i; i = p[i]) {
            ll cnt = t[i].query(-1, l, r);
            res += cnt * getdis(u, i) + t[i].query(0, l, r);
            if (p[i]) res -= cnt * getdis(u, p[i]) + t[i].query(1, l, r);
        }
        printf("%lld\n", res);
    }
    return 0;
}
</node>

Ejemplo 6: Instituto Chengdu No. 7

Dado un árbol con colores en los nodos, realizar consultas sobre la cantidad de colores únicos en subárboles definidos por rangos de nodos.

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

const int maxn = 1e5 + 5, lim = 1e5, inf = 1e9;
int l, m, n, r, u, v, rt, all;
int mx[maxn], sz[maxn];
int c[maxn], col[maxn], pos[maxn], res[maxn];
bool vis[maxn];
vector<int> g[maxn];

struct node {
    int l, r, id;
};

vector<node> h[maxn];

struct oper {
    int l, r, x, op;
    /// op=0, insertar un punto de color x en (l, r)
    /// op=1, consultar la cantidad de colores en (l, r), con índice x
};

vector<oper> vec[maxn];

bool cmp(oper a, oper b) {
    if (a.l != b.l) return a.l > b.l;
    return a.op < b.op;
}

void getroot(int u, int fa) {
    sz[u] = 1, mx[u] = 0;
    for (auto v : g[u]) {
        if (vis[v] || v == fa) continue;
        getroot(v, u);
        sz[u] += sz[v], mx[u] = max(mx[u], sz[v]);
    }
    mx[u] = max(mx[u], all - sz[u]);
    if (mx[u] < mx[rt]) rt = u;
}

void dfs(int u, int fa, int l, int r, int rt) {
    h[u].push_back({l, r, rt});
    vec[rt].push_back({l, r, col[u], 0});
    for (auto v : g[u]) {
        if (vis[v] || v == fa) continue;
        dfs(v, u, min(l, v), max(r, v), rt);
    }
}

void solve(int u) {
    vis[u] = true, dfs(u, 0, u, u, u);
    for (auto v : g[u]) {
        if (vis[v]) continue;
        all = sz[v], getroot(v, rt = 0), solve(rt);
    }
}

void add(int x, int v) {
    while (x <= lim) c[x] += v, x += x & (-x);
}

int sum(int x) {
    int res = 0;
    while (x) res += c[x], x -= x & (-x);
    return res;
}

int main() {
    scanf("%d%d", &n, &m), mx[0] = inf;
    for (int i = 1; i <= n; i++) scanf("%d", &col[i]);
    for (int i = 1; i <= n - 1; i++) {
        scanf("%d%d", &u, &v);
        g[u].push_back(v), g[v].push_back(u);
    }
    all = n, getroot(1, 0), solve(rt);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &l, &r, &u);
        for (auto p : h[u])
            if (l <= p.l && p.r <= r) {
                rt = p.id;
                break;
            }
        vec[rt].push_back({l, r, i, 1});
    }
    for (int i = 1; i <= lim; i++) pos[i] = inf;
    for (int i = 1; i <= n; i++) {
        sort(vec[i].begin(), vec[i].end(), cmp);
        for (auto p : vec[i]) {
            if (!p.op) {
                if (p.r >= pos[p.x]) continue;
                add(pos[p.x], -1), add(p.r, 1), pos[p.x] = p.r;
            } else
                res[p.x] = sum(p.r);
        }
        for (auto p : vec[i]) if (!p.op) add(pos[p.x], -1), pos[p.x] = inf;
    }
    for (int i = 1; i <= m; i++) printf("%d\n", res[i]);
    return 0;
}
</oper></node></int>