結果
問題 | No.235 めぐるはめぐる (5) |
ユーザー | pekempey |
提出日時 | 2017-08-01 22:17:15 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 502 ms / 10,000 ms |
コード長 | 1,640 bytes |
コンパイル時間 | 823 ms |
コンパイル使用メモリ | 79,984 KB |
実行使用メモリ | 24,696 KB |
最終ジャッジ日時 | 2024-10-11 00:24:01 |
合計ジャッジ時間 | 4,452 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 502 ms
23,936 KB |
testcase_01 | AC | 366 ms
24,696 KB |
testcase_02 | AC | 470 ms
24,192 KB |
ソースコード
#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); } } }