#394438 (C++17) No.399 動的な領主

• 問題: No.399 動的な領主
• ユーザー: xuzijian629
• 提出日時: 2019-10-28 14:32:04
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 724 ms / 2,000 ms
• コード長: 9,678 bytes
• コンパイル時間: 2,884 ms
• コンパイル使用メモリ: 212,360 KB
• 最終ジャッジ日時: 2025-01-08 02:01:55
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
other	AC * 19

ソースコード

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

// T0: 元の配列のモノイド
// T1: T0に対する作用素モノイド
template <class T0, class T1>
class BaseLinkCutTree {
    // T0上の演算、単位元
    virtual T0 f0(T0, T0) = 0;
    const T0 u0;
    // T1上の演算、単位元
    virtual T1 f1(T1, T1) = 0;
    const T1 u1;
    // T0に対するT1の作用
    virtual T0 g(T0, T1) = 0;
    // 多数のt1(T1)に対するf1の合成
    virtual T1 p(T1, int) = 0;

    struct Node {
        int cnt;
        T0 val, acc, u0;
        T1 lazy, u1;
        Node *left, *right, *par;
        Node(T0 value, T0 u0, T1 u1)
            : cnt(1), val(value), lazy(u1), acc(u0), u0(u0), u1(u1), left(nullptr), right(nullptr), par(nullptr) {}
        bool isRoot() { return (!par) || (par->left != this && par->right != this); }
        // スプレー木を反転させる
    };

    void push(Node* t) {
        if (t->cnt < 0) {
            swap(t->left, t->right);
            if (t->left) t->left->cnt = -(t->left->cnt);
            if (t->right) t->right->cnt = -(t->right->cnt);
            t->cnt = -t->cnt;
        }
        if (t->lazy != u1) {
            t->val = g(t->val, p(t->lazy, 1));
            t->acc = g(t->acc, p(t->lazy, t->cnt));
            if (t->left) t->left->lazy = g(t->left->lazy, p(t->lazy, 1));
            if (t->right) t->right->lazy = g(t->right->lazy, p(t->lazy, 1));
            t->lazy = u1;
        }
    }

    void eval(Node* t) {
        bool flag = (t->cnt < 0);
        t->cnt = 1, t->acc = t->val;
        if (t->left) push(t->left), t->cnt += _abs(t->left->cnt), t->acc = f1(t->left->acc, t->acc);
        if (t->right) push(t->right), t->cnt += _abs(t->right->cnt), t->acc = f1(t->acc, t->right->acc);
        if (flag) t->cnt = -t->cnt;
    }

    vector<Node*> nodes;

    inline static int _abs(int val) { return val & 0x7fffffff; }
    // 回転
    void rotate(Node* u, bool right) {
        Node *p = u->par, *g = p->par;
        if (right) {
            if ((p->left = u->right)) u->right->par = p;
            u->right = p, p->par = u;
        } else {
            if ((p->right = u->left)) u->left->par = p;
            u->left = p, p->par = u;
        }
        eval(p), eval(u), u->par = g;
        if (!g) return;
        if (g->left == p) g->left = u;
        if (g->right == p) g->right = u;
        eval(g);
    }
    // u を splay 木の根にする
    void splay(Node* u) {
        while (!(u->isRoot())) {
            Node *p = u->par, *gp = p->par;
            if (p->isRoot()) {  // zig
                push(p), push(u);
                rotate(u, (u == p->left));
            } else {
                push(gp), push(p), push(u);
                bool flag = (u == p->left);
                if ((u == p->left) == (p == gp->left)) {  // zig-zig
                    rotate(p, flag), rotate(u, flag);
                } else {  // zig-zag
                    rotate(u, flag), rotate(u, !flag);
                }
            }
        }
        push(u);
    }
    Node* expose(Node* u) {
        Node* last = nullptr;
        for (Node* v = u; v; v = v->par) {
            splay(v);
            v->right = last;
            eval(v);
            last = v;
        }
        splay(u);
        return last;
    }
    bool connected(Node* u, Node* v) {
        expose(u), expose(v);
        return u->par;
    }
    // u と v を結ぶ (v の preferred child を u とする.)
    void link(Node* u, Node* v) {
        // u, v が同じ連結成分にないか
        // assert(!connected(u, v));
        evert(u), u->par = v;
    }
    // u とその親の間の辺を削除
    void cut(Node* u) {
        expose(u);
        // u と親の間に辺があるか
        // assert(u->left);
        u->left->par = nullptr, u->left = nullptr, eval(u);
    }
    Node* lca(Node* u, Node* v) {
        // u,v が同じ連結成分内にあるか
        // assert(connected(u, v));
        expose(u);
        return expose(v);
    }
    void evert(Node* u) { expose(u), u->cnt = -(u->cnt); }
    int depth(Node* u) {
        expose(u);
        return _abs(u->cnt) - 1;
    }
    void update(Node* u, Node* v, const T1 x) {
        evert(u), expose(v);
        v->lazy = f1(v->lazy, x), push(v);
    }
    T0 query(Node* u, Node* v) {
        evert(u), expose(v);
        return v->acc;
    }

public:
    BaseLinkCutTree(T0 u0, T1 u1) : u0(u0), u1(u1) {}
    int make_new_node(T0 v) {
        int idx = nodes.size();
        nodes.push_back(new Node(v, u0, u1));
        return idx;
    }
    // id1 と id2 が同じ木(連結成分)に属するか
    bool connected(int id1, int id2) { return connected(nodes[id1], nodes[id2]); }
    // 木(連結成分)の根 id1 の親を id2 にする
    void link(int id1, int id2) { return link(nodes[id1], nodes[id2]); }
    // id とその親の間の辺を削除する
    void cut(int id) { return cut(nodes[id]); }
    // id1 と id2 の LCA を求める
    int lca(int id1, int id2) { return lca(nodes[id1], nodes[id2])->id; }
    // 元の木の根を id にする
    void evert(int id) { return evert(nodes[id]); }
    // id の深さを求める
    int depth(int id) { return depth(nodes[id]); }
    // id1 と id2 の間にある頂点すべてに x を足す
    void update(int id1, int id2, T1 x) { return update(nodes[id1], nodes[id2], x); }
    // id1 と id2 の間にある頂点すべてのコストの総和を求める
    T0 query(int id1, int id2) { return query(nodes[id1], nodes[id2]); }
};

