library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub tko919/library

:heavy_check_mark: Verify/LC_vertex_add_range_contour_sum_on_tree.test.cpp

Depends on

Code

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

#include "Template/template.hpp"

#include "Utility/fastio.hpp"


#include "Graph/contour.hpp"

#include "DataStructure/bit.hpp"


int main() {
    int n, q;
    read(n, q);
    vector<ll> a(n);
    read(a);
    ContourQuery buf(n);
    rep(_, 0, n - 1) {
        int u, v;
        read(u, v);
        buf.add_edge(u, v);
    }
    auto len = buf.run();
    vector<BIT<ll>> seg(len.size());
    rep(i, 0, len.size()) seg[i] = BIT<ll>(len[i]);
    rep(v, 0, n) {
        for (auto &[i, p] : buf.point(v))
            seg[i].add(p, a[v]);
    }

    while (q--) {
        int t;
        read(t);
        if (t == 0) {
            int v, x;
            read(v, x);
            for (auto &[i, p] : buf.point(v))
                seg[i].add(p, x);
        } else {
            int v, L, R;
            read(v, L, R);
            ll ret = 0;
            for (auto &[i, LR] : buf.range(v, L, R)) {
                auto [lb, rb] = LR;
                ret += seg[i].sum(lb, rb);
            }
            print(ret);
        }
    }
    return 0;
}
#line 1 "Verify/LC_vertex_add_range_contour_sum_on_tree.test.cpp"
#define PROBLEM                                                                \
    "https://judge.yosupo.jp/problem/vertex_add_range_contour_sum_on_tree"

#line 1 "Template/template.hpp"
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (int)(b-1); i >= (int)(a); i--)
#define ALL(v) (v).begin(), (v).end()
#define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v, x) int(lower_bound(ALL(v), (x)) - (v).begin())
#define UB(v, x) int(upper_bound(ALL(v), (x)) - (v).begin())

using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;

template <typename T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T, typename U> T ceil(T x, U y) {
    assert(y != 0);
    if (y < 0)
        x = -x, y = -y;
    return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U> T floor(T x, U y) {
    assert(y != 0);
    if (y < 0)
        x = -x, y = -y;
    return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T> int popcnt(T x) {
    return __builtin_popcountll(x);
}
template <typename T> int topbit(T x) {
    return (x == 0 ? -1 : 63 - __builtin_clzll(x));
}
template <typename T> int lowbit(T x) {
    return (x == 0 ? -1 : __builtin_ctzll(x));
}

#ifdef LOCAL
#define show(...) _show(0, #__VA_ARGS__, __VA_ARGS__)
#else
#define show(...) true
#endif
template <typename T> void _show(int i, T name) {
    cerr << '\n';
}
template <typename T1, typename T2, typename... T3>
void _show(int i, const T1 &a, const T2 &b, const T3 &...c) {
    for (; a[i] != ',' && a[i] != '\0'; i++)
        cerr << a[i];
    cerr << ":" << b << " ";
    _show(i + 1, a, c...);
}
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << "P(" << p.first << ", " << p.second << ")";
    return os;
}
template <typename T, template <class> class C>
ostream &operator<<(ostream &os, const C<T> &v) {
    os << "[";
    for (auto d : v)
        os << d << ", ";
    os << "]";
    return os;
}
#line 2 "Utility/fastio.hpp"
#include <unistd.h>

namespace fastio {
static constexpr uint32_t SZ = 1 << 17;
char ibuf[SZ];
char obuf[SZ];
char out[100];
// pointer of ibuf, obuf


uint32_t pil = 0, pir = 0, por = 0;

struct Pre {
    char num[10000][4];
    constexpr Pre() : num() {
        for (int i = 0; i < 10000; i++) {
            int n = i;
            for (int j = 3; j >= 0; j--) {
                num[i][j] = n % 10 | '0';
                n /= 10;
            }
        }
    }
} constexpr pre;

inline void load() {
    memmove(ibuf, ibuf + pil, pir - pil);
    pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin);
    pil = 0;
    if (pir < SZ)
        ibuf[pir++] = '\n';
}

inline void flush() {
    fwrite(obuf, 1, por, stdout);
    por = 0;
}

void rd(char &c) {
    do {
        if (pil + 1 > pir)
            load();
        c = ibuf[pil++];
    } while (isspace(c));
}

void rd(string &x) {
    x.clear();
    char c;
    do {
        if (pil + 1 > pir)
            load();
        c = ibuf[pil++];
    } while (isspace(c));
    do {
        x += c;
        if (pil == pir)
            load();
        c = ibuf[pil++];
    } while (!isspace(c));
}

template <typename T> void rd_real(T &x) {
    string s;
    rd(s);
    x = stod(s);
}

template <typename T> void rd_integer(T &x) {
    if (pil + 100 > pir)
        load();
    char c;
    do
        c = ibuf[pil++];
    while (c < '-');
    bool minus = 0;
    if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
        if (c == '-') {
            minus = 1, c = ibuf[pil++];
        }
    }
    x = 0;
    while ('0' <= c) {
        x = x * 10 + (c & 15), c = ibuf[pil++];
    }
    if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
        if (minus)
            x = -x;
    }
}

