結果

問題 No.235 めぐるはめぐる (5)
ユーザー TAISA_TAISA_
提出日時 2018-11-13 23:18:23
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,342 ms / 10,000 ms
コード長 3,962 bytes
コンパイル時間 2,105 ms
コンパイル使用メモリ 188,448 KB
実行使用メモリ 35,200 KB
最終ジャッジ日時 2024-06-06 19:49:42
合計ジャッジ時間 7,745 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,342 ms
34,304 KB
testcase_01 AC 962 ms
35,200 KB
testcase_02 AC 1,266 ms
34,432 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll MOD=1000000007;
const ll INF=1000000000;
const ll LINF=4000000000000000010;
ll s[200010],c[200010],sum[200010],tmp[200010];
struct Segtree{//RAQxRSQ
	int n;
	vector<ll> node,lazy;
	void init(int n_){
		n=1;
		while(n<n_)n*=2;
		node.resize(2*n-1,0);
		lazy.resize(2*n-1,0);
		for(int i=0;i<n_;i++){
			node[n+i-1]=tmp[i];
		}
		for(int i=n-2;i>=0;i--){
			node[i]=node[i*2+1]+node[i*2+2];
			node[i]%=MOD;
		}
	}
	void eval(int k,int l,int r){
		if(lazy[k]==0)return;
		lazy[k]%=MOD;
		node[k]+=lazy[k]*((sum[r]-sum[l]+MOD)%MOD)%MOD;
		node[k]%=MOD;
		if(r-l>1){
			(lazy[2*k+1]+=lazy[k])%=MOD;//[l,(l+r)/2)
			(lazy[2*k+2]+=lazy[k])%=MOD;//[(l+r)/2,r)
		}
		lazy[k]=0;
	}
	void add(int a,int b,ll z,int k=0,int l=0,int r=-1){
		if(r<0)r=n;
		eval(k,l,r);
		if(b<=l||r<=a)return;
		if(a<=l&&r<=b){
			lazy[k]+=z;
			lazy[k]%=MOD;
			eval(k,l,r);
		}else{
			add(a,b,z,2*k+1,l,(l+r)/2);
			add(a,b,z,2*k+2,(l+r)/2,r);
			node[k]=node[2*k+1]+node[2*k+2];
			node[k]%=MOD;
		}
	}
	ll getsum(int a,int b,int k=0,int l=0,int r=-1){
		if(r<0)r=n;
		eval(k,l,r);
		if(b<=l||r<=a)return 0;
		if(a<=l&&r<=b)return node[k]%MOD;
		ll vl=getsum(a,b,2*k+1,l,(l+r)/2);
		ll vr=getsum(a,b,2*k+2,(l+r)/2,r);
		return vl+vr;
	}
};

struct HLDecomposition{
    int n,pos;
    vector<vector<int>> G;
	//新index,heavy-edgeの最初の要素のindex,部分木のサイズ,heavy-edgeでの次の頂点,親,深さ,元index
    vector<int> nid,fst,siz,hv,par,dep,id;
	Segtree tree;
    HLDecomposition(int n_){
        n=n_,pos=0;
        G.resize(n);
        nid.resize(n,-1);
        fst.resize(n);
        siz.resize(n,1);
        hv.resize(n,-1);
        par.resize(n);
        dep.resize(n);
        id.resize(n);
    }
    void add_edge(int u,int v){
        G[u].push_back(v);
        G[v].push_back(u);
    }
    void build(int rt){//rtを根とする木についてHL分解
		par[rt]=-1;
		dep[rt]=0;
        dfs(rt);
        bfs(rt);
    }
    void dfs(int v){//heavy-edgeを選んでいく
        int res=0;
        for(auto u:G[v]){
            if(u==par[v])continue;
            par[u]=v;
            dep[u]=dep[v]+1;
            dfs(u);
            siz[v]+=siz[u];
            if(res<siz[u]){
                res=siz[u];
                hv[v]=u;
            }
        }
    }
    void bfs(int r){//BFSで情報を保存する
        queue<int> q;
        q.push(r);
        while(!q.empty()){
            int h=q.front();q.pop();
            for(int i=h;i!=-1;i=hv[i]){
                nid[i]=pos++;
                id[nid[i]]=i;
                fst[i]=h;
                for(int j:G[i]){
                    if(j!=par[i]&&j!=hv[i])q.push(j);
                }
            }
        }
    }
    int lca(int u,int v){
        while(1){
            if(nid[u]>nid[v])swap(u,v);
            if(fst[u]==fst[v])return u;
            v=par[fst[v]];
        }
    }
	void query0(int x,int y,ll z){
		while(1){
			if(nid[x]>nid[y])swap(x,y);
			tree.add(max(nid[fst[y]],nid[x]),nid[y]+1,z);
			if(fst[x]!=fst[y]){
				y=par[fst[y]];
			}else{
				break;
			}
		}
	}
	ll query1(int x,int y){
		ll res=0;
		while(1){
			if(nid[x]>nid[y])swap(x,y);
			res+=tree.getsum(max(nid[fst[y]],nid[x]),nid[y]+1);
			res%=MOD;
			if(fst[x]!=fst[y]){
				y=par[fst[y]];
			}else{
				break;
			}
		}
		return res;
	}
};
int main(){
	int n;cin>>n;
	for(int i=0;i<n;i++)cin>>s[i];
	for(int i=0;i<n;i++)cin>>c[i];
	HLDecomposition tree(n);
	for(int i=0;i<n-1;i++){
		int a,b;cin>>a>>b;a--;b--;
		tree.add_edge(a,b);
	}
	tree.build(0);
	for(int i=0;i<n;i++){
		sum[i+1]=sum[i]+c[tree.id[i]];
		sum[i+1]%=MOD;
	}
	for(int i=0;i<n;i++)tmp[i]=s[tree.id[i]];
	tree.tree.init(n);
	int q;cin>>q;
	while(q--){
		ll t,x,y,z;
		cin>>t;
		if(t==0){
			cin>>x>>y>>z;x--;y--;
			tree.query0(x,y,z);
		}else{
			cin>>x>>y;x--;y--;
			cout<<tree.query1(x,y)%MOD<<endl;
		}
	}
}
0