結果

問題 No.235 めぐるはめぐる (5)
コンテスト
ユーザー pekempey
提出日時 2017-08-01 22:17:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 675 ms / 10,000 ms
コード長 1,640 bytes
コンパイル時間 977 ms
コンパイル使用メモリ 79,136 KB
最終ジャッジ日時 2025-01-05 02:02:08
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:71:36: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int64_t’ {aka ‘long int’} [-Wformat=]
   71 |                         printf("%lld\n",ans%mod);
      |                                 ~~~^    ~~~~~~~
      |                                    |       |
      |                                    |       int64_t {aka long int}
      |                                    long long int
      |                                 %ld
main.cpp: In function ‘int in()’:
main.cpp:14:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   14 | int in(){int n;scanf("%d",&n);return n;}
      |                ~~~~~^~~~~~~~~

ソースコード

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