結果

問題 No.235 めぐるはめぐる (5)
ユーザー nxterunxteru
提出日時 2018-03-28 12:30:42
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,169 ms / 10,000 ms
コード長 3,171 bytes
コンパイル時間 977 ms
コンパイル使用メモリ 73,892 KB
実行使用メモリ 40,308 KB
最終ジャッジ日時 2023-09-07 19:22:35
合計ジャッジ時間 10,110 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,169 ms
39,584 KB
testcase_01 AC 1,392 ms
40,308 KB
testcase_02 AC 2,035 ms
39,748 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
typedef long long ll;
#define M 1000000007
int n,k,q,sz[200005],id[200005],vs[200005],hv[200005],hd[2000005],cn[200005],dp[200005];
ll s[2000005],c[200005];
vector<int>g[200005];
ll seg[1<<20],la[1<<20],sec[1<<20];
void dfs1(int v,int p){
    sz[v]=1;
    hv[v]=-1;
    for(int i=0;i<g[v].size();i++){
        if(g[v][i]!=p){
            dfs1(g[v][i],v);
            sz[v]+=sz[g[v][i]];
            if(hv[v]==-1||sz[hv[v]]<sz[g[v][i]])hv[v]=g[v][i];
        }
    }
}
void dfs2(int v,int p,int d,int h){
    id[v]=k;
    vs[k]=v;
    dp[k]=d;
    hd[k]=h;
    cn[k++]=cn[h];
    if(hv[v]!=-1)dfs2(hv[v],v,d+1,h);
    for(int i=0;i<g[v].size();i++){
        if(g[v][i]!=p&&g[v][i]!=hv[v]){
            cn[k]=id[v];
            dfs2(g[v][i],v,d+1,k);
        }
    }
}
void in1(int o,ll x){
    o+=(1<<19)-1;
    sec[o]=x;
    while(o>0){
        o=(o-1)/2;
        sec[o]=(sec[o*2+1]+sec[o*2+2])%M;
    }
}
void in2(int o,ll x){
    o+=(1<<19)-1;
    seg[o]+=x;
    while(o>0){
        o=(o-1)/2;
        seg[o]=(seg[o*2+1]+seg[o*2+2])%M;
    }
}
void lazy(int r,int l,int o){
    seg[o]=(seg[o]+sec[o]*la[o]%M)%M;
    if(l-r>0){
        la[o*2+1]=(la[o*2+1]+la[o])%M;
        la[o*2+2]=(la[o*2+2]+la[o])%M;
    }
    la[o]=0;
}
void add(int a,int b,int r,int l,int o,ll x){
    lazy(r,l,o);
    if(b<r||l<a)return;
    if(a<=r&&l<=b){
        la[o]=(la[o]+x)%M;
        lazy(r,l,o);
        return;
    }
    add(a,b,r,(r+l-1)/2,o*2+1,x);
    add(a,b,(r+l+1)/2,l,o*2+2,x);
    seg[o]=(seg[o*2+1]+seg[o*2+2])%M;
}
ll sum(int a,int b,int r,int l,int o){
    lazy(r,l,o);
    if(b<r||l<a)return ll(0);
    if(a<=r&&l<=b)return seg[o];
    return (sum(a,b,r,(r+l-1)/2,o*2+1)+sum(a,b,(r+l+1)/2,l,o*2+2))%M;
}
int main(void){
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%lld",s+i);
    for(int i=0;i<n;i++)scanf("%lld",c+i);
    for(int i=0;i<n-1;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        g[--a].push_back(--b);
        g[b].push_back(a);
    }
    dfs1(0,-1);
    dfs2(0,-1,0,0);
    for(int i=0;i<n;i++){
        in1(id[i],c[i]);
        in2(id[i],s[i]);
    }
    scanf("%d",&q);
    for(int i=0;i<q;i++){
        int t,u,v;
        scanf("%d%d%d",&t,&u,&v);
        u=id[u-1];v=id[v-1];
        if(t==0){
            ll z;
            scanf("%lld",&z);
            while(hd[u]!=hd[v]){
                if(dp[hd[u]]>dp[hd[v]]){
                    add(hd[u],u,0,(1<<19)-1,0,z);
                    u=cn[u];
                }else{
                    add(hd[v],v,0,(1<<19)-1,0,z);
                    v=cn[v];
                }
            }
            add(min(u,v),max(u,v),0,(1<<19)-1,0,z);
        }else{
            ll ans=0;
            while(hd[u]!=hd[v]){
                if(dp[hd[u]]>dp[hd[v]]){
                    ans=(ans+sum(hd[u],u,0,(1<<19)-1,0))%M;
                    u=cn[u];
                }else{
                    ans=(ans+sum(hd[v],v,0,(1<<19)-1,0))%M;
                    v=cn[v];
                }
            }
            ans=(ans+sum(min(u,v),max(u,v),0,(1<<19)-1,0))%M;
            printf("%lld\n",ans);
        }
    }
}
0