#959016 (C++17) No.2676 A Tourist

• 問題: No.2676 A Tourist
• ユーザー: Xelmeph
• 提出日時: 2024-03-09 11:39:12
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 4,387 ms / 5,000 ms
• コード長: 8,842 bytes
• コンパイル時間: 2,428 ms
• コンパイル使用メモリ: 150,176 KB
• 最終ジャッジ日時: 2025-02-20 03:27:53
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
sample	AC * 2
other	AC * 31

ソースコード

#include <cassert>
#include <cmath>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

#define FOR(i, a, b) for (long long i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

template <class T>
class LinkCutTree {
   public:
    struct LinkCutNode {
        LinkCutNode *parent = nullptr;
        LinkCutNode *left = nullptr;
        LinkCutNode *right = nullptr;
        T Value;
        T Sum;
        int id = -1;
        int SubTreeSize = 1;
        bool reverse_flag_lazy = false;
        void set_lazyReverse() {
            this->reverse_flag_lazy = !(this->reverse_flag_lazy);
        }
        LinkCutNode() {
        }
        LinkCutNode(int id_, T val) {
            id = id_;
            Value = val;
            Sum = val;
        }
        bool isExist(LinkCutNode *Nd) {
            if (Nd != nullptr)
                return true;
            else
                return false;
        }

        bool isRoot() {
            return (isExist(this->parent) == false || (this->parent->left != this && this->parent->right != this));
        }

        void rotate() {
            LinkCutNode *Parent, *GrandParent, *Child;
            Parent = this->parent;

            Child = nullptr;
            if (isExist(Parent) == false) {
                return;
            }
            GrandParent = Parent->parent;

            Parent->eval();
            this->eval();
            if (Parent->left == this) {
                Child = this->right;
                this->right = Parent;
                Parent->left = Child;
            } else if (Parent->right == this) {
                Child = this->left;
                this->left = Parent;
                Parent->right = Child;
            }
            if (isExist(GrandParent)) {
                if (Parent == GrandParent->left) {
                    GrandParent->left = this;
                } else if (Parent == GrandParent->right) {
                    GrandParent->right = this;
                }
            }
            this->parent = GrandParent;
            Parent->parent = this;
            if (isExist(Child)) Child->parent = Parent;
            Parent->update();
            this->update();
            return;
        }

        int state() {
            if (isExist(this->parent) == false) {
                return 0;
            } else {
                this->parent->eval();
                if (this->parent->left == this) {
                    return 1;
                } else if (this->parent->right == this) {
                    return 2;
                } else {
                    return 0;
                }
            }
        }

        void splay() {
            if (isExist(this) == false) return;
            this->eval();

            while (this->state() != 0) {
                if (this->parent->state() == 0) {
                    this->rotate();
                } else if (this->state() == this->parent->state()) {
                    this->parent->rotate();
                    this->rotate();
                } else {
                    this->rotate();
                    this->rotate();
                }
            }
            return;
        }

        void update(bool evaluate = true) {
            if (isExist(this) == false) return;

            if (evaluate) this->eval();
            if (isExist(this->left) && evaluate) this->left->eval();
            if (isExist(this->right) && evaluate) this->right->eval();
            this->SubTreeSize = 1;
            this->Sum = this->Value;
            if (isExist(this->left)) {
                this->SubTreeSize += this->left->SubTreeSize;
                this->Sum += this->left->Sum;
            }
            if (isExist(this->right)) {
                this->SubTreeSize += this->right->SubTreeSize;
                this->Sum += this->right->Sum;
            }

            return;
        }
        void eval() {
            if (this->reverse_flag_lazy) {
                swap(this->left, this->right);
                // 下に伝播
                if (isExist(this->left)) this->left->set_lazyReverse();
                if (isExist(this->right)) this->right->set_lazyReverse();
                this->reverse_flag_lazy = false;
            }
        }
    };

   private:
    bool isExist(LinkCutNode *Nd) {
        if (Nd == nullptr) {
            return false;
        } else {
            return true;
        }
    }

    int access_sub(LinkCutNode *Node) {
        if (isExist(Node) == false) return -1;
        int res = Node->id;
        while (1) {
            Node->splay();
            Node->right = nullptr;
            Node->update();
            if (isExist(Node->parent) == false) break;
            res = Node->parent->id;

            Node->parent->splay();
            Node->parent->right = Node;
            Node->parent->update();
        }
        return res;
    }

