Heavy-light-декомпозиция: различия между версиями

Версия от 21:58, 14 февраля 2026

struct SegmentTree {
    int size;
    vector<int> t;

    int query(int v, int vl, int vr, int l, int r) {
        if (vr < l || r < vl)
            return -1e9;
        if (l <= vl && vr <= r)
            return t[v];
        int vm = vl + (vr - vl) / 2;
        int ql = query(2 * v + 1, vl, vm, l, r);
        int qr = query(2 * v + 2, vm + 1, vr, l, r);
        return max(ql, qr);
    }

    void modify(int v, int vl, int vr, int index, int value) {
        if (vr < index || index < vl)
            return;
        if (vl == vr) {
            t[v] += value;
            return;
        }
        int vm = vl + (vr - vl) / 2;
        modify(2 * v + 1, vl, vm, index, value);
        modify(2 * v + 2, vm + 1, vr, index, value);
        t[v] = max(t[2 * v + 1], t[2 * v + 2]);
    }

    SegmentTree(int size) : size(size), t(4 * size) {}

    int getMax(int l, int r) {
        return query(0, 0, size - 1, l, r);
    }

    void addValue(int index, int value) {
        modify(0, 0, size - 1, index, value);
    }
};

struct HeavyLightDecomposition {
    vector<vector<int>> graph;
    vector<int> l, r, parent, subtreeSize;
    int timer = 0;
    vector<vector<int>> paths;
    vector<int> pathOf, posOf;
    vector<SegmentTree> segmentTrees;

    HeavyLightDecomposition(int vertexCount) :
        graph(vertexCount), l(vertexCount), r(vertexCount),
        parent(vertexCount), subtreeSize(vertexCount),
        pathOf(vertexCount), posOf(vertexCount) {}

