結果

問題 No.235 めぐるはめぐる (5)
ユーザー latte0119latte0119
提出日時 2015-10-31 16:18:45
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 4,002 bytes
コンパイル時間 1,221 ms
コンパイル使用メモリ 86,108 KB
実行使用メモリ 60,516 KB
最終ジャッジ日時 2023-10-11 07:14:28
合計ジャッジ時間 5,703 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘long long int hl_init()’:
main.cpp:108:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

ソースコード

diff # 

#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
#include<cassert>
#define int long long
using namespace std;
typedef pair<int,int>pint;
typedef vector<int>vint;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);i++)
template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}
const int mod=1000000007;
struct seg_tree{
    int N;
    vint dat,sum,lazy;
    void init(vint &s,vint &c){
        N=1;
        while(N<s.size())N*=2;
        dat.assign(N*2-1,0);
        sum.assign(N*2-1,0);
        lazy.assign(N*2-1,0);
        rep(i,s.size()){
            dat[i+N-1]=s[i];
            sum[i+N-1]=c[i];
        }
        for(int i=N-2;i>=0;i--){
            dat[i]=(dat[i*2+1]+dat[i*2+2])%mod;
            sum[i]=(sum[i*2+1]+dat[i*2+2])%mod;
        }
    }
    inline void evaluate(int k){
        dat[k]=(dat[k]+sum[k]*lazy[k])%mod;
        if(k<N-1){
            lazy[k*2+1]=(lazy[k*2+1]+lazy[k])%mod;
            lazy[k*2+2]=(lazy[k*2+2]+lazy[k])%mod;
        }
        lazy[k]=0;
    }
    inline void update(int k){
        dat[k]=(dat[k*2+1]+dat[k*2+2])%mod;
    }
    void add(int a,int b,int x){add(a,b,x,0,0,N);}
    void add(int a,int b,int x,int k,int l,int r){
        evaluate(k);
        if(r<=a||b<=l)return;
        if(a<=l&&r<=b){
            lazy[k]=(lazy[k]+x+mod)%mod;
            evaluate(k);
            return;
        }
        add(a,b,x,k*2+1,l,(l+r)/2);
        add(a,b,x,k*2+2,(l+r)/2,r);
        update(k);
    }
    int get(int a,int b){return get(a,b,0,0,N);}
    int get(int a,int b,int k,int l,int r){
        evaluate(k);
        if(r<=a||b<=l)return 0;
        if(a<=l&&r<=b)return dat[k];
        return (get(a,b,k*2+1,l,(l+r)/2)+get(a,b,k*2+2,(l+r)/2,r))%mod;
    }
};
const int SIZE=200000;
int N,Q;
int S[SIZE],C[SIZE];
vint G[SIZE];

int par[SIZE],depth[SIZE],heavy[SIZE];
int head[SIZE],chain[SIZE];
vector<seg_tree>seg;

int hl_dfs(int v,int p,int d){
    par[v]=p;
    depth[v]=d;
    heavy[v]=-1;

    int ma=0,sum=0;
    rep(i,G[v].size()){
        int to=G[v][i];
        if(to==p)continue;
        int val=hl_dfs(to,v,d+1);
        if(ma<val){
            ma=val;
            heavy[v]=to;
        }
        sum+=val;
    }
    return sum+1;
}

int hl_init(){
    hl_dfs(0,-1,0);
    rep(i,N){
        if(par[i]>=0&&heavy[par[i]]==i)continue;
        vint s,c;
        for(int j=i;~j;j=heavy[j]){
            head[j]=i;
            chain[j]=seg.size();
            s.pb(S[j]);
            c.pb(C[j]);
        }
        seg.pb(seg_tree());
        seg.back().init(s,c);
    }
}

int lca(int u,int v){
    while(chain[u]!=chain[v]){
        if(depth[head[u]]<depth[head[v]])swap(u,v);
        u=par[head[u]];
    }
    return depth[u]<depth[v]?u:v;
}

void add(int v,int x){
    while(~v){
        seg[chain[v]].add(0,depth[v]-depth[head[v]]+1,x);
        v=par[head[v]];
    }
}

int get(int v){
    int ret=0;
    while(~v){
        ret+=seg[chain[v]].get(0,depth[v]-depth[head[v]]+1);
        v=par[head[v]];
        ret%=mod;
    }
    return ret;
}

signed main(){
    scanf("%lld",&N);
    rep(i,N)scanf("%lld",&S[i]);
    rep(i,N)scanf("%lld",&C[i]);

    rep(i,N-1){
        int a,b;
        scanf("%lld%lld",&a,&b);
        a--;b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    hl_init();

    scanf("%lld",&Q);
    while(Q--){
        int type;
        scanf("%lld",&type);
        if(type==0){
            int x,y,z;
            scanf("%lld%lld%lld",&x,&y,&z);
            x--;y--;
            int p=lca(x,y);
            add(x,z);
            add(y,z);
            add(p,-z);
            if(par[p]>=0)add(par[p],-z);
        }
        else{
            int x,y;
            scanf("%lld%lld",&x,&y);
            x--;y--;
            int p=lca(x,y);
            int ans=get(x)+get(y)-get(p);
            if(par[p]>=0)ans-=get(par[p]);
            ans=(ans+mod*100)%mod;
            printf("%lld\n",ans);
        }
    }
    return 0;
}
0