結果
問題 | No.235 めぐるはめぐる (5) |
ユーザー | blackyuki |
提出日時 | 2022-09-03 10:42:31 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,215 ms / 10,000 ms |
コード長 | 5,028 bytes |
コンパイル時間 | 2,738 ms |
コンパイル使用メモリ | 214,128 KB |
実行使用メモリ | 42,240 KB |
最終ジャッジ日時 | 2024-11-16 22:18:45 |
合計ジャッジ時間 | 12,061 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,215 ms
41,472 KB |
testcase_01 | AC | 1,506 ms
42,240 KB |
testcase_02 | AC | 1,997 ms
41,728 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for(long long i=0;i<(long long)(n);i++) #define REP(i,k,n) for(long long i=k;i<(long long)(n);i++) #define all(a) a.begin(),a.end() #define rsort(a) {sort(all(a));reverse(all(a));} #define pb emplace_back #define eb emplace_back #define lb(v,k) (lower_bound(all(v),(k))-v.begin()) #define ub(v,k) (upper_bound(all(v),(k))-v.begin()) #define fi first #define se second #define pi M_PI #define PQ(T) priority_queue<T> #define SPQ(T) priority_queue<T,vector<T>,greater<T>> #define dame(a) {out(a);return 0;} #define decimal cout<<fixed<<setprecision(15); #define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());} typedef long long ll; typedef pair<ll,ll> P; typedef tuple<ll,ll,ll> PP; typedef tuple<ll,ll,ll,ll> PPP; typedef multiset<ll> S; using vi=vector<ll>; using vvi=vector<vi>; using vvvi=vector<vvi>; using vvvvi=vector<vvvi>; using vp=vector<P>; using vvp=vector<vp>; using vpp=vector<PP>; using vb=vector<bool>; using vvb=vector<vb>; using vvvb=vector<vvb>; const ll inf=1001001001001001001; const ll INF=1001001001; const ll mod=1000000007; const double eps=1e-10; template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;} template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;} template<class T> void out(T a){cout<<a<<'\n';} template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';} template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';} template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);} template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';} template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);} template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);} template<class T> void yesno(T b){if(b)out("yes");else out("no");} template<class T> void YesNo(T b){if(b)out("Yes");else out("No");} template<class T> void YESNO(T b){if(b)out("YES");else out("NO");} template<class T> void noyes(T b){if(b)out("no");else out("yes");} template<class T> void NoYes(T b){if(b)out("No");else out("Yes");} template<class T> void NOYES(T b){if(b)out("NO");else out("YES");} void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);} ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);} ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} ll inv(ll a){return modpow(a,mod-2);} ll ans,md,z; class segtree{ vi seg,lazy,c;ll N=1; ll f(ll a,ll b){return (a+b)%mod;} public: segtree(vi&v,vi&C){ c=C; ll n=v.size(); while(N<n)N*=2; seg=vi(N*2-1);lazy=vi(N*2-1);c=vi(N*2-1); rep(i,n)seg[i+N-1]=v[i]; rep(i,n)c[i+N-1]=C[i]; for(int i=N-2;i>=0;i--)seg[i]=f(seg[i*2+1],seg[i*2+2]); for(int i=N-2;i>=0;i--)c[i]=f(c[i*2+1],c[i*2+2]); } void eval(ll k,ll l,ll r){ seg[k]=f(seg[k],lazy[k]*c[k]); if(r-l>1){ lazy[k*2+1]=f(lazy[k*2+1],lazy[k]); lazy[k*2+2]=f(lazy[k*2+2],lazy[k]); } lazy[k]=0; } void query(ll a,ll b,ll k=0,ll l=0,ll r=-1){ if(r==-1)r=N; eval(k,l,r); if(a<=l&&r<=b){ if(md)ans+=seg[k]; else{ lazy[k]=f(lazy[k],z); eval(k,l,r); } } else if(r<=a||b<=l)return; else{ query(a,b,k*2+1,l,(l+r)/2); query(a,b,k*2+2,(l+r)/2,r); seg[k]=f(seg[k*2+1],seg[k*2+2]); } } }; int main(){ ll n;cin>>n; vi v(n),c(n);rep(i,n)cin>>v[i];rep(i,n)cin>>c[i]; vvi g(n); rep(i,n-1){ ll a,b;cin>>a>>b;a--;b--; g[a].pb(b);g[b].pb(a); } vi par(n),head(n),id(n),sz(n,1); ll cnt=0; function<void(ll,ll)> init=[&](ll i,ll p){ par[i]=p; ll ma=0; rep(j,g[i].size())if(g[i][j]!=p){ init(g[i][j],i); sz[i]+=sz[g[i][j]]; if(chmax(ma,sz[g[i][j]]))swap(g[i][j],g[i][0]); } }; init(0,-1); function<void(ll,ll)> HLD=[&](ll i,ll p){ id[i]=cnt++; rep(j,g[i].size())if(g[i][j]!=p){ if(j)head[g[i][j]]=g[i][j]; else head[g[i][j]]=head[i]; HLD(g[i][j],i); } }; HLD(0,-1); vi V(n),C(n); rep(i,n)C[id[i]]=c[i];rep(i,n)V[id[i]]=v[i]; segtree seg(V,C); function<void(ll,ll)> query=[&](ll a,ll b){ ll A=head[a],B=head[b]; if(A==B)seg.query(min(id[a],id[b]),max(id[a],id[b])+1); else if(id[A]<id[B]){ seg.query(id[B],id[b]+1); query(a,par[B]); } else{ seg.query(id[A],id[a]+1); query(par[A],b); } }; ll q;cin>>q; rep(qq,q){ cin>>md; if(md){ ans=0; ll x,y;cin>>x>>y;x--;y--; query(x,y); out(ans%mod); } else{ ll x,y;cin>>x>>y>>z;x--;y--; query(x,y); } } }