Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<math.h>
- #include<algorithm>
- #include<cstdlib>
- #include<iostream>
- #include<stdio.h>
- #include<map>
- #include<set>
- #include<string>
- #include<assert.h>
- #include<vector>
- #include<ctime>
- #include<queue>
- #include<deque>
- #include<sstream>
- #include<stack>
- #include<sstream>
- #define MA(a,b) ((a)>(b)?(a):(b))
- #define MI(a,b) ((a)<(b)?(a):(b))
- #define AB(a) (-(a)<(a)?(a):-(a))
- #define X first
- #define Y second
- #define mp make_pair
- #define pb push_back
- #define pob pop_back
- #define ep 0.000001
- #define pi 3.1415926535897932384626433832795
- #define na(x) ((x)<P?(x):(x)-P)
- using namespace std;
- const int N=50001;
- const long long P=1000000007;
- int n,a[N],b[N],x,y,anew,bnew,L,R;
- vector <int> v[N];
- struct ele {
- bool f;
- long long fa,fb;
- long long a,b,br;
- ele *l,*r;
- } *tnt,*tnt2;
- struct HLT{
- vector <int> ind;
- ele *start;
- inline ele *mk(){
- ele *t=(ele*)malloc(sizeof(ele));
- t->a=t->b=t->br=0;
- t->f=0;
- t->l=t->r=NULL;
- return t;
- }
- inline void add(ele *&t,ele *L,ele *R){
- t->a=(L->a*R->a)%P;
- t->b=(L->b*R->a+R->b)%P;
- t->br=(R->br*L->a+L->br)%P;
- }
- inline void add2(ele *&t,ele *L,ele *R){
- t->b=(L->b*R->a+R->b)%P;
- t->a=(L->a*R->a)%P;
- }
- inline void po(ele *&t,int x){
- tnt->a=t->fa;
- tnt->b=t->fb;
- t->a=1;
- t->b=0;
- while (x){
- if (x&1) add2(t,t,tnt);
- x>>=1;
- add2(tnt,tnt,tnt);
- }
- t->br=t->b;
- }
- void bil(int l,int r,ele *&t){
- if (t==NULL) t=mk();
- if (l+1==r) {
- t->a=a[ind[l]];
- t->b=t->br=b[ind[l]];
- return;
- }
- bil(l,(l+r)/2,t->l);
- bil((l+r)/2,r,t->r);
- add(t,t->l,t->r);
- }
- void up(int l,int r,ele *&t){
- if (R<l || r-1<L) return;
- if (L<=l && r-1<=R){
- t->f=1;
- t->fa=anew;
- t->fb=bnew;
- po(t,r-l);
- return;
- }
- if (t->f){
- t->l->fa=t->fa;
- t->l->fb=t->fb;
- t->l->f=1;
- po(t->l,(l+r)/2-l);
- t->r->fa=t->fa;
- t->r->fb=t->fb;
- t->r->f=1;
- po(t->r,r-(l+r)/2);
- t->f=0;
- }
- up(l,(l+r)/2,t->l);
- up((l+r)/2,r,t->r);
- add(t,t->l,t->r);
- }
- long long calc(int l,int r,ele *t,long long x,bool rev){
- if (L<=l && r-1<=R) return (t->a*x+(rev?t->br:t->b))%P;
- if (r-1<L || R<l) return x;
- if (t->f){
- tnt2->fa=t->fa;
- tnt2->fb=t->fb;
- po(tnt2,MI(R,r-1)-MA(l,L)+1);
- return (tnt2->a*x+(rev?tnt2->br:tnt2->b))%P;
- }
- if ( rev) return calc(l,(l+r)/2,t->l,calc((l+r)/2,r,t->r,x,rev),rev);
- if (!rev) return calc((l+r)/2,r,t->r,calc(l,(l+r)/2,t->l,x,rev),rev);
- return 0ll;
- }
- } A[N];
- struct mis{
- int HLTind,HLTnum,p[16],deep;
- } node[N];
- int HLTN;
- int go(int x,int fr)
- {
- node[x].deep=node[fr].deep+1;
- int S=1;
- vector <int> s;
- for (int i=0;i<v[x].size();i++) s.pb(v[x][i]!=fr?go(v[x][i],x):0),S+=s[i];
- bool fin=0;
- for (int i=0;i<v[x].size();i++)
- if (S<=s[i]*2){
- node[x].HLTind=node[v[x][i]].HLTind;
- fin=1;
- }
- if (fin==0) node[x].HLTind=HLTN,HLTN++;
- node[x].HLTnum=A[node[x].HLTind].ind.size();
- A[node[x].HLTind].ind.pb(x);
- A[node[x].HLTind].start=NULL;
- node[x].p[0]=fr;
- return S;
- }
- void up(int x,int upto){
- int HLTi=node[x].HLTind;
- L=node[x].HLTnum;
- if (HLTi==node[upto].HLTind) R=node[upto].HLTnum;
- else R=A[HLTi].ind.size()-1;
- A[HLTi].up(0,A[HLTi].ind.size(),A[HLTi].start);
- if (node[A[HLTi].ind[R]].deep<=node[upto].deep) return;
- up(node[A[HLTi].ind[R]].p[0],upto);
- }
- long long calc(int x,int upto,bool rev,long long RET){
- if (node[x].deep<node[upto].deep) return RET;
- int HLTi=node[x].HLTind;
- L=node[x].HLTnum;
- if (HLTi==node[upto].HLTind) R=node[upto].HLTnum;
- else R=A[HLTi].ind.size()-1;
- if (rev)
- if (node[A[HLTi].ind[R]].deep>node[upto].deep)
- RET= calc(node[A[HLTi].ind[R]].p[0],upto,rev,RET);
- L=node[x].HLTnum;
- if (HLTi==node[upto].HLTind) R=node[upto].HLTnum;
- else R=A[HLTi].ind.size()-1;
- RET=A[HLTi].calc(0,A[HLTi].ind.size(),A[HLTi].start,RET,rev);
- if (!rev)
- if (node[A[HLTi].ind[R]].deep>node[upto].deep)
- RET= calc(node[A[HLTi].ind[R]].p[0],upto,rev,RET);
- return RET;
- }
- int LCA(int x,int y){
- for (int i=15;i>=0;i--)
- if (node[node[x].p[i]].deep>=node[y].deep) x=node[x].p[i]; else
- if (node[node[y].p[i]].deep>=node[x].deep) y=node[y].p[i];
- if (x==y) return x;
- for (int i=15;i>=0;i--)
- if (node[x].p[i]!=node[y].p[i]) x=node[x].p[i],y=node[y].p[i];
- return node[x].p[0];
- }
- int LCAto(int x,int upto){
- for (int i=15;i>=0;i--)
- if (node[node[x].p[i]].deep>node[upto].deep) x=node[x].p[i];
- if (x== upto) return 0;
- return x;
- }
- int main()
- {
- node[0].deep=P;
- tnt=new ele;
- tnt2=new ele;
- // freopen("text","r",stdin);
- scanf("%d",&n);
- for (int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
- for (int x,y,i=1;i<n;i++){
- scanf("%d%d",&x,&y);
- v[x].pb(y);
- v[y].pb(x);
- }
- go(1,1);
- for (int j=1;j<16;j++)
- for (int i=1;i<=n;i++)
- node[i].p[j]=node[node[i].p[j-1]].p[j-1];
- for (int i=0;i<HLTN;i++)
- A[i].bil(0,(int)A[i].ind.size(),A[i].start);
- int query,type,LCAp,startv;
- scanf("%d",&query);
- while (query--){
- scanf("%d",&type);
- if (type==1){
- scanf("%d%d%d%d",&x,&y,&anew,&bnew);
- LCAp=LCA(x,y);
- up(x,LCAp);
- up(y,LCAp);
- }else {
- scanf("%d%d%d",&x,&y,&startv);
- LCAp=LCA(x,y);
- printf("%lld\n",calc(y,LCAto(y,LCAp),1,calc(x,LCAp,0,startv)));
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement