結果

問題 No.235 めぐるはめぐる (5)
コンテスト
ユーザー TAISA_
提出日時 2018-11-13 23:05:49
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,813 bytes
コンパイル時間 2,948 ms
コンパイル使用メモリ 186,456 KB
実行使用メモリ 35,328 KB
最終ジャッジ日時 2024-12-24 13:30:28
合計ジャッジ時間 9,549 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 3
権限があれば一括ダウンロードができます

ソースコード

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];
		}
	}
	void eval(int k,int l,int r){
		if(lazy[k]==0)return;
		node[k]+=lazy[k]*(sum[r]-sum[l]);
		if(r-l>1){
			lazy[2*k+1]+=lazy[k];//[l,(l+r)/2)
			lazy[2*k+2]+=lazy[k];//[(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;
			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];
		}
	}
	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];
		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);
			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]];
	}
	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)<<endl;
		}
	}
}
0