src/test/yosupo_vertex_set_path_composite.cpp

• View this file on GitHub
• Last update: 2026-03-15 19:44:39+09:00
• Problem: https://judge.yosupo.jp/problem/vertex_set_path_composite

Depends on

• src/math/modint.hpp
• src/segtree/segtree.hpp
• src/template.hpp
• src/tree/hld.hpp

Code

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

#include "../math/modint.hpp"
#include "../segtree/segtree.hpp"
#include "../tree/hld.hpp"

using mint=modint<>;

struct S {
    pair<mint,mint> l,r;
    S(int a=1,int b=0){
        l.fi=r.fi=a;
        l.se=r.se=b;
    }
};
S op(S l,S r){
    S s;
    s.l.fi=l.l.fi*r.l.fi;
    s.l.se=l.l.se*r.l.fi+r.l.se;
    s.r.fi=l.r.fi*r.r.fi;
    s.r.se=r.r.se*l.r.fi+l.r.se;
    return s;
}
S e(){
    return {1,0};
}

int main(){
    int N,Q;
    cin>>N>>Q;
    vector<int> A(N),B(N);
    rep(i,N) cin>>A[i]>>B[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);
    }
    segtree<S,op,e> seg(N);
    HLD hld(G);
    rep(i,N) seg.set(hld.order[i],S(A[i],B[i]));
    while(Q--){
        int t;
        cin>>t;
        if(t==0){
            int p,c,d;
            cin>>p>>c>>d;
            seg.set(hld.order[p],S(c,d));
        }
        else{
            int u,v,x;
            cin>>u>>v>>x;
            int l=hld.lca(u,v);

            S s=seg.get(hld.order[l]);
            for(auto [l,r]:hld.up_decompose(u,l)|views::reverse){
                s=op(s,seg.prod(l,r));
            }
            swap(s.l,s.r);
            for(auto [l,r]:hld.up_decompose(v,l)|views::reverse){
                s=op(s,seg.prod(l,r));
            }
            cout<<s.l.fi*x+s.l.se<<"\n";
        }
    }
}

#line 1 "src/test/yosupo_vertex_set_path_composite.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_set_path_composite"

#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/math/modint.hpp"

template<int mod=998244353> struct modint {
    int x;
    constexpr modint(long long x_=0):x(((x_%mod)+mod)%mod){}
    constexpr modint operator-(){
        auto res=*this;
        res.x=(x?mod-x:0);
        return res;
    }
    constexpr modint& operator+=(modint r){
        if((x+=r.x)>=mod) x-=mod;
        return *this;
    }
    constexpr modint& operator-=(modint r){
        if((x-=r.x)<0) x+=mod;
        return *this;
    }
    constexpr modint& operator*=(modint r){
        x=1ll*x*r.x%mod;
        return *this;
    }
    constexpr modint& operator/=(modint r){return *this*=r.inv();}
    constexpr friend modint operator+(modint a,modint b){return a+=b;}
    constexpr friend modint operator-(modint a,modint b){return a-=b;}
    constexpr friend modint operator*(modint a,modint b){return a*=b;}
    constexpr friend modint operator/(modint a,modint b){return a/=b;}
    constexpr modint inv() const {return pow(mod-2);}
    constexpr modint pow(long long b) const {
        assert(0<=b);
        modint a=*this,c=1;
        while(b){
            if(b&1) c*=a;
            a*=a;
            b>>=1;
        }
        return c;
    }
    constexpr int val() const {return x;}
    constexpr friend ostream& operator<<(ostream& os,const modint& m){return os<<m.val();}
    constexpr friend istream& operator>>(istream& is,modint& m){
        long long v;
        is>>v;
        m=modint(v);
        return is;
    }
};
#line 3 "src/segtree/segtree.hpp"

