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

• 問題: No.2676 A Tourist
• ユーザー: 👑 eoeo
• 提出日時: 2024-03-13 22:31:39
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 1,455 ms / 5,000 ms
• コード長: 7,634 bytes
• コンパイル時間: 1,750 ms
• コンパイル使用メモリ: 124,040 KB
• 実行使用メモリ: 18,944 KB
• 最終ジャッジ日時: 2024-09-29 23:37:36
• 合計ジャッジ時間: 24,965 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	451 ms; 8,576 KB
testcase_02	AC	1,455 ms; 18,816 KB
testcase_03	AC	999 ms; 18,944 KB
testcase_04	AC	1,115 ms; 18,944 KB
testcase_05	AC	1,204 ms; 18,816 KB
testcase_06	AC	245 ms; 8,576 KB
testcase_07	AC	765 ms; 18,944 KB
testcase_08	AC	353 ms; 18,944 KB
testcase_09	AC	620 ms; 18,816 KB
testcase_10	AC	386 ms; 18,816 KB
testcase_11	AC	819 ms; 17,920 KB
testcase_12	AC	386 ms; 8,448 KB
testcase_13	AC	1,155 ms; 18,816 KB
testcase_14	AC	694 ms; 18,816 KB
testcase_15	AC	850 ms; 18,944 KB
testcase_16	AC	415 ms; 8,576 KB
testcase_17	AC	1,316 ms; 18,816 KB
testcase_18	AC	854 ms; 18,944 KB
testcase_19	AC	1,205 ms; 18,944 KB
testcase_20	AC	1,035 ms; 18,944 KB
testcase_21	AC	98 ms; 6,820 KB
testcase_22	AC	138 ms; 6,816 KB
testcase_23	AC	87 ms; 6,816 KB
testcase_24	AC	161 ms; 6,820 KB
testcase_25	AC	30 ms; 6,820 KB
testcase_26	AC	1 ms; 6,816 KB
testcase_27	AC	218 ms; 8,576 KB
testcase_28	AC	687 ms; 18,944 KB
testcase_29	AC	322 ms; 18,944 KB
testcase_30	AC	636 ms; 18,944 KB
testcase_31	AC	538 ms; 18,944 KB
testcase_32	AC	378 ms; 18,816 KB

ソースコード

#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <set>
#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 find_parent(int x) {
        if (x < 0 || x >= Nodes.size()) assert(0);
        if (isExist(Nodes[x]) == false) assert(0);
        access(x);
        LinkCutNode *now = Nodes[x];
        now->eval();
        if (isExist(now->left) == false) return -1;
        now = now->left;
        now->eval();

        while (isExist(now->right) == true) {
            now = now->right;
            now->eval();
        }

        now->splay();
        now->update();
        access(now->id);
        return now->id;
    }
    int LCA(int x, int y) {
        access(x);
        int lca = access(y);
        access(lca);
        return lca;
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    LinkCutTree<long long> T(n + 1);
    vector<long long> a(n + 1);
    // 超頂点 0 を用意する
    T.link(0, 1);
    REP(i, n + 1)
    T.update_val(i, 0);
    REP(i, n)
    cin >> a[i + 1];

    REP(i, n - 1) {
        int u, v;
        cin >> u >> v;
        T.link(u, v);
    }
    T.evert(0);
    FOR(i, 1, n + 1) {
        int p = T.find_parent(i);
        T.add_val(p, a[i]);
    }

    REP(i, q) {
        int t;
        cin >> t;
        long long u, v;
        cin >> u >> v;
        if (t == 0) {
            T.evert(0);
            int p = T.find_parent(u);
            T.add_val(p, v);
            a[u] += v;
        } else {
            T.evert(u);
            T.access(v);
            long long res = T.Nodes[v]->Sum;
            T.evert(0);
            int lca = T.LCA(u, v);
            int lcap = T.find_parent(lca);
            res += a[lcap] + a[lca];
            cout << res << endl;
        }
    }
}