verify/tree/link-cut-tree/dynamic_tree_vertex_add_path_sum.test.cpp

• View this file on GitHub
• Last update: 2025-07-19 14:29:34+09:00
• Problem: https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum

Depends on

• src/contest/template.hpp
• src/tree/link-cut-tree.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum"
#include "src/contest/template.hpp"
#include "src/tree/link-cut-tree.hpp"

const int N=2e5+5;

int n,q;
ll a[N];
LinkCutTree<N,ll> lct;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> q;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        lct.set(i,a[i]);
    }
    for(int i=0;i<n-1;i++){
        int u,v;
        cin >> u >> v;
        u++,v++;
        lct.link(u,v);
    }
    while(q--){
        int op;
        cin >> op;
        if(op==0){
            int u,v,x,y;
            cin >> u >> v >> x >> y;
            u++,v++,x++,y++;
            lct.cut(u,v);
            lct.link(x,y);
        }else if(op==1){
            int u,x;
            cin >> u >> x;
            u++;
            lct.set(u,a[u]+=x);
        }else{
            int u,v;
            cin >> u >> v;
            u++,v++;
            cout << lct.aggregate(u,v) << "\n";
        }
    }
}

#line 1 "verify/tree/link-cut-tree/dynamic_tree_vertex_add_path_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum"
#line 2 "src/contest/template.hpp"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
using ll = long long;
using db = long double;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<db,db>;
const int INF=0x3fffffff;
const ll LINF=0x1fffffffffffffff;
const db DINF=numeric_limits<db>::infinity();
const db EPS=1e-9;
const db PI=acos(db(-1));
 
template<class T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
#line 2 "src/tree/link-cut-tree.hpp"

/**
 * Author: Teetat T.
 * Description: Link Cut Tree (1-indexed)
 */

template<int N,class T>
struct LinkCutTree{
    int ch[N][2],par[N],lz[N],rev[N];
    T val[N],sum[N],rsum[N];
    void toggle(int v){
        if(!v)return;
        swap(ch[v][0],ch[v][1]);
        swap(sum[v],rsum[v]);
        rev[v]^=1;
    }
    void push(int v){
        if(!v||!rev[v])return;
        toggle(ch[v][0]);
        toggle(ch[v][1]);
        rev[v]=0;
    }
    void pull(int v){
        if(!v)return;
        sum[v]=sum[ch[v][0]]+val[v]+sum[ch[v][1]];
        rsum[v]=rsum[ch[v][0]]+val[v]+rsum[ch[v][1]];
    }
    bool is_root(int v){
        return ch[par[v]][0]!=v&&ch[par[v]][1]!=v;
    }
    bool pos(int v){
        return ch[par[v]][1]==v;
    }
    void rotate(int v){
        int u=par[v],g=par[u];
        bool x=pos(v);
        if(!is_root(u))ch[g][pos(u)]=v;
        ch[u][x]=ch[v][!x];
        if(ch[u][x])par[ch[u][x]]=u;
        ch[v][!x]=u,par[u]=v,par[v]=g;
        pull(u),pull(v);
    }
    void splay(int v){
        if(!v)return;
        for(push(v);!is_root(v);rotate(v)){
            int u=par[v];
            if(is_root(u))push(u),push(v);
            else push(par[u]),push(u),push(v),rotate(pos(u)==pos(v)?u:v);
        }
    }
    void access(int v){
        for(int u=v,c=0;u;u=par[u]){
            splay(u);
            ch[u][1]=c;
            pull(c=u);
        }
        splay(v);
    }
    void evert(int v){
        access(v),toggle(v);
    }
    void link(int u,int v){
        evert(u);
        access(v);
        par[u]=v;
    }
    void cut(int u,int v){
        evert(u);
        access(v);
        assert(par[u]==v);
        ch[v][0]=par[u]=0;
        pull(v);
    }
    T aggregate(int u,int v){
        evert(u);
        access(v);
        return sum[v];
    }
    void set(int u,T v){
        evert(u);
        val[u]=v;
        pull(u);
    }
};
#line 4 "verify/tree/link-cut-tree/dynamic_tree_vertex_add_path_sum.test.cpp"

const int N=2e5+5;

int n,q;
ll a[N];
LinkCutTree<N,ll> lct;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> q;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        lct.set(i,a[i]);
    }
    for(int i=0;i<n-1;i++){
        int u,v;
        cin >> u >> v;
        u++,v++;
        lct.link(u,v);
    }
    while(q--){
        int op;
        cin >> op;
        if(op==0){
            int u,v,x,y;
            cin >> u >> v >> x >> y;
            u++,v++,x++,y++;
            lct.cut(u,v);
            lct.link(x,y);
        }else if(op==1){
            int u,x;
            cin >> u >> x;
            u++;
            lct.set(u,a[u]+=x);
        }else{
            int u,v;
            cin >> u >> v;
            u++,v++;
            cout << lct.aggregate(u,v) << "\n";
        }
    }
}

Back to top page