    void link_sub(LinkCutNode *c, LinkCutNode *p) {
        if (isExist(c) && isExist(p)) {
            evert_sub(c);
            access_sub(p);
            c->parent = p;
            p->update();
        }
    }

    void evert_sub(LinkCutNode *Node) {
        if (isExist(Node) == false) return;
        access_sub(Node);
        Node->set_lazyReverse();
        Node->update();
        access_sub(Node);
    }

   public:
    int V = 0;

    vector<LinkCutNode *> Nodes;

    LinkCutTree(int size_, T init_ = 0) {
        V = size_ + 10;
        Nodes = vector<LinkCutNode *>(V);
        REP(i, V)
        Nodes[i] = new LinkCutNode(i, init_);
    }

    int access(int id) {
        return access_sub(Nodes[id]);
    }

    void update_val(int i, T x) {
        access(i);
        Nodes[i]->Value = x;
        Nodes[i]->update();
    }

    void add_val(int i, T x) {
        access(i);
        Nodes[i]->Value += x;
        Nodes[i]->update();
    }

    void evert(int x) {
        evert_sub(Nodes[x]);
    }

    void link(int c, int p) {
        link_sub(Nodes[c], Nodes[p]);
    }

    int LCA(int x, int y) {
        access(x);
        int lca = access(y);
        access(lca);
        return lca;
    }

    void debug() {
        for (LinkCutNode *x : Nodes) {
            cerr << x->id << "th node : " << x->Value << endl;
        }
    }
};

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<vector<int> > G(N + 1);

    // パス上の頂点の重みを計算する
    LinkCutTree<long long> T(N + 1, 0);

    // 隣接頂点の重みの和(ただし、更新クエリでは 次数が border 以上の頂点の変更を反映しない)
    LinkCutTree<long long> T_adj(N + 1, 0);

    vector<long long> a(N + 1);

    for (int i = 0; i < N; i++) {
        cin >> a[i + 1];
        T.update_val(i + 1, a[i + 1]);
    }

    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
        T.link(u, v);
        T_adj.link(u, v);
    }

    T.evert(1);  // 根頂点を 1 に
    T_adj.evert(1);

    for (int u = 1; u < N + 1; u++) {
        for (int nx : G[u]) T_adj.add_val(nx, T.Nodes[u]->Value);
    }

    int border = sqrt(N);
    vector<int> stack_vertices;        // 次数が大きい頂点たち
    vector<long long> diff(N + 1, 0);  // 更新クエリによる、元の重みとの差分

    for (int x = 1; x <= N; x++) {
        if (int(G[x].size()) >= border) stack_vertices.push_back(x);
    }

    for (int c = 1; c <= Q; c++) {
        long long t, u, v;
        cin >> t >> u >> v;
        if (t == 0) {
            // 次数が大きい頂点のデータに関しては、クエリに答えるときに計算する
            if (int(G[u].size()) >= border) {
                diff[u] += v;
                continue;
            }

            // 次数が小さいものは愚直に更新する
            T.add_val(u, v);
            if (int(G[u].size()) < border) {
                for (int adj : G[u]) {
                    T_adj.add_val(adj, v);
                }
            }
        } else {
            long long res = 0;
            T.evert(u);  // 根頂点を u にすることで、v にアクセスするとパスになる
            T.access(v);
            T_adj.evert(u);
            T_adj.access(v);

            res = T_adj.Nodes[v]->Sum - T.Nodes[v]->Sum + T.Nodes[u]->Value + T.Nodes[v]->Value;

            for (int x : stack_vertices) {
                T.evert(x);
                int lca = T.LCA(u, v);
                T.access(lca);
                // 頂点 x の隣接頂点が パス u-v に影響がある場合
                if (T.Nodes[lca]->SubTreeSize - 1 == 1) res += diff[x];
                // 頂点 x 地震が パス u-v に影響がある場合
                if (T.Nodes[lca]->SubTreeSize - 1 == 0) res += diff[x];
            }
            cout << res << "\n";
        }
    }

    return 0;
}