template<class S,S (*op)(S,S),S (*e)()> struct segtree {
    int n;
    vector<S> d;
    segtree():segtree(1){}
    explicit segtree(int n_):segtree(vector<S>(n_,e())){}
    explicit segtree(const vector<S>& a):n(__bit_ceil(a.size())),d(n*2,e()){
        rep(i,si(a)) d[n+i]=a[i];
        for(int i=n;--i;) d[i]=op(d[i*2],d[i*2+1]);
    }
    void set(int i,S x){
        for(d[i+=n]=x;i>>=1;) d[i]=op(d[i*2],d[i*2+1]);
    }
    S get(int i){return d[i+n];}
    S prod(int l,int r){
        S L=e(),R=e();
        for(l+=n,r+=n;l<r;l>>=1,r>>=1){
            if(l&1) L=op(L,d[l++]);
            if(r&1) R=op(d[--r],R);
        }
        return op(L,R);
    }
    template<typename F> int max_right(int l,F f) const {
        if(l==n) return n;
        l+=n;
        S sm=e();
        do {
            while(~l&1) l>>=1;
            if(!f(op(sm,d[l]))){
                while(l<n){
                    l<<=1;
                    if(f(op(sm,d[l]))) sm=op(sm,d[l++]);
                }
                return l-n;
            }
            sm=op(sm,d[l++]);
        } while((l& -l)!=l);
        return n;
    }
    template<typename F> int min_left(int r,F f) const {
        if(!r) return 0;
        r+=n;
        S sm=e();
        do {
            r--;
            while(r>1 and r&1) r>>=1;
            if(!f(op(d[r],sm))){
                while(r<n){
                    r=(2*r+1);
                    if(f(op(d[r],sm))) sm=op(d[r--],sm);
                }
                return r+1-n;
            }
            sm=op(d[r],sm);
        } while((r& -r)!=r);
        return 0;
    }
};

template<class T> using SegtreeFrom=segtree<typename T::S,T::op,T::e>;
#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 6 "src/test/yosupo_vertex_set_path_composite.cpp"

using mint=modint<>;

struct S {
    pair<mint,mint> l,r;
    S(int a=1,int b=0){
        l.fi=r.fi=a;
        l.se=r.se=b;
    }
};
S op(S l,S r){
    S s;
    s.l.fi=l.l.fi*r.l.fi;
    s.l.se=l.l.se*r.l.fi+r.l.se;
    s.r.fi=l.r.fi*r.r.fi;
    s.r.se=r.r.se*l.r.fi+l.r.se;
    return s;
}
S e(){
    return {1,0};
}

int main(){
    int N,Q;
    cin>>N>>Q;
    vector<int> A(N),B(N);
    rep(i,N) cin>>A[i]>>B[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);
    }
    segtree<S,op,e> seg(N);
    HLD hld(G);
    rep(i,N) seg.set(hld.order[i],S(A[i],B[i]));
    while(Q--){
        int t;
        cin>>t;
        if(t==0){
            int p,c,d;
            cin>>p>>c>>d;
            seg.set(hld.order[p],S(c,d));
        }
        else{
            int u,v,x;
            cin>>u>>v>>x;
            int l=hld.lca(u,v);

            S s=seg.get(hld.order[l]);
            for(auto [l,r]:hld.up_decompose(u,l)|views::reverse){
                s=op(s,seg.prod(l,r));
            }
            swap(s.l,s.r);
            for(auto [l,r]:hld.up_decompose(v,l)|views::reverse){
                s=op(s,seg.prod(l,r));
            }
            cout<<s.l.fi*x+s.l.se<<"\n";
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	1332 ms	55 MB
g++	almost_line_01	AC	1309 ms	57 MB
g++	example_00	AC	5 ms	4 MB
g++	example_01	AC	5 ms	4 MB
g++	line_00	AC	1262 ms	60 MB
g++	line_01	AC	1264 ms	61 MB
g++	long-path-decomposition_killer_00	AC	1207 ms	50 MB
g++	max_random_00	AC	1490 ms	50 MB
g++	max_random_01	AC	1478 ms	50 MB
g++	max_random_02	AC	1466 ms	50 MB
g++	random_00	AC	994 ms	32 MB
g++	random_01	AC	1116 ms	41 MB
g++	random_02	AC	613 ms	16 MB
g++	small_00	AC	10 ms	4 MB
g++	small_01	AC	8 ms	4 MB
g++	small_02	AC	7 ms	4 MB
g++	small_03	AC	11 ms	4 MB
g++	small_04	AC	8 ms	4 MB
g++	worst_for_path_decomposition_00	AC	3986 ms	51 MB
g++	worst_for_path_decomposition_01	AC	4138 ms	51 MB

Back to top page