void rd(int &x) {
    rd_integer(x);
}
void rd(ll &x) {
    rd_integer(x);
}
void rd(i128 &x) {
    rd_integer(x);
}
void rd(uint &x) {
    rd_integer(x);
}
void rd(ull &x) {
    rd_integer(x);
}
void rd(u128 &x) {
    rd_integer(x);
}
void rd(double &x) {
    rd_real(x);
}
void rd(long double &x) {
    rd_real(x);
}

template <class T, class U> void rd(pair<T, U> &p) {
    return rd(p.first), rd(p.second);
}
template <size_t N = 0, typename T> void rd_tuple(T &t) {
    if constexpr (N < std::tuple_size<T>::value) {
        auto &x = std::get<N>(t);
        rd(x);
        rd_tuple<N + 1>(t);
    }
}
template <class... T> void rd(tuple<T...> &tpl) {
    rd_tuple(tpl);
}

template <size_t N = 0, typename T> void rd(array<T, N> &x) {
    for (auto &d : x)
        rd(d);
}
template <class T> void rd(vector<T> &x) {
    for (auto &d : x)
        rd(d);
}

void read() {}
template <class H, class... T> void read(H &h, T &...t) {
    rd(h), read(t...);
}

void wt(const char c) {
    if (por == SZ)
        flush();
    obuf[por++] = c;
}
void wt(const string s) {
    for (char c : s)
        wt(c);
}
void wt(const char *s) {
    size_t len = strlen(s);
    for (size_t i = 0; i < len; i++)
        wt(s[i]);
}

template <typename T> void wt_integer(T x) {
    if (por > SZ - 100)
        flush();
    if (x < 0) {
        obuf[por++] = '-', x = -x;
    }
    int outi;
    for (outi = 96; x >= 10000; outi -= 4) {
        memcpy(out + outi, pre.num[x % 10000], 4);
        x /= 10000;
    }
    if (x >= 1000) {
        memcpy(obuf + por, pre.num[x], 4);
        por += 4;
    } else if (x >= 100) {
        memcpy(obuf + por, pre.num[x] + 1, 3);
        por += 3;
    } else if (x >= 10) {
        int q = (x * 103) >> 10;
        obuf[por] = q | '0';
        obuf[por + 1] = (x - q * 10) | '0';
        por += 2;
    } else
        obuf[por++] = x | '0';
    memcpy(obuf + por, out + outi + 4, 96 - outi);
    por += 96 - outi;
}

template <typename T> void wt_real(T x) {
    ostringstream oss;
    oss << fixed << setprecision(15) << double(x);
    string s = oss.str();
    wt(s);
}

