#227562 (C++14) No.399 動的な領主

• 問題: No.399 動的な領主
• ユーザー: sekiya9311
• 提出日時: 2018-01-04 21:17:49
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 502 ms / 2,000 ms
• コード長: 6,305 bytes
• コンパイル時間: 1,791 ms
• コンパイル使用メモリ: 184,472 KB
• 実行使用メモリ: 21,248 KB
• 最終ジャッジ日時: 2024-06-02 08:37:15
• 合計ジャッジ時間: 6,863 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	4 ms; 7,424 KB
testcase_01	AC	4 ms; 7,424 KB
testcase_02	AC	5 ms; 7,424 KB
testcase_03	AC	5 ms; 7,424 KB
testcase_04	AC	7 ms; 7,552 KB
testcase_05	AC	37 ms; 8,320 KB
testcase_06	AC	496 ms; 16,128 KB
testcase_07	AC	485 ms; 16,000 KB
testcase_08	AC	492 ms; 16,256 KB
testcase_09	AC	489 ms; 16,256 KB
testcase_10	AC	7 ms; 7,552 KB
testcase_11	AC	28 ms; 8,320 KB
testcase_12	AC	347 ms; 16,768 KB
testcase_13	AC	320 ms; 16,768 KB
testcase_14	AC	77 ms; 21,248 KB
testcase_15	AC	150 ms; 21,248 KB
testcase_16	AC	224 ms; 18,816 KB
testcase_17	AC	502 ms; 16,256 KB
testcase_18	AC	492 ms; 16,256 KB

ソースコード

#include <bits/stdc++.h>

using namespace std;

// 区間加算，区間参照
// 半開区間!!!
template<typename T = int>
class RangeAddQuery {
private:
     vector<T> data, lazy;
     int sz;
     void push(int k, int l, int r) {
          if (this->lazy[k]) {
               this->data[k] += this->lazy[k] * (r - l);
               if (k * 2 + 2 < sz * 2 - 1) {
                    this->lazy[2 * k + 1] += this->lazy[k];
                    this->lazy[2 * k + 2] += this->lazy[k];
               }
               this->lazy[k] = 0;
          }
     }
     void add(int l, int r, int L, int R, int k, T val) {
           this->push(k, l, r);
          if (L <= l && r <= R) {
               this->lazy[k] += val;
               this->push(k, l, r);
          } else if (R <= l || r <= L) {
               return;
          } else if (r - l > 1) {
               const int mid = (l + r) / 2;
               this->add(l, mid, L, R, k * 2 + 1, val);
               this->add(mid, r, L, R, k * 2 + 2, val);
               data[k] = data[k * 2 + 1] + data[k * 2 + 2];
          }
     }
     T query(int l, int r, int L, int R, int k) {
          this->push(k, l, r);
          if (L <= l && r <= R) {
               return data[k];
          } else if (R <= l || r <= L) {
               return 0;
          } else {
               const int mid = (l + r) / 2;
               const T left = this->query(l, mid, L, R, k * 2 + 1);
               const T right = this->query(mid, r, L, R, k * 2 + 2);
               return left + right;
          }
     }
public:
     RangeAddQuery(const int n) {
          this->sz = 1;
          while (this->sz < n) this->sz <<= 1;
          this->data.resize(this->sz * 2 - 1);
          this->lazy.resize(this->sz * 2 - 1);
     }
     void add(int l, int r, T val) {
         this->add(0, this->sz, l, r, 0, val);
     }
     T query(int l, int r) {
          return this->query(0, this->sz, l, r, 0);
     }
};

