fork(2) 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.  
  13. using namespace std;
  14.  
  15. #define fi first
  16. #define sc second
  17. #define ff first.first
  18. #define fs first.second
  19. #define sf second.first
  20. #define ss second.second
  21. #define pb push_back
  22. #define mp make_pair
  23. #define ll long long
  24. #define dl double
  25. #define ison(a,b) (a&(1<<b))
  26. #define bitcnt __builtin_popcount
  27. #define MOD 1000000007 
  28.  
  29. typedef pair<ll,ll> ii;
  30. typedef pair<ll,ii> iii;
  31. typedef vector<ll> vi;
  32. typedef vector<ii> vii;
  33. typedef vector<iii> wadj;
  34.  
  35. const ll N=1e5+5;
  36. const ll LN=18;
  37. ll parent[N],sub_size[N],depth[N];
  38. ll chead[N],cind[N];
  39. ll cno,lazy[4*N],ptr,pib[N],bsa[N],a[N];
  40. iii st[4*N];
  41. vi adj[N];
  42.  
  43. ll gcd(ll a,ll b)
  44. {
  45.   a=abs(a),b=abs(b);
  46.   if(b>a)
  47.   swap(a,b);
  48.   if(b==0)
  49.   return a;
  50.   else
  51.   return gcd(b,a%b);
  52. }
  53.  
  54. ll nlca(ll x,ll y)
  55. {
  56.   while(chead[cind[x]]!=chead[cind[y]])
  57.   {
  58.   if(depth[chead[cind[x]]] > depth[chead[cind[y]]])
  59.     x=parent[chead[cind[x]]];
  60.   else
  61.     y=parent[chead[cind[y]]];
  62.   }
  63.   if(depth[x]>depth[y])
  64.     return y;
  65.   else
  66.     return x;
  67. }
  68.  
  69. iii build(ll p,ll s,ll e)
  70. {
  71.   if(s==e)
  72.   {
  73.     return st[p]=iii(0,ii(bsa[s],bsa[s]));
  74.   }
  75.   build(2*p,s,(s+e)>>1),build(2*p+1,((s+e)>>1)+1,e);
  76.   st[p]=iii(abs(gcd(st[2*p].fi,gcd(st[2*p+1].sf-st[2*p].ss,st[2*p+1].fi))),ii(st[2*p].sf,st[2*p+1].ss));
  77.   return st[p];
  78. }
  79.  
  80. void push(ll p,ll l,ll r)
  81. {
  82.   if(lazy[p])
  83.   {
  84.     st[p].sf+=lazy[p];
  85.     st[p].ss+=lazy[p];
  86.     if(l!=r)
  87.     {
  88.       lazy[2*p]+=lazy[p];
  89.       lazy[2*p+1]+=lazy[p];
  90.     }
  91.     lazy[p]=0;
  92.   }
  93. }
  94.  
  95. void update(ll p,ll s,ll e,ll L,ll R,ll val)
  96. {
  97.   push(p,L,R);
  98.   if(L>e||s>R)
  99.   return;
  100.   if(L>=s&&e>=R)
  101.   {
  102.     lazy[p]+=val;
  103.     push(p,L,R);
  104.     return;
  105.   }
  106.   update(2*p,s,e,L,(L+R)>>1,val);
  107.   update(2*p+1,s,e,((L+R)>>1)+1,R,val);
  108.   st[p]=iii(gcd(st[2*p].fi,gcd(st[2*p+1].sf-st[2*p].ss,st[2*p+1].fi)),ii(st[2*p].sf,st[2*p+1].ss));
  109.  
  110. }
  111.  
  112. ll query_tree(ll p,ll s,ll e,ll L,ll R)
  113. {
  114.   push(p,L,R);
  115.   if(L>e||R<s)
  116.   return 0;
  117.   if(L>=s&&R<=e)
  118.   return gcd(st[p].fi,st[p].sf);
  119.   return gcd(query_tree(2*p,s,e,L,((L+R)>>1)),query_tree(2*p+1,s,e,((L+R)>>1)+1,R));
  120. }
  121.  
  122. ll query_up(ll u,ll v)
  123. {
  124.   ll uch,vch=cind[v],ans=0;
  125.   while(1)
  126.   {
  127.     uch=cind[u];
  128.     if(uch==vch)
  129.     {
  130.       ll t=query_tree(1,pib[v],pib[u],1,ptr);
  131.       ans=gcd(ans,t);
  132.       break;
  133.     }
  134.     ll t=query_tree(1,pib[chead[uch]],pib[u],1,ptr);
  135.     ans=gcd(ans,t);
  136.     u=chead[uch];
  137.     u=parent[u];
  138.  
  139.   }
  140.   return ans;
  141. }
  142.  
  143. void change_up(ll u,ll v,ll val)
  144. {
  145.   ll uch,vch=cind[v];
  146.   while(1)
  147.   {
  148.     uch=cind[u];
  149.     if(uch==vch)
  150.     {
  151.       update(1,pib[v],pib[u],1,ptr,val);
  152.       break;
  153.     }
  154.     update(1,pib[chead[uch]],pib[u],1,ptr,val);
  155.     u=chead[uch];
  156.     u=parent[u];  }
  157. }
  158. void query(ll u,ll v)
  159. {
  160.   ll l=nlca(u,v);
  161.   ll q1=query_up(u,l);
  162.   ll q2=query_up(v,l);
  163.   printf("%lld\n",gcd(q1,q2));
  164. }
  165.  
  166. void change(ll u,ll v,ll val)
  167. {
  168.   //printf("change\n" );
  169.   ll l=nlca(u,v);
  170.   change_up(u,l,val);
  171.   change_up(v,l,val);
  172.   change_up(l,l,-val);
  173.  
  174. }
  175. void dfs(ll u1,ll p)
  176. {
  177.   parent[u1]=p;
  178.   sub_size[u1]=1;
  179.   for(ll i=0;i<adj[u1].size();i++)
  180.   {
  181.     ll v=adj[u1][i];
  182.     if(v!=p)
  183.     {
  184.       depth[v]=depth[u1]+1;
  185.       dfs(v,u1);
  186.       sub_size[u1]+=sub_size[v];
  187.     }
  188.   }
  189. }
  190.  
  191.  
  192. void hld(ll u,ll p)
  193. {
  194.   if(chead[cno]==0)
  195.   chead[cno]=u;
  196.   cind[u]=cno;
  197.   pib[u]=ptr;
  198.   bsa[ptr]=a[u];
  199.   ptr++;
  200.   ll sc=-1,nc;
  201.   for(ll i=0;i<adj[u].size();i++)
  202.   if(adj[u][i]!=p)
  203.   {
  204.     if(sc==-1||sub_size[sc]<sub_size[adj[u][i]])
  205.     {
  206.       sc=adj[u][i];
  207.     }
  208.   }
  209.   if(sc!=-1)
  210.   hld(sc,u);
  211.   for(ll i=0;i<adj[u].size();i++)
  212.   if(adj[u][i]!=sc&&adj[u][i]!=p)
  213.   {
  214.     cno++;
  215.     hld(adj[u][i],u);
  216.   }
  217. }
  218.  
  219. void pre()
  220. {
  221.   depth[1]=0;
  222.   dfs(1,0);
  223.   cno=ptr=1;
  224.   hld(1,0);
  225.   ptr--;
  226.   build(1,1,ptr);
  227. }
  228. int main(int argc, char const *argv[])
  229. {
  230. //freopen("inp.txt","r",stdin);
  231.  ll n;
  232.  cin>>n;
  233.  for(ll i=1;i<n;i++)
  234.  {
  235.   ll a,b;
  236.   scanf("%lld%lld",&a,&b);
  237.   adj[a+1].pb(b+1);
  238.   adj[b+1].pb(a+1);
  239.  }
  240.  for(ll i=1;i<=n;i++)
  241.   scanf("%lld",&a[i]);
  242.  pre();
  243.  ll q;
  244.  cin>>q;
  245.  while(q--)
  246.  {
  247.   char c;
  248.   ll u,v,d;
  249.   cin>>c;
  250.   scanf("%lld%lld",&u,&v);
  251.     u++,v++;
  252.   if(c=='F')
  253.     query(u,v);
  254.   else
  255.   {
  256.     scanf("%lld",&d);
  257.     change(u,v,d);
  258.   }
  259.  }
  260.  
  261.     return 0;
  262. }
Runtime error #stdin #stdout 0s 23392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/aUlGTZ
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!