void wt(int x) {
    wt_integer(x);
}
void wt(ll x) {
    wt_integer(x);
}
void wt(i128 x) {
    wt_integer(x);
}
void wt(uint x) {
    wt_integer(x);
}
void wt(ull x) {
    wt_integer(x);
}
void wt(u128 x) {
    wt_integer(x);
}
void wt(double x) {
    wt_real(x);
}
void wt(long double x) {
    wt_real(x);
}

template <class T, class U> void wt(const pair<T, U> val) {
    wt(val.first);
    wt(' ');
    wt(val.second);
}
template <size_t N = 0, typename T> void wt_tuple(const T t) {
    if constexpr (N < std::tuple_size<T>::value) {
        if constexpr (N > 0) {
            wt(' ');
        }
        const auto x = std::get<N>(t);
        wt(x);
        wt_tuple<N + 1>(t);
    }
}
template <class... T> void wt(tuple<T...> tpl) {
    wt_tuple(tpl);
}
template <class T, size_t S> void wt(const array<T, S> val) {
    auto n = val.size();
    for (size_t i = 0; i < n; i++) {
        if (i)
            wt(' ');
        wt(val[i]);
    }
}
template <class T> void wt(const vector<T> val) {
    auto n = val.size();
    for (size_t i = 0; i < n; i++) {
        if (i)
            wt(' ');
        wt(val[i]);
    }
}

void print() {
    wt('\n');
}
template <class Head, class... Tail> void print(Head &&head, Tail &&...tail) {
    wt(head);
    if (sizeof...(Tail))
        wt(' ');
    print(forward<Tail>(tail)...);
}
void __attribute__((destructor)) _d() {
    flush();
}
} // namespace fastio


using fastio::flush;
using fastio::print;
using fastio::read;

inline void first(bool i = true) {
    print(i ? "first" : "second");
}
inline void Alice(bool i = true) {
    print(i ? "Alice" : "Bob");
}
inline void yes(bool i = true) {
    print(i ? "yes" : "no");
}
inline void Yes(bool i = true) {
    print(i ? "Yes" : "No");
}
inline void No() {
    print("No");
}
inline void YES(bool i = true) {
    print(i ? "YES" : "NO");
}
inline void NO() {
    print("NO");
}
inline void Yay(bool i = true) {
    print(i ? "Yay!" : ":(");
}
inline void Possible(bool i = true) {
    print(i ? "Possible" : "Impossible");
}
inline void POSSIBLE(bool i = true) {
    print(i ? "POSSIBLE" : "IMPOSSIBLE");
}

/**
 * @brief Fast IO
 */
#line 6 "Verify/LC_vertex_add_range_contour_sum_on_tree.test.cpp"

#line 2 "Graph/centroid.hpp"