class HeavyLightDecomposition {

private:
    int N, pos;
    std::vector<std::vector<int>> G;
    std::vector<int> parent;
    std::vector<int> depth;
    std::vector<int> heavy;                 // next node of heavy path
    std::vector<int> sub_tree_cnt;
    std::vector<int> maximum_sub_tree_cnt;
    std::vector<int> tree_th_num;           // what number of tree ?
    std::vector<int> vid, inv_vid;          // re numbering node for decomp (vertex_index)
    std::vector<int> head;                  // root of SubTree in this node

public:
    HeavyLightDecomposition() {}
    HeavyLightDecomposition(int g_size) :
        N(g_size), G(g_size), parent(g_size),
        depth(g_size), heavy(g_size, -1),
        sub_tree_cnt(g_size), pos(0), tree_th_num(g_size),
        head(g_size), vid(g_size), inv_vid(g_size) {}

    void add_edge(const int a, const int b) {
        this->G[a].emplace_back(b);
        this->G[b].emplace_back(a);
    }

    // if forest, tree roots in argument
    void build(const std::vector<int> roots = std::vector<int>(1, 0)) {
        for (int th = 0; th < roots.size(); th++) {
            this->dfs(roots[th], -1);
            this->bfs(roots[th], th);
        }
    }

    // calc SubTree count of this node
    int dfs(const int now, const int prev) {
        parent[now] = prev;
        int sub_tree_all_cnt = 1; // include now node
        int max_sub_tree_cnt = 0;
        for (auto &&nxt : this->G[now]) {
            if (nxt == prev) {
                continue;
            }
            this->depth[nxt] = this->depth[now] + 1;
            const int now_sub_tree_cnt = this->dfs(nxt, now);
            sub_tree_all_cnt += now_sub_tree_cnt;
            if (max_sub_tree_cnt < now_sub_tree_cnt) {
                max_sub_tree_cnt = now_sub_tree_cnt;
                this->heavy[now] = nxt;
            }
        }
        return this->sub_tree_cnt[now] = sub_tree_all_cnt;
    }

    void bfs(const int root, const int th) {
        std::queue<int> que;
        que.emplace(root);
        while (!que.empty()) {
            const int now_head = que.front();
            que.pop();
            for (int now = now_head; now != -1; now = this->heavy[now]) {
                this->tree_th_num[now] = th;
                this->vid[now] = pos++;
                this->inv_vid[this->vid[now]] = now;
                this->head[now] = now_head;
                for (auto &&nxt : this->G[now]) {
                    if (nxt != this->parent[now]
                        && nxt != this->heavy[now]) {
                        // not parent && not same heavy path
                        // == different heavy path && haven't search yet
                        que.emplace(nxt);
                    }
                }
            }
        }
    }

    // node(vertex) func in [l, r] !!!!!
    void for_each_node(int a, int b, const std::function<void(int, int)> &func) {
        if (this->vid[a] > this->vid[b]) {
            std::swap(a, b);
        }
        func(std::max(this->vid[this->head[b]], this->vid[a]), this->vid[b]);
        if (this->head[a] != this->head[b]) {
            this->for_each_node(a, this->parent[this->head[b]], func);
        }
    }

    // edge func in [l, r] !!!!!
    void for_each_edge(int a, int b, const std::function<void(int, int)> &func) {
        if (this->vid[a] > this->vid[b]) {
            std::swap(a, b);
        }
        if (this->head[a] != this->head[b]) {
            func(this->vid[this->head[b]], this->vid[b]);
            this->for_each_edge(a, this->parent[this->head[b]], func);
        } else {
            if (a != b) {
                func(this->vid[a] + 1, this->vid[b]);
            }
        }
    }
};

const int MAX = 1e5 + 10;
RangeAddQuery<long long> ra(MAX);
HeavyLightDecomposition hld;
int n;

int main() {
    scanf("%d", &n);
    hld = HeavyLightDecomposition(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        a--;b--;
        hld.add_edge(a, b);
    }
    hld.build();
    ra.add(0, n, 1);
    long long ans = 0;
    int q;
    scanf("%d", &q);
    while (q--) {
        int a, b;
        scanf("%d%d", &a, &b);
        a--;b--;
        hld.for_each_node(a, b, [&](int l, int r) {
            ans += ra.query(l, r + 1);
            ra.add(l, r + 1, 1);
        });
    }
    printf("%lld\n", ans);
}