    void addEdge(int a, int b) {
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    int dfs(int v, int p) {
        l[v] = timer++;
        parent[v] = p;
        subtreeSize[v] = 1;

        for (int to : graph[v])
            if (to != p)
                subtreeSize[v] += dfs(to, v);

        r[v] = timer++;
        return subtreeSize[v];
    }

    bool isAncestor(int a, int b) {
        return l[a] <= l[b] && r[b] <= r[a];
    }

    void buildPath(int v, int pathIndex) {
        if (paths.size() == pathIndex)
            paths.emplace_back();
        paths[pathIndex].push_back(v);

        pathOf[v] = pathIndex;
        posOf[v] = paths[pathIndex].size() - 1;

        int maxTo = -1;
        for (int to : graph[v])
            if (to != parent[v] && (maxTo == -1 || subtreeSize[maxTo] < subtreeSize[to]))
                maxTo = to;

        for (int to : graph[v]) {
            if (to == parent[v])
                continue;
            if (to == maxTo)
                buildPath(to, pathIndex);
            else
                buildPath(to, paths.size());
        }
    }

    void prepare(int root) {
        dfs(root, -1);
        buildPath(root, 0);
        for (vector<int> &path : paths)
            segmentTrees.push_back(SegmentTree(path.size()));
    }

    int getMax(int a, int b) {
        int res = 0;

        for (; !isAncestor(paths[pathOf[a]][0], b); a = parent[paths[pathOf[a]][0]])
            res = max(res, segmentTrees[pathOf[a]].getMax(0, posOf[a]));
        for (; !isAncestor(paths[pathOf[b]][0], a); b = parent[paths[pathOf[b]][0]])
            res = max(res, segmentTrees[pathOf[b]].getMax(0, posOf[b]));

        if (posOf[a] > posOf[b])
            swap(a, b);
        return max(res, segmentTrees[pathOf[a]].getMax(posOf[a], posOf[b]));
    }

    void addValue(int v, int value) {
        segmentTrees[pathOf[v]].addValue(posOf[v], value);
    }
};

Ссылки на задачи

Timus #1553 — Caves and Tunnels

Ссылки

@@ Строка 1: / Строка 1: @@
-  #include <stdio.h>
+  struct SegmentTree {
- #include <vector>
+      int size;
- #include <queue>
+      vector<int> t;
- #include <set>
- #include <map>
- #include <algorithm>
- #include <iostream>
- using namespace std;
- class ST {
-      int *t, size;
-      void build(int v, int vl, int vr) {
-         if (vl == vr) {
-             t[v] = 0;
-             return;
-         }
-         int vm = vl + (vr - vl) / 2;
-         build(2 * v + 1, vl, vm);
-         build(2 * v + 2, vm + 1, vr);
-         t[v] = max(t[2 * v + 1], t[2 * v + 2]);
-     }
       int query(int v, int vl, int vr, int l, int r) {
-          if (r < vl || vr < l)
+          if (vr < l || r < vl)
-              return -(1 << 30);
+              return -1e9;
           if (l <= vl && vr <= r)
               return t[v];
@@ Строка 30: / Строка 13: @@
           return max(ql, qr);
       }
-      void modify(int v, int vl, int vr, int pos, int val) {
-          if (pos < vl || vr < pos)
+      void modify(int v, int vl, int vr, int index, int value) {
+          if (vr < index || index < vl)
               return;
-          if (pos == vl && vl == vr) {
+          if (vl == vr) {
-              t[v] += val;
+              t[v] += value;
               return;
           }
           int vm = vl + (vr - vl) / 2;
-          modify(2 * v + 1, vl, vm, pos, val);
+          modify(2 * v + 1, vl, vm, index, value);
-          modify(2 * v + 2, vm + 1, vr, pos, val);
+          modify(2 * v + 2, vm + 1, vr, index, value);
           t[v] = max(t[2 * v + 1], t[2 * v + 2]);
       }
-  public:
-      ST() {}
+      SegmentTree(int size) : size(size), t(4 * size) {}
-     ST(int n) {
-         t = new int[4 * n];
+      int getMax(int l, int r) {
-         size = n;
-         build(0, 0, size - 1);
-     }
-      int query(int l, int r) {
           return query(0, 0, size - 1, l, r);
       }
-      void modify(int pos, int val) {
-          modify(0, 0, size - 1, pos, val);
+      void addValue(int index, int value) {
+          modify(0, 0, size - 1, index, value);
       }
-  } st[100010];
+  };
-  int n, q, a, b;
+  struct HeavyLightDecomposition {
- char c;
+     vector<vector<int>> graph;
- vector<int> g[100010];
+     vector<int> l, r, parent, subtreeSize;
-  int tIn[100010], tOut[100010], timer, size[100010], parent[100010];
+     int timer = 0;
+     vector<vector<int>> paths;
+     vector<int> pathOf, posOf;
+     vector<SegmentTree> segmentTrees;
+     HeavyLightDecomposition(int vertexCount) :
+         graph(vertexCount), l(vertexCount), r(vertexCount),
+         parent(vertexCount), subtreeSize(vertexCount),
+         pathOf(vertexCount), posOf(vertexCount) {}
- void dfs(int v) {
+     void addEdge(int a, int b) {
-     tIn[v] = ++timer;
+         graph[a].push_back(b);
-     size[v] = 1;
+          graph[b].push_back(a);
-     for (int i = 0; i < g[v].size(); i++) {
-          if (!tIn[g[v][i]]) {
-             parent[g[v][i]] = v;
-             dfs(g[v][i]);
-             size[v] += size[g[v][i]];
-         }
       }
-     tOut[v] = ++timer;
- }
- bool isAncestor(int a, int v) {
+     int dfs(int v, int p) {
-     return tIn[a] <= tIn[v] && tOut[v] <= tOut[a];
+         l[v] = timer++;
-  }
+         parent[v] = p;
+         subtreeSize[v] = 1;
- int chainInd[100010], chainPos[100010];
- int chainSize[100010], chainRoot[100010];
+         for (int to : graph[v])
- int chainsCount;
+             if (to != p)
+                 subtreeSize[v] += dfs(to, v);
- void buildHLD(int v, int chain) {
+         r[v] = timer++;
-     chainInd[v] = chain;
+          return subtreeSize[v];
-     chainPos[v] = chainSize[chain];
-     chainSize[chain]++;
-     if (chainSize[chain] == 1)
-          chainRoot[chain] = v;
-     int maxChild = -1;
-     for (int i = 0; i < g[v].size(); i++) {
-         if (g[v][i] != parent[v] && (maxChild == -1 || size[g[v][i]] > size[g[v][maxChild]]))
-             maxChild = i;
       }
-     if (maxChild != -1)
+      bool isAncestor(int a, int b) {
-      for (int i = 0; i < g[v].size(); i++) {
+          return l[a] <= l[b] && r[b] <= r[a];
-          if (g[v][i] == parent[v])
-             continue;
-         if (i == maxChild)
-             buildHLD(g[v][i], chain);
-         else
-             buildHLD(g[v][i], chainsCount++);
       }
- }
- int queryHLD(int a, int b) {
+     void buildPath(int v, int pathIndex) {
-     int res = 0;
+         if (paths.size() == pathIndex)
-     while (1) {
+             paths.emplace_back();
-          if (isAncestor(chainRoot[chainInd[a]], b))
+         paths[pathIndex].push_back(v);
-             break;
-          res = max(res, st[chainInd[a]].query(0, chainPos[a]));
+          pathOf[v] = pathIndex;
-          a = parent[chainRoot[chainInd[a]]];
+         posOf[v] = paths[pathIndex].size() - 1;
+         int maxTo = -1;
+          for (int to : graph[v])
+             if (to != parent[v] && (maxTo == -1 || subtreeSize[maxTo] < subtreeSize[to]))
+                 maxTo = to;
+          for (int to : graph[v]) {
+             if (to == parent[v])
+                 continue;
+             if (to == maxTo)
+                 buildPath(to, pathIndex);
+             else
+                 buildPath(to, paths.size());
+         }
       }
-      while (1) {
-          if (isAncestor(chainRoot[chainInd[b]], a))
+      void prepare(int root) {
-             break;
+          dfs(root, -1);
-          res = max(res, st[chainInd[b]].query(0, chainPos[b]));
+          buildPath(root, 0);
-          b = parent[chainRoot[chainInd[b]]];
+          for (vector<int> &path : paths)
+             segmentTrees.push_back(SegmentTree(path.size()));
       }
-     if (chainPos[a] > chainPos[b])
-         swap(a, b);
-     return max(res, st[chainInd[a]].query(chainPos[a], chainPos[b]));
- }
- int main() {
-     freopen("input.txt", "r", stdin);
-     freopen("output.txt", "w", stdout);
-      scanf("%d", &n);
+      int getMax(int a, int b) {
-     for (int i = 0; i < n - 1; i++) {
+         int res = 0;
-         scanf("%d%d", &a, &b);
-          g[a - 1].push_back(b - 1);
+         for (; !isAncestor(paths[pathOf[a]][0], b); a = parent[paths[pathOf[a]][0]])
-          g[b - 1].push_back(a - 1);
+             res = max(res, segmentTrees[pathOf[a]].getMax(0, posOf[a]));
+         for (; !isAncestor(paths[pathOf[b]][0], a); b = parent[paths[pathOf[b]][0]])
+             res = max(res, segmentTrees[pathOf[b]].getMax(0, posOf[b]));
+          if (posOf[a] > posOf[b])
+             swap(a, b);
+          return max(res, segmentTrees[pathOf[a]].getMax(posOf[a], posOf[b]));
       }
-      dfs(0);
+      void addValue(int v, int value) {
-     buildHLD(0, chainsCount++);
+          segmentTrees[pathOf[v]].addValue(posOf[v], value);
-     for (int i = 0; i < chainsCount; i++)
-         st[i] = ST(chainSize[i]);
-     scanf("%d", &q);
-     for (int i = 0; i < q; i++) {
-          scanf(" %c%d%d", &c, &a, &b);
-         if (c == 'I')
-             st[chainInd[a - 1]].modify(chainPos[a - 1], b);
-         else
-             printf("%d\n", queryHLD(a - 1, b - 1));
       }
-  }
+  };
 == Ссылки на задачи ==

Heavy-light-декомпозиция: различия между версиями

Версия от 21:58, 14 февраля 2026

Ссылки на задачи

Ссылки

Навигация

Поиск