class CentroidDecomposition{
    void get(int v,int p){
        sz[v]=1;
        for(auto& to:g[v])if(to!=p and !used[to]){
            get(to,v);
            sz[v]+=sz[to];
        }
    }
    int dfs(int v,int p,int rt){
        for(auto& to:g[v])if(to!=p and !used[to]){
            if(sz[to]>(sz[rt]>>1))return dfs(to,v,rt);
        }
        return v;
    }
public:
    int n;
    vector<vector<int>> g;
    vector<int> sz,used;
    CentroidDecomposition(int n_):n(n_),g(n),sz(n),used(n){}
    void add_edge(int u,int v){
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int find(int rt){
        get(rt,-1);
        int res=dfs(rt,-1,rt);
        used[res]=1;
        return res;
    }
};

/**
 * @brief Centroid Decomposition
 */
#line 2 "Graph/hld.hpp"

struct HLD{
    using P=pair<int,int>;
    vector<vector<int>> g; vector<int> sz,in,out,rev,hs,par,dist;
    void dfs(int v,int p){
        par[v]=p; sz[v]=1;
        if(p!=-1)dist[v]=dist[p]+1;
        if(!g[v].empty() and g[v][0]==p)swap(g[v][0],g[v].back());
        for(auto& to:g[v])if(to!=p){
           dfs(to,v); sz[v]+=sz[to];
           if(sz[g[v][0]]<sz[to])swap(g[v][0],to);
        }
    }
    void dfs2(int v,int p,int& k){
        in[v]=k++; rev[in[v]]=v;
        for(auto& to:g[v])if(to!=p){
            hs[to]=(g[v][0]==to?hs[v]:to);
            dfs2(to,v,k);
        }
        out[v]=k;
    }
    HLD(int _n):g(_n),sz(_n),in(_n),out(_n),rev(_n),hs(_n),par(_n),dist(_n){}
    void add_edge(int u,int v){
        g[u].emplace_back(v); g[v].emplace_back(u);
    }
    void run(int rt=0){dfs(rt,-1); hs[rt]=rt; int k=0; dfs2(rt,-1,k);}
    int lca(int u,int v){
        for(;;v=par[hs[v]]){
            if(in[u]>in[v])swap(u,v);
            if(hs[u]==hs[v])return u;
        }
    }
    vector<P> get(int u,int p,bool es=0){
        assert(in[p]<=in[u] and out[u]<=out[p]);
        vector<P> res;
        while(hs[u]!=hs[p]){
            res.push_back({in[hs[u]],in[u]+1});
            u=par[hs[u]];
        }
        res.push_back({in[p]+es,in[u]+1});
        return res;
    }
    int jump(int u,int v,int k){
        if(k<0)return -1;
        int g=lca(u,v);
        int d0=dist[u]+dist[v]-dist[g]*2;
        if(d0<k)return -1;
        int st=u;
        if(dist[u]-dist[g]<k)st=v,k=d0-k;
        for(;;){
            int to=hs[st];
            if(in[st]-k>=in[to])return rev[in[st]-k];
            k-=in[st]-in[to]+1; st=par[to];
        }
    }
};

/**
 * @brief Heavy Light Decomposition
 */
#line 4 "Graph/contour.hpp"

struct ContourQuery {
    using P = pair<int, int>;
    using T = pair<int, P>;
    ContourQuery(int _n = 0)
        : n(_n), m(_n), cd(_n), hld(_n), tree(_n * 3), depth(_n * 3),
          base(_n * 3), parent(_n * 3, -1), buf(_n * 3), width(_n * 3, 1),
          seg(_n * 3) {}
    void add_edge(int u, int v) {
        cd.add_edge(u, v);
        hld.add_edge(u, v);
    }
    vector<int> run() {
        hld.run();
        root = rec(0);
        depth[0] = 0;
        dfs(0, -1);
        rep(v, 0, m) if (v != root) { seg[v] = width[v]; }
        return seg;
    }
    vector<P> point(int v) {
        vector<P> ret;
        int cur = v;
        while (cur != root) {
            int D =
                depth[v] + depth[base[cur]] - 2 * depth[hld.lca(v, base[cur])];
            ret.push_back({cur, D});
            cur = parent[cur];
        }
        return ret;
    }
    vector<T> range(int v, int L, int R) {
        vector<T> ret;
        if (L <= 0 and 0 < R)
            ret.push_back({v, {0, 1}});
        int cur = parent[v], pre = v;
        while (pre != root) {
            int bro = -1;
            for (auto &to : tree[cur])
                if (to != parent[cur] and to != pre) {
                    bro = to;
                    break;
                }
            if (bro != -1) {
                int D = depth[v] + depth[base[bro]] -
                        2 * depth[hld.lca(v, base[bro])];
                ret.push_back(
                    {bro,
                     {clamp(L - D, 0, seg[bro]), clamp(R - D, 0, seg[bro])}});
            }
            pre = cur;
            cur = parent[cur];
        }
        return ret;
    }

