We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#include<bits/stdc++.h>usingnamespacestd;#define mod 1000000007#define vi vector<int>#define pb push_back#define N 50005inta[N],b[N],sz[N],top[N],ch[N],f[N],st[N],w[N],p[N][18],d[N],cnt,n;vig[N];voiddfs(intu,intfa){sz[u]=1;for(inti=0;i<g[u].size();i++){intj=g[u][i];if(j==fa)continue;dfs(j,u);sz[u]+=sz[j];if(ch[u]==0||sz[ch[u]]<sz[j])ch[u]=j;}}voidgo(intu,intfa,intp){st[u]=++cnt;w[cnt]=u;top[u]=p;f[u]=fa;d[u]=d[fa]+1;if(ch[u]==0){return;}go(ch[u],u,p);for(inti=0;i<g[u].size();i++){intj=g[u][i];if(j==fa||j==ch[u])continue;go(j,u,j);}}intlca(inta,intb){if(d[a]<d[b])swap(a,b);inth=d[a]-d[b];for(inti=17;i>=0;i--)if(h>>i&1)a=p[a][i];if(a==b)returna;for(inti=17;i>=0;i--)if(p[a][i]!=p[b][i])a=p[a][i],b=p[b][i];returnp[a][0];}intpow(inta,intb){intans=1;while(b){if(b&1)ans=1LL*ans*a%mod;b>>=1;a=1LL*a*a%mod;}returnans;}structnode{inta,b1,b2,ca,cb;}t[N<<2];voidup(intp){t[p].a=1LL*t[p<<1].a*t[p<<1|1].a%mod;t[p].b1=(1LL*t[p<<1].a*t[p<<1|1].b1%mod+t[p<<1].b1)%mod;t[p].b2=(1LL*t[p<<1|1].a*t[p<<1].b2%mod+t[p<<1|1].b2)%mod;}voidbuild(intp,intl,intr){t[p].ca=t[p].cb=-1;if(l==r){t[p].a=a[w[l]];t[p].b1=t[p].b2=b[w[l]];return;}intm=(l+r)>>1;build(p<<1,l,m);build(p<<1|1,m+1,r);up(p);}voidcal(intp,intl,intr,inta,intb){t[p].a=pow(a,r-l+1);if(a==1){intv=1LL*b*(r-l+1)%mod;t[p].b1=t[p].b2=v;}else{intv=t[p].a-1;if(v<0)v+=mod;intw=a-1;if(w<0)w+=mod;w=pow(w,mod-2);v=1LL*v*w%mod*b%mod;t[p].b1=t[p].b2=v;}t[p].ca=a,t[p].cb=b;}voiddown(intp,intl,intr){if(t[p].ca!=-1){intm=(l+r)>>1;cal(p<<1,l,m,t[p].ca,t[p].cb);cal(p<<1|1,m+1,r,t[p].ca,t[p].cb);t[p].ca=-1;}}voidupd(intp,intl,intr,intx,inty,inta,intb){if(l>=x&&r<=y){cal(p,l,r,a,b);return;}intm=(l+r)>>1;down(p,l,r);if(x<=m)upd(p<<1,l,m,x,y,a,b);if(y>m)upd(p<<1|1,m+1,r,x,y,a,b);up(p);}voidquery(intp,intl,intr,intx,inty,int&a,int&b,intk){if(l>=x&&r<=y){a=t[p].a;if(k)b=t[p].b1;elseb=t[p].b2;return;}a=1;b=0;intm=(l+r)>>1,a1=1,b1=0,a2=1,b2=0;down(p,l,r);if(x<=m)query(p<<1,l,m,x,y,a1,b1,k);if(y>m)query(p<<1|1,m+1,r,x,y,a2,b2,k);a=1LL*a2*a1%mod;if(k)b=(1LL*a1*b2%mod+b1)%mod;elseb=(1LL*a2*b1%mod+b2)%mod;up(p);}voidchange(intu,intv,inta,intb){while(top[u]!=top[v]){intx=top[u];upd(1,1,n,st[x],st[u],a,b);u=f[x];}upd(1,1,n,st[v],st[u],a,b);}voidquery(intu,intv,int&a,int&b,intdir){a=1,b=0;while(top[u]!=top[v]){intx=top[u],a1,b1;query(1,1,n,st[x],st[u],a1,b1,dir);if(dir==0)b=(1LL*a*b1%mod+b)%mod;elseb=(1LL*a1*b%mod+b1)%mod;a=1LL*a*a1%mod;u=f[x];}inta1,b1;query(1,1,n,st[v],st[u],a1,b1,dir);if(dir==0)b=(1LL*a*b1%mod+b)%mod;elseb=(1LL*a1*b%mod+b1)%mod;a=1LL*a*a1%mod;}intmain(){intT,i,j,ca=0,k,m;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);for(i=1;i<n;i++){scanf("%d%d",&j,&k);g[j].pb(k);g[k].pb(j);}dfs(1,0);cnt=0;go(1,0,1);p[1][0]=1;for(i=1;i<=n;i++)p[i][0]=f[i];for(i=1;i<18;i++)for(j=1;j<=n;j++)p[j][i]=p[p[j][i-1]][i-1];build(1,1,n);scanf("%d",&m);while(m--){intx,y;scanf("%d%d%d",&k,&x,&y);if(k==1){inta,b;scanf("%d%d",&a,&b);intfa=lca(x,y);if(x==fa)change(y,x,a,b);elseif(y==fa)change(x,y,a,b);else{inth=d[x]-d[fa]-1;intu=x;for(i=17;i>=0;i--)if(h>>i&1)u=p[u][i];change(x,u,a,b);change(y,fa,a,b);}}else{intv;scanf("%d",&v);intfa=lca(x,y),a,b;if(x==fa)query(y,x,a,b,0);elseif(y==fa)query(x,y,a,b,1);else{inth=d[x]-d[fa]-1;intu=x,a1,b1;for(i=17;i>=0;i--)if(h>>i&1)u=p[u][i];query(x,u,a,b,1);query(y,fa,a1,b1,0);b=(1LL*a1*b%mod+b1)%mod;a=1LL*a*a1%mod;}printf("%d\n",(1LL*a*v%mod+b)%mod);}}return0;}
C++ solution
for complete solution in java c++ and c programming search for programs.programmingoneonone.com on google
I don't understand the description of the input format. It seems inconsistent with the example.