template <class T0, class T1>
struct MinUpdateQuery : public BaseLinkCutTree<T0, T1> {
    using BaseLinkCutTree<T0, T1>::BaseLinkCutTree;
    MinUpdateQuery() : MinUpdateQuery(numeric_limits<T0>::max(), numeric_limits<T1>::min()) {}
    T0 f0(T0 x, T0 y) override { return min(x, y); }
    T1 f1(T1 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T0 g(T0 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T1 p(T1 x, int len) override { return x; }
};

template <class T0, class T1>
struct SumAddQuery : public BaseLinkCutTree<T0, T1> {
    using BaseLinkCutTree<T0, T1>::BaseLinkCutTree;
    SumAddQuery() : SumAddQuery(0, 0) {}
    T0 f0(T0 x, T0 y) override { return x + y; }
    T1 f1(T1 x, T1 y) override { return x + y; }
    T0 g(T0 x, T1 y) override { return x + y; }
    T1 p(T1 x, int len) override { return x * len; }
};

template <class T0, class T1>
struct MinAddQuery : public BaseLinkCutTree<T0, T1> {
    using BaseLinkCutTree<T0, T1>::BaseLinkCutTree;
    MinAddQuery() : MinAddQuery(numeric_limits<T0>::max(), 0) {}
    T0 f0(T0 x, T0 y) override { return min(x, y); }
    T1 f1(T1 x, T1 y) override { return x + y; }
    T0 g(T0 x, T1 y) override { return x + y; }
    T1 p(T1 x, int len) override { return x; }
};

template <class T0, class T1>
struct SumUpdateQuery : public BaseLinkCutTree<T0, T1> {
    using BaseLinkCutTree<T0, T1>::BaseLinkCutTree;
    SumUpdateQuery() : SumUpdateQuery(0, numeric_limits<T1>::min()) {}
    T0 f0(T0 x, T0 y) override { return x + y; }
    T1 f1(T1 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T0 g(T0 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T1 p(T1 x, int len) override { return x == numeric_limits<T1>::min() ? numeric_limits<T1>::min() : x * len; }
};

template <class T0>
struct SumAffineQuery : public BaseLinkCutTree<T0, pair<T0, T0>> {
    using T1 = pair<T0, T0>;  // first * x + second
    using BaseLinkCutTree<T0, T1>::BaseLinkCutTree;
    SumAffineQuery() : SumAffineQuery(0, {1, 0}) {}
    T0 f0(T0 x, T0 y) override { return x + y; }
    T1 f1(T1 x, T1 y) override { return {x.first * y.first, x.second * y.first + y.second}; }
    T0 g(T0 x, T1 y) override { return y.first * x + y.second; }
    T1 p(T1 x, int len) override { return {x.first, x.second * len}; }
    // update(i, j, {a, b}); // [i, j)にax + bを作用
    // update(i, j, {0, a}); // update
    // update(i, j, {1, a}); // 加算
    // update(i, j, {a, 0}); // 倍
};

template <class T>
struct MinmaxAffineQuery : public BaseLinkCutTree<pair<T, T>, pair<T, T>> {
    using T0 = pair<T, T>;  // {min, max}
    using T1 = pair<T, T>;  // first * x + second
    using BaseLinkCutTree<T0, T1>::BaseLinkCutTree;
    MinmaxAffineQuery()
        : MinmaxAffineQuery({numeric_limits<T>::max(), -numeric_limits<T>::max()}, {1, 0}) {
    }  // TODO: _u1を使うとコンパイル通らない原因不明
    T0 f0(T0 x, T0 y) override { return {min(x.first, y.first), max(x.second, y.second)}; }
    T1 f1(T1 x, T1 y) override { return {x.first * y.first, x.second * y.first + y.second}; }
    T0 g(T0 x, T1 y) override {
        T0 ret = {x.first * y.first + y.second, x.second * y.first + y.second};
        if (y.first < 0) swap(ret.first, ret.second);
        return ret;
    }
    T1 p(T1 x, int len) override { return x; }
    // update(i, j, {a, b}); // [i, j)にax + bを作用
    // update(i, j, {0, a}); // update
    // update(i, j, {1, a}); // 加算
    // update(i, j, {a, 0}); // 倍
};

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

    SumAddQuery<int, int> lct;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) lct.make_new_node(0);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        lct.link(a, b);
    }

    int q;
    cin >> q;
    long long ans = 0;
    while (q--) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        lct.update(a, b, 1);
    }

    for (int i = 0; i < n; i++) {
        int k = lct.query(i, i);
        ans += 1LL * k * (k + 1) / 2;
    }

    cout << ans << endl;
}