Advertisement
Guest User

Untitled

a guest
Nov 26th, 2014
151
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.96 KB | None | 0 0
  1. #include<math.h>
  2. #include<algorithm>
  3. #include<cstdlib>
  4. #include<iostream>
  5. #include<stdio.h>
  6. #include<map>
  7. #include<set>
  8. #include<string>
  9. #include<assert.h>
  10. #include<vector>
  11. #include<ctime>
  12. #include<queue>
  13. #include<deque>
  14. #include<sstream>
  15. #include<stack>
  16. #include<sstream>
  17. #define MA(a,b) ((a)>(b)?(a):(b))
  18. #define MI(a,b) ((a)<(b)?(a):(b))
  19. #define AB(a) (-(a)<(a)?(a):-(a))
  20. #define X first
  21. #define Y second
  22. #define mp make_pair
  23. #define pb push_back
  24. #define pob pop_back
  25. #define ep 0.000001
  26. #define pi 3.1415926535897932384626433832795
  27. #define na(x) ((x)<P?(x):(x)-P)
  28. using namespace std;
  29. const int N=50001;
  30. const long long P=1000000007;
  31. int n,a[N],b[N],x,y,anew,bnew,L,R;
  32. vector <int> v[N];
  33. struct ele {
  34.     bool f;
  35.     long long fa,fb;
  36.     long long a,b,br;
  37.     ele *l,*r;
  38. } *tnt,*tnt2;
  39. struct HLT{
  40.     vector <int> ind;
  41.     ele *start;
  42.     inline ele *mk(){
  43.         ele *t=(ele*)malloc(sizeof(ele));
  44.         t->a=t->b=t->br=0;
  45.         t->f=0;
  46.         t->l=t->r=NULL;
  47.         return t;
  48.     }
  49.     inline void add(ele *&t,ele *L,ele *R){
  50.        t->a=(L->a*R->a)%P;
  51.        t->b=(L->b*R->a+R->b)%P;
  52.        t->br=(R->br*L->a+L->br)%P;
  53.     }
  54.     inline void add2(ele *&t,ele *L,ele *R){
  55.        t->b=(L->b*R->a+R->b)%P;
  56.        t->a=(L->a*R->a)%P;
  57.     }
  58.     inline void po(ele *&t,int x){
  59.         tnt->a=t->fa;
  60.         tnt->b=t->fb;
  61.         t->a=1;
  62.         t->b=0;
  63.         while (x){
  64.             if (x&1) add2(t,t,tnt);
  65.             x>>=1;
  66.             add2(tnt,tnt,tnt);
  67.         }
  68.         t->br=t->b;
  69.     }
  70.     void bil(int l,int r,ele *&t){
  71.         if (t==NULL) t=mk();
  72.         if (l+1==r) {
  73.             t->a=a[ind[l]];
  74.             t->b=t->br=b[ind[l]];
  75.             return;
  76.         }
  77.             bil(l,(l+r)/2,t->l);
  78.             bil((l+r)/2,r,t->r);
  79.             add(t,t->l,t->r);
  80.     }
  81.     void up(int l,int r,ele *&t){
  82.         if (R<l || r-1<L) return;
  83.         if (L<=l && r-1<=R){
  84.             t->f=1;
  85.             t->fa=anew;
  86.             t->fb=bnew;
  87.             po(t,r-l);
  88.             return;
  89.         }
  90.         if (t->f){
  91.             t->l->fa=t->fa;
  92.             t->l->fb=t->fb;
  93.             t->l->f=1;
  94.             po(t->l,(l+r)/2-l);
  95.             t->r->fa=t->fa;
  96.             t->r->fb=t->fb;
  97.             t->r->f=1;
  98.             po(t->r,r-(l+r)/2);
  99.             t->f=0;
  100.         }
  101.         up(l,(l+r)/2,t->l);
  102.         up((l+r)/2,r,t->r);
  103.         add(t,t->l,t->r);
  104.     }
  105.     long long calc(int l,int r,ele *t,long long x,bool rev){
  106.         if (L<=l && r-1<=R) return (t->a*x+(rev?t->br:t->b))%P;
  107.         if (r-1<L || R<l) return x;
  108.         if (t->f){
  109.             tnt2->fa=t->fa;
  110.             tnt2->fb=t->fb;
  111.             po(tnt2,MI(R,r-1)-MA(l,L)+1);
  112.             return (tnt2->a*x+(rev?tnt2->br:tnt2->b))%P;
  113.         }
  114.         if ( rev) return calc(l,(l+r)/2,t->l,calc((l+r)/2,r,t->r,x,rev),rev);
  115.         if (!rev) return calc((l+r)/2,r,t->r,calc(l,(l+r)/2,t->l,x,rev),rev);
  116.         return 0ll;
  117.     }
  118. } A[N];
  119. struct mis{
  120.     int HLTind,HLTnum,p[16],deep;
  121. } node[N];
  122.  
  123. int HLTN;
  124. int go(int x,int fr)
  125. {
  126.     node[x].deep=node[fr].deep+1;
  127.     int S=1;
  128.     vector <int> s;
  129.     for (int i=0;i<v[x].size();i++) s.pb(v[x][i]!=fr?go(v[x][i],x):0),S+=s[i];
  130.     bool fin=0;
  131.     for (int i=0;i<v[x].size();i++)
  132.         if (S<=s[i]*2){
  133.             node[x].HLTind=node[v[x][i]].HLTind;
  134.             fin=1;
  135.         }
  136.     if (fin==0) node[x].HLTind=HLTN,HLTN++;
  137.     node[x].HLTnum=A[node[x].HLTind].ind.size();
  138.     A[node[x].HLTind].ind.pb(x);
  139.     A[node[x].HLTind].start=NULL;
  140.     node[x].p[0]=fr;
  141.     return S;
  142. }
  143.  
  144. void up(int x,int upto){
  145.     int HLTi=node[x].HLTind;
  146.     L=node[x].HLTnum;
  147.     if (HLTi==node[upto].HLTind) R=node[upto].HLTnum;
  148.                       else       R=A[HLTi].ind.size()-1;
  149.     A[HLTi].up(0,A[HLTi].ind.size(),A[HLTi].start);
  150.     if (node[A[HLTi].ind[R]].deep<=node[upto].deep) return;
  151.     up(node[A[HLTi].ind[R]].p[0],upto);
  152. }
  153. long long calc(int x,int upto,bool rev,long long RET){
  154.     if (node[x].deep<node[upto].deep) return RET;
  155.     int HLTi=node[x].HLTind;
  156.     L=node[x].HLTnum;
  157.     if (HLTi==node[upto].HLTind) R=node[upto].HLTnum;
  158.                     else       R=A[HLTi].ind.size()-1;
  159.     if (rev)
  160.     if (node[A[HLTi].ind[R]].deep>node[upto].deep)
  161.     RET= calc(node[A[HLTi].ind[R]].p[0],upto,rev,RET);
  162.  
  163.     L=node[x].HLTnum;
  164.     if (HLTi==node[upto].HLTind) R=node[upto].HLTnum;
  165.                     else       R=A[HLTi].ind.size()-1;
  166.  
  167.     RET=A[HLTi].calc(0,A[HLTi].ind.size(),A[HLTi].start,RET,rev);
  168.  
  169.  
  170.     if (!rev)
  171.     if (node[A[HLTi].ind[R]].deep>node[upto].deep)
  172.     RET= calc(node[A[HLTi].ind[R]].p[0],upto,rev,RET);
  173.     return RET;
  174. }
  175.  
  176. int LCA(int x,int y){
  177.     for (int i=15;i>=0;i--)
  178.         if (node[node[x].p[i]].deep>=node[y].deep) x=node[x].p[i]; else
  179.         if (node[node[y].p[i]].deep>=node[x].deep) y=node[y].p[i];
  180.     if (x==y) return x;
  181.     for (int i=15;i>=0;i--)
  182.         if (node[x].p[i]!=node[y].p[i]) x=node[x].p[i],y=node[y].p[i];
  183.     return node[x].p[0];
  184. }
  185. int LCAto(int x,int upto){
  186.     for (int i=15;i>=0;i--)
  187.     if (node[node[x].p[i]].deep>node[upto].deep) x=node[x].p[i];
  188.     if (x== upto) return 0;
  189.     return x;
  190. }
  191. int main()
  192. {
  193.   node[0].deep=P;
  194.   tnt=new ele;
  195.   tnt2=new ele;
  196.   //  freopen("text","r",stdin);
  197.   scanf("%d",&n);
  198.   for (int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
  199.   for (int x,y,i=1;i<n;i++){
  200.     scanf("%d%d",&x,&y);
  201.     v[x].pb(y);
  202.     v[y].pb(x);
  203.   }
  204.   go(1,1);
  205.   for (int j=1;j<16;j++)
  206.     for (int i=1;i<=n;i++)
  207.         node[i].p[j]=node[node[i].p[j-1]].p[j-1];
  208.   for (int i=0;i<HLTN;i++)
  209.   A[i].bil(0,(int)A[i].ind.size(),A[i].start);
  210.   int query,type,LCAp,startv;
  211.   scanf("%d",&query);
  212.   while (query--){
  213.     scanf("%d",&type);
  214.     if (type==1){
  215.         scanf("%d%d%d%d",&x,&y,&anew,&bnew);
  216.         LCAp=LCA(x,y);
  217.         up(x,LCAp);
  218.         up(y,LCAp);
  219.     }else {
  220.         scanf("%d%d%d",&x,&y,&startv);
  221.         LCAp=LCA(x,y);
  222.         printf("%lld\n",calc(y,LCAto(y,LCAp),1,calc(x,LCAp,0,startv)));
  223.     }
  224.   }
  225.   return 0;
  226. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement