fork download
copy 
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <vector>
  4. #include <stack>
  5. #include <queue>
  6. #include <stdlib.h>
  7. #include <math.h>
  8. #include <cstring>
  9. #include <algorithm>
  10. #include <map>
  11. #include <set>
  12. #include <assert.h>
  13.  
  14. using namespace std;
  15.  
  16. #define fi first
  17. #define sc second
  18. #define ff first.first
  19. #define fs first.second
  20. #define sf second.first
  21. #define ss second.second
  22. #define pb push_back
  23. #define mp make_pair
  24. #define ll long long
  25. #define dl double
  26. #define ison(a,b) (a&(1<<b))
  27. #define bitcnt __builtin_popcount
  28. #define MOD 1000000007 
  29.  
  30. typedef pair<int,int> ii;
  31. typedef pair<int,ii> iii;
  32. typedef vector<int> vi;
  33. typedef vector<ii> vii;
  34. typedef vector<iii> wadj;
  35.  
  36. const int N=5e4+5;
  37. int parent[N],sub_size[N],depth[N];
  38. int chead[N];
  39. int cno,ptr,pib[N],bsa[N],a[N],n,q,lazy[4*N];
  40. vi adj[N];
  41.  
  42. struct node{
  43.     int start;
  44.     int finish;
  45.     int gcd1;
  46. };
  47. node segtree[4*N];
  48.  
  49. void scanint(int &x)
  50. {
  51.     register int c = getchar_unlocked();
  52.     x = 0;
  53.     for(;(c<48 || c>57);c = getchar_unlocked());
  54.     for(;c>47 && c<58;c = getchar_unlocked()) {x = (x<<1) + (x<<3) + c - 48;}
  55. }
  56.  
  57. char scanc(){
  58.     char c = getchar_unlocked();
  59.     while(c < 'C' || c > 'F'){
  60.         c = getchar_unlocked();
  61.     }
  62.     return c;
  63. }
  64.  
  65. int gcd(int a,int b)
  66. {
  67.   a=abs(a);b=abs(b);
  68.   if(b>a)
  69.   swap(a,b);
  70.   if(b==0)
  71.   return a;
  72.   else
  73.   return gcd(b,a%b);
  74. }
  75.  
  76. inline void combine(node &l , node &r,node &temp){
  77.     temp.start = l.start;
  78.     temp.finish = r.finish;
  79.     temp.gcd1 = gcd(gcd(r.start - l.finish , r.gcd1 ) , l.gcd1);
  80. }
  81.  
  82.  
  83.     void build(int l , int r , int node){
  84.         lazy[node] = 0;
  85.         if(l == r){
  86.             segtree[node].start = bsa[l];
  87.             segtree[node].finish = bsa[r];
  88.             segtree[node].gcd1 = 0;
  89.         }
  90.         else{
  91.             int mid = (l + r) >> 1;
  92.             int lc = node + node;
  93.             int rc = lc | 1;
  94.             build(l , mid , lc);
  95.             build(mid + 1 , r , rc);
  96.             combine(segtree[lc] , segtree[rc] , segtree[node]);
  97.         }
  98.     }
  99.     void push(int l , int r , int node){
  100.         if(lazy[node]){
  101.             segtree[node].start += lazy[node];
  102.             segtree[node].finish += lazy[node];
  103.             if(l ^ r){
  104.                 int lc = node + node;
  105.                 int rc = lc | 1;
  106.                 lazy[lc] += lazy[node];
  107.                 lazy[rc] += lazy[node];
  108.             }
  109.             lazy[node] = 0;
  110.         }
  111.     }
  112.     void update1(int l , int r , int node , int ql ,int qr , int val){
  113.         push(l,r,node);
  114.         if(l > qr || r < ql){
  115.             return;
  116.         }
  117.         if(l >= ql && r <= qr){
  118.             lazy[node] += val;
  119.             push(l,r,node);
  120.             return;
  121.         }
  122.         int mid = (l + r) >> 1;
  123.         int lc = node + node;
  124.         int rc = lc | 1;
  125.         update1(l,mid,lc,ql,qr,val);
  126.         update1(mid+1,r,rc,ql,qr,val);
  127.         combine(segtree[lc] , segtree[rc] , segtree[node]);
  128.     }
  129.     int query1(int l , int r , int node, int ql , int qr){
  130.         push(l,r,node);
  131.         if(l > qr || r < ql){
  132.             return 0;
  133.         }
  134.         if(l >= ql && r <= qr){
  135.             return gcd(segtree[node].start , segtree[node].gcd1);
  136.         }
  137.         int mid = (l + r) >> 1;
  138.         int lc = node + node;
  139.         int rc = lc | 1;
  140.         return gcd(query1(l,mid,lc,ql,qr),query1(mid+1,r,rc,ql,qr));
  141.     }
  142.     inline void update(int l , int r , int val){
  143.         update1(1,n,1,l,r,val);
  144.     }
  145.     inline int query(int l , int r){
  146.         return query1(1,n,1,l,r);
  147.     }
  148.  
  149. void dfs(int u1,int p)
  150. {
  151.   parent[u1]=p;
  152.   sub_size[u1]=1;
  153.   for(int i=0;i<adj[u1].size();i++)
  154.   {
  155.     ll v=adj[u1][i];
  156.     if(v!=p)
  157.     {
  158.       depth[v]=depth[u1]+1;
  159.       dfs(v,u1);
  160.       sub_size[u1]+=sub_size[v];
  161.     }
  162.   }
  163. }
  164. void hld(ll u,ll p)
  165. {
  166.   //printf("(hh)\n" );
  167.   pib[u]=++ptr;
  168.   bsa[ptr]=a[u];
  169.   ll sc=-1,nc;
  170.   for(ll i=0;i<adj[u].size();i++)
  171.   if(adj[u][i]!=p)
  172.     if(sc==-1||sub_size[sc]<sub_size[adj[u][i]])
  173.       sc=adj[u][i];
  174.   if(sc!=-1)
  175.   {
  176.     chead[sc]=chead[u];
  177.     hld(sc,u);
  178.   }
  179.   for(int i=0;i<adj[u].size();i++)
  180.   if(adj[u][i]!=sc&&adj[u][i]!=p)
  181.   {
  182.     chead[adj[u][i]]=adj[u][i];
  183.     hld(adj[u][i],u);
  184.   }
  185. }
  186. void upd(ll u,ll v,ll val)
  187. {
  188.   while(chead[u]!=chead[v])
  189.   {
  190.     if(depth[chead[u]]<depth[chead[v]])
  191.       swap(u,v);
  192.     update(pib[chead[u]],pib[u],val);
  193.     u=parent[chead[u]];
  194.   }
  195.   if(depth[u]>depth[v])
  196.     swap(u,v);
  197.   update(pib[u],pib[v],val);
  198. }
  199.  
  200. int solve(int u,int v)
  201. {
  202.   int ans=0;
  203.   while(chead[u]!=chead[v])
  204.   {
  205.  
  206.     if(depth[chead[u]]<depth[chead[v]])
  207.       swap(u,v);
  208.     ans=gcd(ans,query(pib[chead[u]],pib[u]));
  209.     u=parent[chead[u]];
  210.   }
  211.   if(depth[u]>depth[v])
  212.     swap(u,v);
  213.   ans=gcd(ans,query(pib[u],pib[v]));
  214.   return ans;
  215. }
  216.  
  217. void pre()
  218. {
  219.   dfs(1,0);
  220.   chead[1]=1;
  221.   hld(1,0);
  222.  build(1,n,1);
  223. }
  224. int main(){
  225.   //freopen("inp.txt","r",stdin);
  226.     scanint(n);
  227.     for(int i = 1 ; i < n ; ++i){
  228.         int a,b;
  229.         scanint(a);scanint(b);
  230.         adj[a+1].pb(b+1);
  231.         adj[b+1].pb(a+1);
  232.     }
  233.     for(int i = 1 ; i <= n ; ++i)
  234.       scanint(a[i]);
  235.     pre();
  236.     int q;
  237.     scanint(q);
  238.     while(q--){
  239.         char type = scanc();
  240.         int l,r,val;
  241.         scanint(l);scanint(r);
  242.         l++,r++;
  243.         if(type=='F'){
  244.             printf("%d\n",solve(l,r));
  245.         }
  246.         else{
  247.             scanint(val);
  248.             upd(l,r,val);
  249.         }
  250.     }
  251. }
Time limit exceeded #stdin #stdout 5s 8496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/m7wSJ0
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!