test/src/tree/euler_tour/vertex_add_path_sum.test.cpp

View this file on GitHub
Last update: 2021-07-20 21:04:19+09:00
Problem: https://judge.yosupo.jp/problem/vertex_add_path_sum

Depends on

Euler Tour (library/tree/euler_tour.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_path_sum"

#include <iostream>
#include <atcoder/segtree>

#include "library/tree/euler_tour.hpp"
using suisen::EulerTour;

constexpr long long op(long long x, long long y) { return x + y; }
constexpr long long e() { return 0LL; }

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, q;
    std::cin >> n >> q;
    std::vector<long long> a(n);
    for (long long &e : a) std::cin >> e;
    std::vector<std::vector<int>> g(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    EulerTour et(g);
    atcoder::segtree<long long, op, e> seg(2 * n);
    for (int i = 0; i < n; ++i) {
        seg.set(et.visit_time(i), +a[i]);
        seg.set(et.leave_time(i), -a[i]);
    }
    for (int i = 0; i < q; ++i) {
        int t;
        std::cin >> t;
        if (t == 0) {
            int p, x;
            std::cin >> p >> x;
            int l = et.visit_time(p), r = et.leave_time(p);
            seg.set(l, seg.get(l) + x);
            seg.set(r, seg.get(r) - x);
        } else {
            int u, v;
            std::cin >> u >> v;
            int a = et.lca(u, v);
            long long sum_au = seg.prod(et.visit_time(a), et.visit_time(u) + 1);
            long long sum_av = seg.prod(et.visit_time(a) + 1, et.visit_time(v) + 1);
            std::cout << sum_au + sum_av << '\n';
        }
    }
    return 0;
}

#line 1 "test/src/tree/euler_tour/vertex_add_path_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_path_sum"

#include <iostream>
#include <atcoder/segtree>

#line 1 "library/tree/euler_tour.hpp"



#include <limits>
#include <vector>

namespace suisen {
/**
 * ImplicitGraph g : (int u, auto f) -> { for (int v : adjacent(u)) f(v); }
 */
class EulerTour {
    public:
        template <typename ImplicitGraph>
        EulerTour(const ImplicitGraph g, int n, int root = 0) : n(n), m(ceil_pow2(2 * n)) {
            dep.resize(n + 1), visit.resize(n), leave.resize(n);
            seg.assign(2 * m, n);
            dfs(g, root);
            for (int k = m - 1; k > 0; --k) seg[k] = argmin(seg[(k << 1) | 0], seg[(k << 1) | 1]);
        }
        template <typename Edge, typename EdgeToNode>
        EulerTour(const std::vector<std::vector<Edge>> &g, const EdgeToNode eton, int root = 0) :
            EulerTour([&](int u, auto f) { for (const Edge &e : g[u]) f(eton(e)); }, g.size(), root) {}
        EulerTour(const std::vector<std::vector<int>> &g, int root = 0) :
            EulerTour([&](int u, auto f) { for (int v : g[u]) f(v); }, g.size(), root) {}
        int lca(int u, int v) const {
            if (visit[u] > visit[v]) return lca(v, u);
            int res = n;
            for (int l = m + visit[u], r = m + visit[v] + 1; l < r; l >>= 1, r >>= 1) {
                if (l & 1) res = argmin(res, seg[l++]);
                if (r & 1) res = argmin(res, seg[--r]);
            }
            return res;
        }
        inline int dist(int u, int v) const { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
        inline int depth(int u) const { return dep[u]; }
        inline int visit_time(int u) const { return visit[u]; }
        inline int leave_time(int u) const { return leave[u]; }
        inline int parent(int u) const {
            int p = seg[m + leave[u]];
            return p == n ? -1 : p;
        }
    private:
        const int n, m;
        std::vector<int> visit, leave, dep, seg;
        template <typename ImplicitGraph>
        void dfs(ImplicitGraph g, int root) {
            dep[root] = 0, dep[n] = std::numeric_limits<int>::max();
            int k = 0;
            auto f = [&](auto self, int u, int p) -> void {
                visit[u] = k, seg[m + k++] = u;
                g(u, [&](int v){ if (v != p) dep[v] = dep[u] + 1, self(self, v, u); });
                leave[u] = k, seg[m + k++] = p;
            };
            f(f, root, n);
        }
        inline int argmin(int u, int v) const { return dep[u] < dep[v] ? u : v; }
        static int ceil_pow2(const int n) {
            int k = 1;
            while (k < n) k <<= 1;
            return k;
        }
};
} // namespace suisen


#line 7 "test/src/tree/euler_tour/vertex_add_path_sum.test.cpp"
using suisen::EulerTour;

constexpr long long op(long long x, long long y) { return x + y; }
constexpr long long e() { return 0LL; }

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, q;
    std::cin >> n >> q;
    std::vector<long long> a(n);
    for (long long &e : a) std::cin >> e;
    std::vector<std::vector<int>> g(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    EulerTour et(g);
    atcoder::segtree<long long, op, e> seg(2 * n);
    for (int i = 0; i < n; ++i) {
        seg.set(et.visit_time(i), +a[i]);
        seg.set(et.leave_time(i), -a[i]);
    }
    for (int i = 0; i < q; ++i) {
        int t;
        std::cin >> t;
        if (t == 0) {
            int p, x;
            std::cin >> p >> x;
            int l = et.visit_time(p), r = et.leave_time(p);
            seg.set(l, seg.get(l) + x);
            seg.set(r, seg.get(r) - x);
        } else {
            int u, v;
            std::cin >> u >> v;
            int a = et.lca(u, v);
            long long sum_au = seg.prod(et.visit_time(a), et.visit_time(u) + 1);
            long long sum_av = seg.prod(et.visit_time(a) + 1, et.visit_time(v) + 1);
            std::cout << sum_au + sum_av << '\n';
        }
    }
    return 0;
}