結果

問題 No.235 めぐるはめぐる (5)
ユーザー LayCurseLayCurse
提出日時 2015-06-26 12:40:20
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 676 ms / 10,000 ms
コード長 11,901 bytes
コンパイル時間 2,293 ms
コンパイル使用メモリ 163,748 KB
実行使用メモリ 33,800 KB
最終ジャッジ日時 2023-09-22 00:46:25
合計ジャッジ時間 6,022 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 676 ms
27,600 KB
testcase_01 AC 239 ms
33,800 KB
testcase_02 AC 464 ms
29,616 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(double *x){scanf("%lf",x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(double x, char c){printf("%.15f",x);mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}
template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');}
template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}

char memarr[77000000]; void *mem = memarr;
#define MD 1000000007

int get_inv(ll a, int md){ll t=a,s=md,u=1,v=0,e;while(s){e=t/s;t-=e*s;u-=e*v;swap(t,s);swap(u,v);}if(u<0)u+=md;return u;}

struct mint{
  static unsigned md, W, R, Rinv, mdninv, RR;
  unsigned val;

  mint(){}mint(int a){val=mulR(a);}mint(unsigned a){val=mulR(a);}mint(ll a){val=mulR(a);}mint(ull a){val=mulR(a);}
  void setmod(unsigned m){int i;unsigned t;W=32;md=m;R=(1ULL<<W)%md;RR=(ull)R*R%md;switch(m){case 104857601:Rinv=2560000;mdninv=104857599;break;case 998244353:Rinv=232013824;mdninv=998244351;break;case 1000000007:Rinv=518424770;mdninv=2226617417U;break;case 1000000009:Rinv=171601999;mdninv=737024967;break;case 1004535809:Rinv=234947584;mdninv=1004535807;break;case 1007681537:Rinv=236421376;mdninv=1007681535;break;case 1012924417:Rinv=238887936;mdninv=1012924415;break;case 1045430273:Rinv=254466304;mdninv=1045430271;break;case 1051721729:Rinv=257538304;mdninv=1051721727;break;default:Rinv=get_inv(R,md);mdninv=0;t=0;rep(i,W){if(t%2==0)t+=md,mdninv|=(1U<<i);t/=2;}}}
  unsigned mulR(unsigned a){return(ull)a*R%md;}unsigned mulR(int a){if(a<0)a=a%md+md;return mulR((unsigned)a);}unsigned mulR(ull a){return mulR((unsigned)(a%md));}unsigned mulR(ll a){if(a<0)a=a%md+md;return mulR((unsigned)a);}
  unsigned reduce(unsigned T){unsigned m=T*mdninv;unsigned t=(unsigned)((T+(ull)m*md)>>W);if(t>=md)t-=md;return t;}unsigned reduce(ull T){unsigned m=(unsigned)T*mdninv;unsigned t=(unsigned)((T+(ull)m*md)>>W);if(t>=md)t-=md;return t;}
  unsigned get(){return reduce(val);}
  mint&operator+=(mint a){val+=a.val;if(val>=md)val-=md;return*this;}mint&operator-=(mint a){if(val<a.val)val=val+md-a.val;else val-=a.val;return*this;}mint&operator*=(mint a){val=reduce((ull)val*a.val);return*this;}mint&operator/=(mint a){return*this*=a.inverse();}
  mint operator+(mint a){return mint(*this)+=a;}mint operator-(mint a){return mint(*this)-=a;}mint operator*(mint a){return mint(*this)*=a;}mint operator/(mint a){return mint(*this)/=a;}
  mint operator+(int a){return mint(*this)+=mint(a);}mint operator-(int a){return mint(*this)-=mint(a);}mint operator*(int a){return mint(*this)*=mint(a);}mint operator/(int a){return mint(*this)/=mint(a);}
  mint operator+(ll a){return mint(*this)+=mint(a);}mint operator-(ll a){return mint(*this)-=mint(a);}mint operator*(ll a){return mint(*this)*=mint(a);}mint operator/(ll a){return mint(*this)/=mint(a);}
  mint operator-(void){mint res;if(val)res.val=md-val;else res.val=0;return res;}
  operator bool(void){return val!=0;}operator int(void){return get();}operator ll(void){return get();}
  mint inverse(){int a=val,b=md,u=1,v=0,t;mint r;while(b){t=a/b;a-=t*b;swap(a,b);u-=t*v;swap(u,v);}if(u<0)u+=md;r.val=(ull)u*RR%md;return r;}
  mint pw(ull b){mint a(*this),r;r.val=R;while(b){if(b&1)r*=a;b>>=1;a*=a;}return r;}
  bool operator==(int a){return get()==a;}
  bool operator!=(int a){return get()!=a;}
};
unsigned mint::md, mint::W, mint::R, mint::Rinv, mint::mdninv, mint::RR;
mint operator+(int a, mint b){return mint(a)+=b;}mint operator-(int a, mint b){return mint(a)-=b;}mint operator*(int a, mint b){return mint(a)*=b;}mint operator/(int a, mint b){return mint(a)/=b;}
mint operator+(ll a, mint b){return mint(a)+=b;}mint operator-(ll a, mint b){return mint(a)-=b;}mint operator*(ll a, mint b){return mint(a)*=b;}mint operator/(ll a, mint b){return mint(a)/=b;}

mint mval[10000], minv[10000];
void mint_init(int md=MD, mint val[]=mval, int vals=10000, mint inv[]=minv, int invs=10000){int i;val[0].setmod(md);val[0].val=0;REP(i,1,vals){val[i].val=val[i-1].val+mint::R;if(val[i].val >=md)val[i].val-=md;}inv[1].val=1;REP(i,2,invs){inv[i].val=md-((ll)(md/i)*inv[md%i].val%md);}REP(i,1,invs)inv[i].val=(ull)inv[i].val*mint::R%md;}



template<class T, class S>
struct lazySegtreeSumWithCoef_AddOnly{
  int N, logN; T *data, *addval; S *coef, *coefsum;

  void malloc(int maxN){int i;for(i=1;i<maxN;i*=2);data=(T*)std::malloc(sizeof(T)*2*i);addval=(T*)std::malloc(sizeof(T)*i);coef=(S*)std::malloc(sizeof(T)*i);coefsum=(S*)std::malloc(sizeof(T)*(i+1));}
  void* malloc(int maxN, void *mem){int i;for(i=1;i<maxN;i*=2);data=(T*)mem;addval=data+2*i;coef=(S*)(addval+i);coefsum=coef+i;return coefsum+i+1;}
  T& operator[](int i){return data[N+i];}
  void setN(int n, int zerofill=1){int i;for(i=1,logN=0;i<n;i*=2,logN++);N=i;if(zerofill){rep(i,N)data[N+i]=0;rep(i,N)coef[i]=0;}}
  void build(void){int i;for(i=N-1;i;i--)data[i]=data[2*i]+data[2*i+1];REP(i,1,N)addval[i]=0;coefsum[0]=0;rep(i,N)coefsum[i+1]=coefsum[i]+coef[i];}
  inline void push_one(int a, int st, int ed){if(addval[a]!=0){if(ed-st>2)addval[a*2]+=addval[a],addval[a*2+1]+=addval[a];data[a*2]+=(coefsum[(st+ed)/2]-coefsum[st])*addval[a];data[a*2+1]+=(coefsum[ed]-coefsum[(st+ed)/2])*addval[a];addval[a]=0;}}
  inline void push(int a){int i,s=0,e=N;for(i=logN;i;i--){push_one(a>>i,s,e);if((a>>(i-1))&1)s=(s+e)/2;else e=(s+e)/2;}}
  inline void build(int a){int s=a-N,e=a-N+1;while(a>1){if(a%2)s-=e-s;else e+=e-s;a/=2;data[a]=data[a*2]+data[a*2+1];if(addval[a]!=0)data[a]+=addval[a]*(coefsum[e]-coefsum[s]);}}
  inline void add(int a, int b, T val){int c,d,s=a,t=b,sz=1;if(a>=b)return;c=(a+=N);d=(b+=N);push(a);push(b-1);if(a%2){data[a]+=val*(coefsum[s+sz]-coefsum[s]);a++;s+=sz;}if(b%2){b--;data[b]+=val*(coefsum[t]-coefsum[t-sz]);t-=sz;}a/=2;b/=2;while(a<b){sz*=2;if(a%2){addval[a]+=val;data[a++]+=(coefsum[s+sz]-coefsum[s])*val;s+=sz;}if(b%2){b--;addval[b]+=val;data[b]+=(coefsum[t]-coefsum[t-sz])*val;t-=sz;}a/=2;b/=2;}build(c);build(d-1);}
  inline T getSum(int a, int b){T res;int sz=1;a+=N;b+=N;push(a);push(b-1);res=0;while(a<b){if(a%2)res+=data[a++];if(b%2)res+=data[--b];a/=2;b/=2;}return res;}
};

struct HLD{
  int N, *es, **edge, *dep, *sz;
  int *group, *groupind, groupNum, *groupSize, **groupNode, *groupUpNode, *groupDepth;
  void* init(int N__, int *es__, int **edge__, void *mem){int i,j,k,x,y,m,*q;char*v;N=N__;es=es__;edge=edge__;dep=(int*)mem;sz=dep+N;group=sz+N;groupind=group+N;mem=groupind+N;q=(int*)mem;v=(char*)(q+N);rep(i,N)v[i]=0;x=0;y=1;q[0]=0;v[0]=1;while(x<y){i=q[x++];rep(j,es[i]){k=edge[i][j];if(!v[k])v[k]=1,q[y++]=k;}}rep(i,N)sz[i]=0;for(j=N-1;j>=0;j--){i=q[j];sz[i]=1;rep(k,es[i])sz[i]+=sz[edge[i][k]];}rep(i,N)group[i]=-1;groupNum=0;rep(j,N){i=q[j];if(group[i]>=0)continue;group[i]=groupNum++;groupind[i]=0;for(;;){m=-1;rep(k,es[i]){if(group[edge[i][k]]!=-1)continue;if(m==-1)m=k;else if(sz[edge[i][k]]>sz[edge[i][m]])m=k;}if(m==-1)break;group[edge[i][m]]=group[i];groupind[edge[i][m]]=groupind[i]+1;i=edge[i][m];}}groupSize=(int*)mem;groupUpNode=groupSize+groupNum;groupDepth=groupUpNode+groupNum;rep(i,groupNum)groupSize[i]=0;rep(i,N)groupSize[group[i]]++;groupNode=(int**)(groupDepth+groupNum);groupNode[0]=(int*)(groupNode+groupNum);REP(i,1,groupNum)groupNode[i]=groupNode[i-1]+groupSize[i-1];mem=groupNode[groupNum-1]+groupSize[groupNum-1];rep(i,N)groupNode[group[i]][groupind[i]]=i;rep(i,groupNum)groupDepth[i]=-1;groupUpNode[0]=-1;groupDepth[0]=0;rep(x,groupNum)rep(y,groupSize[x]){i=groupNode[x][y];rep(j,es[i]){k=edge[i][j];if(x!=group[k]&&groupDepth[group[k]]==-1)groupUpNode[group[k]]=i,groupDepth[group[k]]=groupDepth[x]+1;}}return mem;}
};

template<class T, class S> struct HLD_Node_LazySegtreeSumWithCoef_AddOnly{
  HLD *hld;
  lazySegtreeSumWithCoef_AddOnly<T,S>*seg;

  void* init(HLD *hld__, T initval[], S coef[], void *mem){int i,j;hld=hld__;seg=(lazySegtreeSumWithCoef_AddOnly<T,S>*)mem;mem=seg+hld->groupNum;rep(i,hld->groupNum){mem=seg[i].malloc(hld->groupSize[i], mem);seg[i].setN(hld->groupSize[i]);if(initval!=NULL)rep(j,hld->groupSize[i])seg[i][j]=initval[hld->groupNode[i][j]];if(coef!=NULL)rep(j,hld->groupSize[i])seg[i].coef[j]=coef[hld->groupNode[i][j]];seg[i].build();}return mem;}
  void add(int u, int v, T val){int X=hld->group[u],Y=hld->group[v],Z,W;while(X!=Y){if(hld->groupDepth[X]<hld->groupDepth[Y])swap(u,v),swap(X,Y);seg[X].add(0,hld->groupind[u]+1,val);u=hld->groupUpNode[X];X=hld->group[u];}Z=hld->groupind[u];W=hld->groupind[v];seg[X].add(min(Z,W),max(Z,W)+1,val);}
  T getSum(int u, int v){T res=0;int X=hld->group[u],Y=hld->group[v],Z,W;while(X!=Y){if(hld->groupDepth[X]<hld->groupDepth[Y])swap(u,v),swap(X,Y);res+=seg[X].getSum(0,hld->groupind[u]+1);u=hld->groupUpNode[X];X=hld->group[u];}Z=hld->groupind[u];W=hld->groupind[v];res+=seg[X].getSum(min(Z,W),max(Z,W)+1);return res;}
};


void* setUndirectEdge(int N, int M, int A[], int B[], int **es, int ***edge, void *workMemory){int i;*es=(int*)workMemory;*edge=(int**)((*es)+N);(*edge)[0]=(int*)((*edge)+N);rep(i,N)(*es)[i]=0;rep(i,M)(*es)[A[i]]++,(*es)[B[i]]++;REP(i,1,N)(*edge)[i]=(*edge)[i-1]+(*es)[i-1];workMemory=(void*)((*edge)[N-1]+(*es)[N-1]);rep(i,N)(*es)[i]=0;rep(i,M)(*edge)[A[i]][(*es)[A[i]]++]=B[i],(*edge)[B[i]][(*es)[B[i]]++]=A[i];return workMemory;}
void getDist(int N, int root, int *es, int **edge, int dist[], void *mem){int i,j,k,*q,s,z;q=(int*)mem;rep(i,N)dist[i]=-1;dist[root]=0;s=0;z=1;q[0]=root;while(z){i=q[s++];z--;rep(j,es[i]){k=edge[i][j];if(dist[k]>=0)continue;dist[k]=dist[i]+1;q[s+z++]=k;}}}

int N, Q;
int A[300000], B[300000], S[300000], C[300000];

int T, X, Y, Z;
int *es, **edge;
mint SS[300000], CC[300000];


int main(){
  int i, j, k;
  HLD hld;
  HLD_Node_LazySegtreeSumWithCoef_AddOnly<mint,mint> seg;
  mint res;

  mint_init();

  reader(&N);
  rep(i,N) reader(S+i);
  rep(i,N) reader(C+i);
  rep(i,N-1) reader(A+i,B+i), A[i]--, B[i]--;
  reader(&Q);

  rep(i,N) SS[i] = (unsigned)S[i];
  rep(i,N) CC[i] = (unsigned)C[i];

  mem = setUndirectEdge(N, N-1, A, B, &es, &edge, mem);
  mem = hld.init(N, es, edge, mem);
  mem = seg.init(&hld, SS, CC, mem);

  while(Q--){
    reader(&T);
    if(T==0){
      reader(&X,&Y,&Z);
      X--; Y--;
      seg.add(X,Y,mint(Z));
    } else {
      reader(&X,&Y);
      X--; Y--;
      res = seg.getSum(X,Y);
      printf("%d\n",(int)res);
    }
  }

  return 0;
}
0