結果
| 問題 | No.235 めぐるはめぐる (5) |
| ユーザー |
 latte0119
|
| 提出日時 | 2015-10-31 16:09:04 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 3,964 bytes |
| コンパイル時間 | 870 ms |
| コンパイル使用メモリ | 71,116 KB |
| 実行使用メモリ | 61,712 KB |
| 最終ジャッジ日時 | 2024-09-13 06:22:45 |
| 合計ジャッジ時間 | 4,816 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | RE | - |
| testcase_02 | RE | - |
コンパイルメッセージ
main.cpp: In function ‘long long int hl_init()’:
main.cpp:108:1: warning: no return statement in function returning non-void [-Wreturn-type]
108 | }
| ^
main.cpp: In function ‘int main()’:
main.cpp:135:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
135 | scanf("%lld",&N);
| ~~~~~^~~~~~~~~~~
main.cpp:136:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
136 | rep(i,N)scanf("%lld",&S[i]);
| ~~~~~^~~~~~~~~~~~~~
main.cpp:137:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
137 | rep(i,N)scanf("%lld",&C[i]);
| ~~~~~^~~~~~~~~~~~~~
main.cpp:141:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
141 | scanf("%lld%lld",&a,&b);
| ~~~~~^~~~~~~~~~~~~~~~~~
main.cpp:148:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
148 | scanf("%lld",&Q);
| ~~~~~^~~~~~~~~~~
main.cpp:151:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
151 | scanf("%lld",&type);
| ~~~~~^~~~~~~~~~~~~~
main.cpp:154:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
154 | scanf("%lld%lld%lld",&x,&y,&z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:164:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
164 | scanf("%lld%lld",&x,&y
ソースコード
#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
#include<cassert>
#define int long long
using namespace std;
typedef pair<int,int>pint;
typedef vector<int>vint;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);i++)
template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}
const int mod=1000000007;
struct seg_tree{
int N;
vint dat,sum,lazy;
void init(vint &s,vint &c){
N=1;
while(N<s.size())N<<=1;
dat.resize(N*2-1);
sum.resize(N*2-1);
lazy.resize(N*2-1);
rep(i,s.size()){
dat[i+N-1]=s[i];
sum[i+N-1]=c[i];
}
for(int i=N-2;i>=0;i--){
dat[i]=(dat[i*2+1]+dat[i*2+2])%mod;
sum[i]=(sum[i*2+1]+dat[i*2+2])%mod;
}
}
inline void evaluate(int k){
dat[k]+=sum[k]*lazy[k]%mod;
if(k<N-1){
lazy[k*2+1]=(lazy[k*2+1]+lazy[k])%mod;
lazy[k*2+2]=(lazy[k*2+2]+lazy[k])%mod;
}
lazy[k]=0;
}
void update(int k){
dat[k]=(dat[k*2+1]+dat[k*2+2])%mod;
}
void add(int a,int b,int x){add(a,b,x,0,0,N);}
void add(int a,int b,int x,int k,int l,int r){
evaluate(k);
if(r<=a||b<=l)return;
if(a<=l&&r<=b){
lazy[k]=(lazy[k]+x+mod)%mod;
evaluate(k);
return;
}
add(a,b,x,k*2+1,l,(l+r)/2);
add(a,b,x,k*2+2,(l+r)/2,r);
update(k);
}
int get(int a,int b){return get(a,b,0,0,N);}
int get(int a,int b,int k,int l,int r){
evaluate(k);
if(r<=a||b<=l)return 0;
if(a<=l&&r<=b)return dat[k];
return (get(a,b,k*2+1,l,(l+r)/2)+get(a,b,k*2+2,(l+r)/2,r))%mod;
}
};
const int SIZE=200000;
int N,Q;
int S[SIZE],C[SIZE];
vint G[SIZE];
int par[SIZE],depth[SIZE],heavy[SIZE];
int head[SIZE],chain[SIZE];
vector<seg_tree>seg;
int hl_dfs(int v,int p,int d){
par[v]=p;
depth[v]=d;
heavy[v]=-1;
int ma=0,sum=0;
rep(i,G[v].size()){
int to=G[v][i];
if(to==p)continue;
int val=hl_dfs(to,v,d+1);
if(ma<val){
ma=val;
heavy[v]=to;
}
sum+=val;
}
return sum+1;
}
int hl_init(){
hl_dfs(0,-1,0);
rep(i,N){
if(par[i]>=0&&heavy[par[i]]==i)continue;
vint s,c;
for(int j=i;~j;j=heavy[j]){
head[j]=i;
chain[j]=seg.size();
s.pb(S[j]);
c.pb(C[j]);
}
seg.pb(seg_tree());
seg.back().init(s,c);
}
}
int lca(int u,int v){
while(chain[u]!=chain[v]){
if(depth[head[u]]<depth[head[v]])swap(u,v);
u=par[head[u]];
}
return depth[u]<depth[v]?u:v;
}
void add(int v,int x){
while(~v){
seg[chain[v]].add(0,depth[v]-depth[head[v]]+1,x);
v=par[head[v]];
}
}
int get(int v){
int ret=0;
while(~v){
ret+=seg[chain[v]].get(0,depth[v]-depth[head[v]]+1);
v=par[head[v]];
}
return ret;
}
signed main(){
scanf("%lld",&N);
rep(i,N)scanf("%lld",&S[i]);
rep(i,N)scanf("%lld",&C[i]);
rep(i,N-1){
int a,b;
scanf("%lld%lld",&a,&b);
a--;b--;
G[a].pb(b);
G[b].pb(a);
}
hl_init();
scanf("%lld",&Q);
while(Q--){
int type;
scanf("%lld",&type);
if(type==0){
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
x--;y--;
int p=lca(x,y);
add(x,z);
add(y,z);
add(p,-z);
if(par[p]>=0)add(par[p],-z);
}
else{
int x,y;
scanf("%lld%lld",&x,&y);
x--;y--;
int p=lca(x,y);
int ans=get(x)+get(y)-get(p);
if(par[p]>=0)ans-=get(par[p]);
ans=(ans+mod*100)%mod;
printf("%lld\n",ans);
}
}
return 0;
}