src/test/yosupo_vertex_add_path_sum.cpp

View this file on GitHub
Last update: 2026-03-17 19:58:42+09:00
Problem: https://judge.yosupo.jp/problem/vertex_add_path_sum

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_path_sum"
#include "../tree/hld.hpp"
#include "../structure/fenwick_tree.hpp"

int main(){
    int N,Q;
    cin>>N>>Q;
    vector<int> A(N);
    rep(i,N) cin>>A[i];
    vector<vector<int>> G(N);
    rep(i,N-1){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    HLD hld(G);
    fenwick_tree<long> bit(N);
    rep(i,N) bit.add(hld.order[i],A[i]);
    rep(i,Q){
        int t;
        cin>>t;
        if(t==0){
            int p,x;
            cin>>p>>x;
            bit.add(hld.order[p],x);
        }
        else{
            int u,v;
            cin>>u>>v;
            long cur=0;
            for(auto [l,r]: hld.path_decompose(u,v,false)){
                cur+=bit.sum(l,r);
            }
            cout<<cur<<"\n";
        }
    }
}

#line 1 "src/test/yosupo_vertex_add_path_sum.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_path_sum"
#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 3 "src/tree/hld.hpp"

struct HLD {
    vector<vector<int>> G;
    int N,T;
    vector<int> par,sub,order,head,dep;
    HLD(vector<vector<int>> G_,int root=0):G(G_),N(si(G)),T(0),par(N),sub(N),order(N),head(N),dep(N){
        dep[root]=0;
        dfs_hld(root,root);
        head[root]=root;
        dfs2(root);
    }
    void dfs_hld(int v,int p){
        par[v]=p;
        sub[v]=1;
        if(auto it=find(all(G[v]),p);it!=G[v].end()) G[v].erase(it);
        for(auto &e: G[v]){
            dep[e]=dep[v]+1;
            dfs_hld(e,v);
            sub[v]+=sub[e];
            if(sub[e]>sub[G[v][0]]) swap(e,G[v][0]);
        }
    }
    void dfs2(int v){
        order[v]=T++;
        for(auto& e: G[v]){
            head[e]=(G[v][0]==e?head[v]:e);
            dfs2(e);
        }
    }
    int lca(int u,int v){
        while(head[u]!=head[v]){
            if(order[u]<order[v]) swap(u,v);
            u=par[head[u]];
        }
        return (order[u]<order[v]?u:v);
    }

    vector<pair<int,int>> path_decompose(int u,int v,bool edge=1){
        vector<pair<int,int>> ret;
        while(head[u]!=head[v]){
            if(order[u]<order[v]) swap(u,v);
            ret.push_back({order[head[u]],order[u]+1});
            u=par[head[u]];
        }
        if(order[u]>order[v]) swap(u,v);
        ret.push_back({order[u],order[v]+(!edge)});
        return ret;
    }
    vector<pair<int,int>> up_decompose(int u,int l){
        vector<pair<int,int>> ret;
        while(head[u]!=head[l]){
            ret.emplace_back(order[head[u]],order[u]+1);
            u=par[head[u]];
        }
        if(u!=l) ret.emplace_back(order[l]+1,order[u]+1);
        return ret;
    }
};
#line 3 "src/structure/fenwick_tree.hpp"

template<class T> struct fenwick_tree {
    vector<T> a;
    fenwick_tree():a(1,0){}
    fenwick_tree(int n):a(n+1,0){}
    void add(int i,T x){
        for(i++;i<si(a);i+=i&-i) a[i]+=x;
    }
    T sum(int r){
        T s=0;
        for(;r;r-=r& -r) s+=a[r];
        return s;
    }
    T sum(int l,int r){return sum(r)-sum(l);}

    int lower_bound(T w){
        if(w<=0) return 0;
        int x=0,k=1;
        while(k<si(a))k<<=1;
        for(;k;k>>=1){
            if(x+k<si(a)&&a[x+k]<w){
                w-=a[x+k];
                x+=k;
            }
        }
        return x+1;
    }
};
#line 4 "src/test/yosupo_vertex_add_path_sum.cpp"

int main(){
    int N,Q;
    cin>>N>>Q;
    vector<int> A(N);
    rep(i,N) cin>>A[i];
    vector<vector<int>> G(N);
    rep(i,N-1){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    HLD hld(G);
    fenwick_tree<long> bit(N);
    rep(i,N) bit.add(hld.order[i],A[i]);
    rep(i,Q){
        int t;
        cin>>t;
        if(t==0){
            int p,x;
            cin>>p>>x;
            bit.add(hld.order[p],x);
        }
        else{
            int u,v;
            cin>>u>>v;
            long cur=0;
            for(auto [l,r]: hld.path_decompose(u,v,false)){
                cur+=bit.sum(l,r);
            }
            cout<<cur<<"\n";
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	1254 ms	130 MB
g++	almost_line_01	AC	1209 ms	126 MB
g++	example_00	AC	5 ms	4 MB
g++	line_00	AC	1137 ms	125 MB
g++	line_01	AC	1131 ms	139 MB
g++	long-path-decomposition_killer_00	AC	971 ms	97 MB
g++	max_random_00	AC	1725 ms	98 MB
g++	max_random_01	AC	1711 ms	98 MB
g++	max_random_02	AC	1690 ms	98 MB
g++	random_00	AC	1286 ms	77 MB
g++	random_01	AC	1518 ms	91 MB
g++	random_02	AC	600 ms	13 MB
g++	random_03	AC	709 ms	85 MB
g++	random_04	AC	603 ms	56 MB
g++	small_00	AC	7 ms	4 MB
g++	small_01	AC	6 ms	4 MB
g++	small_02	AC	5 ms	4 MB
g++	small_03	AC	5 ms	4 MB
g++	small_04	AC	6 ms	4 MB