結果

問題 No.235 めぐるはめぐる (5)
ユーザー pekempeypekempey
提出日時 2017-08-01 22:17:15
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 527 ms / 10,000 ms
コード長 1,640 bytes
コンパイル時間 940 ms
コンパイル使用メモリ 82,056 KB
実行使用メモリ 24,792 KB
最終ジャッジ日時 2024-04-19 07:45:02
合計ジャッジ時間 4,671 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 510 ms
23,964 KB
testcase_01 AC 419 ms
24,792 KB
testcase_02 AC 527 ms
24,316 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

constexpr int mod=1e9+7;
constexpr int N = 2e5;
int now;
int parent[N],head[N],vid[N],sub[N],s[N],w[N];
vector<int> g[N];
int64_t s0[N+1],s1[N+1],sw[N+1];

int in(){int n;scanf("%d",&n);return n;}

void dfs(int u,int p){
	sub[u]=1;for(int v:g[u])if(v!=p)dfs(v,u),sub[u]+=sub[v];
}

void dfs2(int u,int p,int h){
	parent[u]=p;head[u]=h;vid[u]=now++;
	for(int v:g[u])if(v!=p&&sub[u]<sub[v]*2)dfs2(v,u,h);
	for(int v:g[u])if(v!=p&&sub[u]>=sub[v]*2)dfs2(v,u,v);
}

template<class T> void foreach(int u,int v,T f){
	for(;;v=parent[head[v]]){
		if(vid[u]>vid[v])swap(u,v);
		if(head[u]==head[v])return f(vid[u],vid[v]);
		f(vid[head[v]],vid[v]);
	}
}

void add(int k,int64_t v){
	for(int i=k+1;i<=N;i+=i&-i)s0[i]+=mod-v*sw[k]%mod,s1[i]+=v;
}

void add_point(int k,int64_t v){
	for(int i=k+1;i<=N;i+=i&-i)s0[i]+=v;
}

int64_t sum(int k){
	int64_t ret0=0,ret1=0;
	for(int i=k;i>0;i-=i&-i)ret0+=s0[i],ret1+=s1[i];
	return (ret0+ret1%mod*sw[k])%mod;
}

int main() {
	int n=in();
	for(int i=0;i<n;i++)s[i]=in();
	for(int i=0;i<n;i++)w[i]=in();
	for(int i=1;i<n;i++){
		int u=in()-1,v=in()-1;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(0,-1);
	dfs2(0,-1,0);
	for(int i=0;i<n;i++)sw[vid[i]+1]=w[i];
	for(int i=0;i<n;i++)sw[i+1]=(sw[i+1]+sw[i])%mod;
	for(int i=0;i<n;i++)add_point(vid[i],s[i]);
	int q=in();
	while(q--){
		int t=in(),x=in()-1,y=in()-1;
		if(t==0){
			int z=in();
			foreach(x,y,[&](int l,int r){add(l,z),add(r+1,mod-z);});
		}else{
			int64_t ans=0;
			foreach(x,y,[&](int l,int r){ans+=sum(r+1)+mod-sum(l);});
			printf("%lld\n",ans%mod);
		}
	}
}
0