#1173790 (C++23) No.235 めぐるはめぐる (5)

• 問題: No.235 めぐるはめぐる (5)
• ユーザー: ZeriToki
• 提出日時: 2026-07-26 20:26:22
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 1,446 ms / 10,000 ms
• コード長: 7,919 bytes
• コンパイル時間: 3,292 ms
• コンパイル使用メモリ: 364,324 KB
• 実行使用メモリ: 40,796 KB
• 最終ジャッジ日時: 2026-07-26 20:26:33
• 合計ジャッジ時間: 9,552 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
other	AC * 3

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
const long long mod=998244353;
const long long mod2=469762049;
const long long mod100=1000000007;
struct HLD{
    //0-indexed
    //根が0の根付き木で実装
    vector<int>V;//入りがけ順
    vector<int>id;//頂点iがどこにあるか
    vector<int>head;//頂点iが属するheavy pathの親
    vector<int>child;//頂点iが属するheavy pathの子
    vector<vector<int>>G;//グラフ
    vector<int>subtree;//部分木サイズ
    vector<int>parent;//自分の親

    //初期化
    HLD(int N){
        id.assign(N,-1);
        head.assign(N,-1);
        child.assign(N,-1);
        subtree.assign(N,-1);
        parent.assign(N,-1);
        G.assign(N,{});
    }

    //辺の追加
    void add_edge(int u,int v){
        G[u].push_back(v);
        G[v].push_back(u);
    }

    //テーブルの作成。辺を追加した後にやる
    void make_table(){
        auto dfs1=[&](auto &dfs1,int pos,int last)->void {
            subtree[pos]=1;
            for(auto nex:G[pos]){
                if(nex==last) continue;
                parent[nex]=pos;
                dfs1(dfs1,nex,pos);
                subtree[pos]+=subtree[nex];
            }
            return;
        };
        dfs1(dfs1,0,-1);
        auto dfs2=[&](auto &dfs2,int pos,int last,int h)->int {
            id[pos]=(int)V.size();
            V.push_back(pos);
            head[pos]=h;
            pair<int,int>priority={-1,-1};
            for(auto nex:G[pos]){
                if(nex==last) continue;
                if(priority<make_pair(subtree[nex],nex)){
                    priority=make_pair(subtree[nex],nex);
                }
            }
            if(priority.second==-1){
                child[pos]=pos;
                return pos;
            }
            child[pos]=dfs2(dfs2,priority.second,pos,h);
            for(auto nex:G[pos]){
                if(nex==last) continue;
                if(priority.second==nex) continue;
                dfs2(dfs2,nex,pos,nex);
            }
            return child[pos];
        };
        dfs2(dfs2,0,-1,0);
        return;
    }
    
    //LCAを求める
    int LCA(int u,int v){
        while(true){
            if(head[u]==head[v]){
                if(id[u]>id[v]) return v;
                else return u;
            }
            if(id[u]>id[v]){
                u=parent[head[u]];
            }
            else{
                v=parent[head[v]];
            }
        }
    }
};

template<typename T,typename F> struct lazysegtree{
    using F1=function<T(T,T)>;
    using F2=function<T(T,F)>;
    using F3=function<F(F,F)>;
    vector<T>node;
    vector<F>lazy;
    int N;int log;F1 op;T e;F2 mapping;F3 composition;F id;
    lazysegtree(int n,F1 op,T e,F2 mapping,F3 composition,F id)
    :op(op),e(e),mapping(mapping),composition(composition),id(id){
        N=1;
        log=1;
        while(N<=n){
            N<<=1;
            log++;
        }
        node.assign(N*2,e);
        lazy.assign(N*2,id);
    }
    void set(int p,T x){
        int pos=1;
        for(int i=log-2;i>=0;i--){
            lazy[pos*2]=composition(lazy[pos*2],lazy[pos]);
            lazy[pos*2+1]=composition(lazy[pos*2+1],lazy[pos]);
            node[pos*2]=mapping(node[pos*2],lazy[pos]);
            node[pos*2+1]=mapping(node[pos*2+1],lazy[pos]);
            lazy[pos]=id;
            pos<<=1;
            if((p>>i)&1) pos++;
        }
        lazy[pos]=id;
        node[pos]=x;
        while(pos>=2){
            pos/=2;
            node[pos]=op(node[pos*2],node[pos*2+1]);
        }
        return;
    }
    void apply(int l,int r,int a,int b,int u,F f){
        if(b<=l || r<=a) return;
        if(l<=a && b<=r){
            lazy[u]=composition(lazy[u],f);
            node[u]=mapping(node[u],f);
            return;
        }
        lazy[u*2]=composition(lazy[u*2],lazy[u]);
        lazy[u*2+1]=composition(lazy[u*2+1],lazy[u]);
        node[u*2]=mapping(node[u*2],lazy[u]);
        node[u*2+1]=mapping(node[u*2+1],lazy[u]);
        lazy[u]=id;
        int m=(a+b)/2;
        apply(l,r,a,m,u*2,f);
        apply(l,r,m,b,u*2+1,f);
        node[u]=op(node[u*2],node[u*2+1]);
        return;
    }
    void apply(int l,int r,F f){//[l,r)を変更
        l++;r++;
        apply(l,r,1,N+1,1,f);
    }
    void apply(int p,F f){
        p++;
        apply(p,p+1,1,N+1,1,f);
    }
    T fold(int l,int r,int a,int b,int u){
        if(b<=l || r<=a)return e;
        if(l<=a && b<=r){
            return node[u];
        }
        int m=(a+b)/2;
        T L=mapping(fold(l,r,a,m,u*2),lazy[u]);
        T R=mapping(fold(l,r,m,b,u*2+1),lazy[u]);
        return op(L,R);
    }
    T fold(int l,int r){//[l,r)をを求める
        l++;r++;
        return fold(l,r,1,N+1,1);
    }
    T fold(int p){
        p++;
        return fold(p,p+1,1,N+1,1);
    }
};


