結果

問題 No.2676 A Tourist
ユーザー 👑 eoeo
提出日時 2024-03-13 19:57:49
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,086 ms / 5,000 ms
コード長 7,633 bytes
コンパイル時間 2,096 ms
コンパイル使用メモリ 122,648 KB
最終ジャッジ日時 2025-02-20 04:11:52
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0