  private:
    int n, m, root;
    CentroidDecomposition cd;
    HLD hld;
    vector<vector<int>> tree;
    vector<int> depth, base, parent, buf, width, seg;
    int rec(int rt) {
        int cen = cd.find(rt);
        buf[cen] = 1;
        queue<P> que;
        auto cmp = [&](int u, int v) { return buf[u] > buf[v]; };
        priority_queue<int, vector<int>, decltype(cmp)> pq{cmp};
        pq.push(cen);
        depth[cen] = 0;
        base[cen] = cen;
        for (auto &to : cd.g[cen])
            if (!cd.used[to]) {
                int v = rec(to);
                que.push({to, cen});
                depth[to] = 1;
                while (!que.empty()) {
                    auto [cur, par] = que.front();
                    que.pop();
                    width[v] = depth[cur] + 1;
                    for (auto &nxt : cd.g[cur])
                        if (nxt != par and !cd.used[nxt]) {
                            depth[nxt] = depth[cur] + 1;
                            que.push({nxt, cur});
                        }
                }
                pq.push(v);
                base[v] = cen;
            }
        cd.used[cen] = 0;
        if (pq.size() > 1) {
            for (;;) {
                int v1 = pq.top();
                pq.pop();
                int v2 = pq.top();
                pq.pop();
                int extra = m++;
                tree[extra].push_back(v1);
                tree[extra].push_back(v2);
                tree[v1].push_back(extra);
                tree[v2].push_back(extra);
                buf[extra] = buf[v1] + buf[v2];
                parent[v1] = parent[v2] = extra;
                if (pq.empty()) {
                    return extra;
                }
                pq.push(extra);
                base[extra] = cen;
                width[extra] = max(width[v1], width[v2]);
            }
        } else {
            int extra = m++;
            tree[extra].push_back(cen);
            tree[cen].push_back(extra);
            buf[extra] = 1;
            parent[cen] = extra;
            return extra;
        }
    }
    void dfs(int v, int p) {
        for (auto &to : cd.g[v])
            if (to != p) {
                depth[to] = depth[v] + 1;
                dfs(to, v);
            }
    }
};

/**
 * @brief Contour Sum Query
 */
#line 2 "DataStructure/bit.hpp"

template<typename T>struct BIT{
    int n; T all=0; vector<T> val;
    BIT(int _n=0):n(_n),val(_n+10){}
    void clear(){val.assign(n+10,0); all=T();}
    void add(int i,T x){
        for(i++;i<=n;i+=(i&-i))val[i]=val[i]+x;
        all+=x;
    }
    T sum(int i){
        T res=0;
        for(;i;i-=(i&-i))res+=val[i];
        return res;
    }
    T sum(int L,int R){return sum(R)-sum(L);} // [L,R)

    int lower_bound(T x){
        int ret=0,len=1;
        while(2*len<=n)len<<=1;
        for(;len>=1;len>>=1){
            if(ret+len<=n and val[ret+len]<x){
                ret+=len;
                x-=val[ret];
            }
        }
        return ret;
    }
};

/**
 * @brief Binary Indexed Tree
 */
#line 9 "Verify/LC_vertex_add_range_contour_sum_on_tree.test.cpp"

int main() {
    int n, q;
    read(n, q);
    vector<ll> a(n);
    read(a);
    ContourQuery buf(n);
    rep(_, 0, n - 1) {
        int u, v;
        read(u, v);
        buf.add_edge(u, v);
    }
    auto len = buf.run();
    vector<BIT<ll>> seg(len.size());
    rep(i, 0, len.size()) seg[i] = BIT<ll>(len[i]);
    rep(v, 0, n) {
        for (auto &[i, p] : buf.point(v))
            seg[i].add(p, a[v]);
    }

    while (q--) {
        int t;
        read(t);
        if (t == 0) {
            int v, x;
            read(v, x);
            for (auto &[i, p] : buf.point(v))
                seg[i].add(p, x);
        } else {
            int v, L, R;
            read(v, L, R);
            ll ret = 0;
            for (auto &[i, LR] : buf.range(v, L, R)) {
                auto [lb, rb] = LR;
                ret += seg[i].sum(lb, rb);
            }
            print(ret);
        }
    }
    return 0;
}
Back to top page