struct D{
    ll ans,infr;
};
D e(){
    D res;
    res.ans=0;
    res.infr=0;
    return res;
}
D op(D a,D b){
    D res;
    res.ans=a.ans+b.ans;
    res.infr=a.infr+b.infr;
    res.ans%=mod100;
    res.infr%=mod100;
    return res;
}
D mapping(D x,ll f){
    x.ans+=x.infr*f;
    x.ans%=mod100;
    return x;
}
ll composition(ll f,ll g){
    return (f+g)%mod100;
}


int main(){
    cout.tie()->sync_with_stdio(0);
    cin.tie(0);
    
    int N;cin>>N;
    HLD H(N);
    ll S[N],C[N];
    for(int i=0;i<N;i++) cin>>S[i];
    for(int i=0;i<N;i++) cin>>C[i];
    int A[N-1],B[N-1];
    for(int i=0;i<N-1;i++){
        cin>>A[i]>>B[i];
        A[i]--;B[i]--;
        H.add_edge(A[i],B[i]);
    }
    H.make_table();
    int Q;cin>>Q;
    int query[Q],X[Q],Y[Q];
    ll Z[Q];
    for(int i=0;i<Q;i++){
        cin>>query[i]>>X[i]>>Y[i];
        X[i]--;Y[i]--;
        if(query[i]==0) cin>>Z[i];
    }

    lazysegtree<D,ll>seg(N,op,e(),mapping,composition,0LL);
    for(int i=0;i<N;i++){
        D now;
        now.ans=S[i];
        now.infr=C[i];
        seg.set(H.id[i],now);
    }


    auto solve1=[&](int x,int y,ll z){
        int a=H.LCA(x,y);
        while(true){
            if(H.head[x]==H.head[a]){
                seg.apply(H.id[a],H.id[x]+1,z);
                break;
            }
            int goal=H.head[x];
            seg.apply(H.id[goal],H.id[x]+1,z);
            x=H.parent[goal];
        }

        while(true){
            if(H.head[y]==H.head[a]){
                seg.apply(H.id[a]+1,H.id[y]+1,z);
                break;
            }
            int goal=H.head[y];
            seg.apply(H.id[goal],H.id[y]+1,z);
            y=H.parent[goal];
        }
        return;
    };
    auto solve2=[&](int x,int y){
        ll res=0;
        int a=H.LCA(x,y);
        //cout<<x<<" "<<y<<" "<<a<<endl;
        while(true){
            if(H.head[x]==H.head[a]){
                res+=seg.fold(H.id[a],H.id[x]+1).ans;
                break;
            }
            int goal=H.head[x];
            res+=seg.fold(H.id[goal],H.id[x]+1).ans;
            res%=mod100;
            x=H.parent[goal];
        }
        while(true){
            if(H.head[y]==H.head[a]){
                res+=seg.fold(H.id[a]+1,H.id[y]+1).ans;
                break;
            }
            int goal=H.head[y];
            //cout<<res<<" "<<y<<" "<<goal<<endl;
            //cout<<seg.fold(H.id[goal],H.id[y]+1).infr<<endl;
            res+=seg.fold(H.id[goal],H.id[y]+1).ans;
            res%=mod100;
            y=H.parent[goal];
        }
        res%=mod100;
        return res;
    };
    ll ans=0;
    for(int i=0;i<Q;i++){
        if(query[i]==0){
            solve1(X[i],Y[i],Z[i]);
        }
        else{
            ans=solve2(X[i],Y[i]);
            ans%=mod100;
            cout<<ans<<endl;
        }
    }
}