結果

問題 No.235 めぐるはめぐる (5)
ユーザー momoyuumomoyuu
提出日時 2023-03-21 21:34:54
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,352 ms / 10,000 ms
コード長 6,263 bytes
コンパイル時間 4,143 ms
コンパイル使用メモリ 266,540 KB
実行使用メモリ 36,304 KB
最終ジャッジ日時 2023-10-18 18:35:52
合計ジャッジ時間 13,808 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,352 ms
35,776 KB
testcase_01 AC 1,507 ms
36,304 KB
testcase_02 AC 2,097 ms
35,776 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

//const ll mod = 998'244'353;
const ll mod = 1'000'000'007;
//const ll mod = 67'280'421'310'721;
struct mint{
    long long x;
    mint(long long x=0):x((x%mod+mod)%mod){}
    mint operator-() const{
        return mint(-x);
    }
    mint& operator+=(const mint& a){
        if((x+=a.x)>=mod)x-=mod;
        return *this;
    }
    mint& operator-=(const mint& a){
        if((x+=mod-a.x)>=mod)x-=mod;
        return *this;
    }
    mint& operator*=(const  mint& a){
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint& a) const{
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const{
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const{
        mint res(*this);
        return res*=a;
    }
    mint pow(long long n) const {
        assert(0 <= n);
        mint a = *this, r = 1;
        while (n) {
            if (n & 1) r *= a;
            a *= a;
            n >>= 1;
        }
        return r;
    }
    mint inv() const{
        return pow(mod-2);
    }
    mint& operator/=(const mint& a){
        return (*this)*=a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }
    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
    bool operator==(const mint& a) const {
        return x == a.x;
    }
    bool operator<(const mint& a) const{
        return x < a.x;
    }
};

template< typename T1, typename T2 = T1 >
struct lazysegtree{
    using F1 = function<T1(T1,T1)>;
    using F2 = function<T2(T2,T2)>;
    //using F3 = function<T1(T2,T1)>;
    using F3 = function<T1(T2,T1,int,int)>;
    int n;
    F1 f1;
    F2 f2;
    F3 f3;
    T1 e1;
    T2 e2,e3;
    vector<T1> data;
    vector<T2> lazy;//莨晄成繝・・繧ｿ
    vector<int> p;//莨晄成縺ｮ繝輔Λ繧ｰW
    /*
     * n:鬆らせ謨ｰ
     * f1:隕∫ｴ蜷悟｣ｫ縺ｮ貍皮ｮ・f2:菴懃畑邏蜷悟｣ｫ,f3:菴懃畑
     * e:蜊倅ｽ榊・
     */
    lazysegtree(int _n,F1 f1,F2 f2,F3 f3,T1 e1,T2 e2,T2 e3):f1(f1),f2(f2),f3(f3),e1(e1),e2(e2),e3(e3){
        n = 1;
        while(n<_n) n<<=1;
        data.assign(2*n,e1);
        lazy.assign(2*n,e3);
        p.assign(2*n,0);
    }

    void set(int i,T1 x){
        data[i+n-1] = x;
    }


    void build(){
        for(int i = n - 2;i>=0;i--){
            data[i] = f1(data[2*i+1],data[2*i+2]);
        }
    }

    void rangeupdate(T2 x,int a,int b,int ni,int l,int r){
        update(ni,l,r);
        if(b<=l||r<=a) return;
        if(a<=l&&r<=b){
            p[ni] = 1;
            lazy[ni] = f2(x,lazy[ni]);
            update(ni,l,r);
        }else{
            rangeupdate(x,a,b,2*ni+1,l,(l+r)/2);
            rangeupdate(x,a,b,2*ni+2,(l+r)/2,r);
            if(l+1<r) data[ni] = f1(data[2*ni+1],data[2*ni+2]);
        }
    }

    void rangeupdate(T2 x,int a,int b){
        rangeupdate(x,a,b,0,0,n);
    }

    void update(int ni,int l,int r){
        if(!p[ni])return;
        p[ni] = 0;
        //data[ni] = f3(lazy[ni],data[ni]);
        data[ni] = f3(lazy[ni],data[ni],l,r);
        if(l+1<r){
            p[2*ni+1] = 1;
            p[2*ni+2] = 1;
            lazy[2*ni+1] = f2(lazy[ni],lazy[2*ni+1]);
            lazy[2*ni+2] = f2(lazy[ni],lazy[2*ni+2]);
        }
        lazy[ni] = e3;
    }

    T1 query(int a,int b,int ni,int l,int r){
        update(ni,l,r);
        if(b<=l||r<=a) return e1;
        if(a<=l&&r<=b) return data[ni];
        else return f1(query(a,b,2*ni+1,l,(l+r)/2),query(a,b,2*ni+2,(r+l)/2,r));
    }

    T1 query(int a,int b){
        return query(a,b,0,0,n);
    }

    T1 operator[](const int i) const {
        return data[i+n-1];
    }
};


const int mx = 2e5 + 10;
int in[mx],out[mx],par[mx],head[mx],sz[mx];
vector<int> g[mx];
int n;
pair<mint,mint> c1(pair<mint,mint> a,pair<mint,mint> b){
    a.first += b.first;
    a.second += b.second;
    return a;
}
mint c2(mint a,mint b){
    return a + b;
}
pair<mint,mint> c3(mint a,pair<mint,mint> b,ll l,ll r){
    b.first += a * b.second;
    return b;
}

int sdfs(int ni,int p){
    sz[ni] = 1;
    par[ni] = p;
    if(g[ni].size()&&g[ni][0]==p) swap(g[ni][0],g[ni].back());
    for(auto&to:g[ni]){
        if(to==p) continue;
        sz[ni] += sdfs(to,ni);
        if(sz[to]>sz[g[ni][0]]) swap(to,g[ni][0]);
    }
    return sz[ni];
}

void hdfs(int ni,int p,int&time){
    in[ni] = time++;
    for(auto&to:g[ni]){
        if(to==p) continue;
        head[to] = (g[ni][0]==to?head[ni]:to);
        hdfs(to,ni,time);
    }
    out[ni] = time;
}

int main(){
    cin>>n;
    vector<mint> s(n),c(n);
    for(int i = 0;i<n;i++){
        ll x;cin>>x;
        s[i] = mint(x);
    }
    for(int i = 0;i<n;i++){
        ll x;
        cin>>x;
        c[i] = mint(x);
    }
    for(int i = 1;i<n;i++){
        int u,v;
        cin>>u>>v;
        u--;v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    lazysegtree<pair<mint,mint>,mint> seg(n,c1,c2,c3,make_pair(mint(0),mint(0)),mint(0),mint(0));
    sdfs(0,-1);
    int time = 0;
    hdfs(0,-1,time);
    for(int i = 0;i<n;i++) seg.set(in[i],make_pair(s[i],c[i]));
    int q;
    cin>>q;
    seg.build();
    while(q--){
        int t;
        cin>>t;
        if(t==0){
            int u,v;ll z;
            cin>>u>>v>>z;
            u--;v--;
            for(;;v=par[head[v]]){
                if(in[u]>in[v]) swap(u,v);
                if(head[u]==head[v]) break;
                seg.rangeupdate(mint(z),in[head[v]],in[v]+1);
            }
            seg.rangeupdate(mint(z),in[u],in[v]+1);
        }else{
            mint ans = 0;
            int u,v;
            cin>>u>>v;
            u--;v--;
            //cout<<u<<" "<<v<<endl;
            for(;;v=par[head[v]]){
                if(in[u]>in[v]) swap(u,v);
                if(head[u]==head[v]) break;
                auto itr = seg.query(in[head[v]],in[v]+1);
                ans += itr.first;
                //cout<<itr.first<<endl;
            }
            auto itr = seg.query(in[u],in[v]+1);
            ans += itr.first;
            //cout<<itr.first<<endl;
            cout<<ans<<endl;
        }
    }
}
0