fork download
copy 
  1. /*...Part - 01...*/
  2.  
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cstring>
  8. #include <string>
  9. #include <cmath>
  10. #include <vector>
  11. #include <set>
  12. #include <map>
  13. #include <unordered_set>
  14. #include <unordered_map>
  15. #include <stack>
  16. #include <queue>
  17. #include <deque>
  18. #include <iterator>
  19. #include <bitset>
  20. #include <assert.h>
  21. #include <new>
  22. #include <sstream>
  23. //#include <bits/stdc++.h>
  24. using namespace std ;
  25.  
  26. /*...Part - 02...*/
  27.  
  28. typedef long long               ll ;
  29. typedef long double             ld ;
  30. typedef unsigned long long      ull ;
  31. typedef pair<int,int>           pii ;
  32. typedef pair<ll,ll>             pll ;
  33. typedef vector<int>             vi ;
  34. typedef vector<ll>              vll ;
  35. typedef vector<vector<int>>     vvi ;
  36.  
  37. int Int(){int x ; scanf("%d",&x) ; return x ;}
  38. ll Long(){ll x ; scanf("%lld",&x) ; return x ;}
  39.  
  40. /*...Part - 03...*/
  41. /*....Debugger....*/
  42.  
  43. #define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
  44. void err(istream_iterator<string> it) {cout << endl ;}
  45. template<typename T, typename... Args>
  46. void err(istream_iterator<string> it, T a, Args... args) {
  47.     cerr << *it << " = " << a << ' ' ;
  48.     err(++it, args...);
  49. }
  50.  
  51. /*...Part - 04...*/
  52. /*...Needed to change according to problem requirements...*/
  53.  
  54. const int N          = (int)5e4 + 5 ;
  55. const int maxN       = (int)1e6 + 6 ;
  56. const ll  Mod        = (ll)1e9 + 7 ;
  57. const int inf        = (int)2e9 ;
  58. const ll  Inf        = (ll)1e18 ;
  59.  
  60. /*..........................................................*/
  61. /*...Part - 05...*/
  62.  
  63. #define     debug(x)    cerr << #x << " = " << x << '\n' ;
  64. #define     rep(i,b,e)  for(__typeof(e) i = (b) ; i != (e + 1) - 2 * ((b) > (e))  ; i += 1 - 2 * ((b) > (e)))
  65. #define     Int         Int()
  66. #define     Long        Long()
  67. #define     all(x)      x.begin() , x.end()
  68. #define     sz(x)       (int)x.size()
  69. #define     ff          first
  70. #define     ss          second
  71. #define     pb          push_back
  72. #define     eb          emplace_back
  73. #define     mem(a)      memset(a , 0 ,sizeof a)
  74. #define     memn(a)     memset(a , -1 ,sizeof a)
  75.  
  76. /*...Part - 06...*/
  77. /*...... ! Code start from here ! ......*/
  78.  
  79. vvi g ;
  80. int chainHead[N], chainID[N], cost[N], pos[N], chainNo, cur;
  81. int a[N], par[N][17], dep[N], subsz[N], tree[N << 2], n;
  82.  
  83.  
  84. void dfs(int s , int p = -1){
  85. 	dep[s] = 1 + dep[p] ;
  86. 	par[s][0] = p ;
  87. 	subsz[s] = 1 ;
  88. 	for(int i = 1 ; i < 16 ; ++i)
  89. 		par[s][i] = par[par[s][i - 1]][i - 1] ;
  90. 	for(int i : g[s]){
  91. 		if(i != p){
  92. 			dfs(i, s);
  93. 			subsz[s] += subsz[i];
  94. 		}
  95. 	}
  96. }
  97.  
  98.  
  99. void HLD(int s, int p = -1){
  100. 	if(chainHead[chainNo] == -1){
  101. 		chainHead[chainNo] = s ;
  102. 	}
  103. 	chainID[s] = chainNo ;
  104. 	pos[s] = ++cur ;
  105. 	a[cur] = cost[s] ;
  106. 	int id = -1, mx = -1 ;
  107. 	for(int i : g[s]){
  108. 		if(i == p)continue ;
  109. 		if(subsz[i] > mx){
  110. 			mx = subsz[i] ;
  111. 			id = i ;
  112. 		}
  113. 	}
  114. 	if(id != -1)HLD(id, s) ;
  115. 	for(int i : g[s]){
  116. 		if(i == p or i == id)continue ;
  117. 		++chainNo ;
  118. 		HLD(i, s) ;
  119. 	}
  120. }
  121.  
  122. void fresh(){
  123. 	memn(chainHead) ;
  124. 	g.clear() ;
  125. 	mem(tree) ;
  126. 	mem(par) ;
  127. 	chainNo = 0 ;
  128. 	cur = 0 ;
  129. }
  130.  
  131. int gcd(int a, int b){
  132. 	return !b ? a : gcd(b, a % b) ;
  133. }
  134.  
  135. void build(int i , int b, int e){
  136. 	if(b == e){
  137. 		tree[i] = a[b] ;
  138. 		return ;
  139. 	}
  140.  
  141. 	int mid = (b + e) >> 1 ;
  142. 	build(i << 1, b,  mid) ;
  143. 	build(i << 1 | 1, mid + 1, e) ;
  144. 	tree[i] = gcd(tree[i << 1], tree[i << 1 | 1]) ;
  145. }
  146.  
  147. void update(int i, int b, int e, int p, int v){
  148. 	if(p > e or p < b)return ;
  149. 	if(p == b and p == e){
  150. 		tree[i] = v ;
  151. 		return ;
  152. 	}
  153. 	int mid = (b + e) >> 1 ;
  154. 	update(i << 1, b, mid, p, v) ;
  155. 	update(i << 1 | 1, mid + 1, e, p, v) ;
  156. 	tree[i] = gcd(tree[i << 1], tree[i << 1 | 1]) ;
  157. }
  158.  
  159. int query(int i, int b, int e, int l, int r){
  160. 	if(b > r or e < l)return 0 ;
  161. 	if(l <= b and e <= r)return tree[i] ;
  162. 	int mid = (b + e) >> 1 ;
  163. 	return gcd(query(i << 1, b, mid, l, r), query(i << 1 | 1, mid + 1, e, l, r)) ;
  164. }
  165.  
  166. int getLca(int a, int b){
  167. 	if(dep[a] < dep[b])swap(a, b) ;
  168. 	int d = dep[a] - dep[b] ;
  169. 	for(int i = 15 ; i >= 0 ; --i)
  170. 		if(d & (1 << i))a = par[a][i] ;
  171. 	if(a == b)return a ;
  172. 	for(int i = 15 ; i >= 0 ; --i){
  173. 		if(par[a][i] != par[b][i])
  174. 			a = par[a][i], b = par[b][i] ;
  175. 	}
  176. 	return par[a][0] ;
  177. }
  178.  
  179. int chain_query(int u, int v){
  180. 	if(u == v)return cost[u] ;
  181. 	int uchain, vchain = chainID[v], res = 0 ;
  182. 	while(1){
  183. 		uchain = chainID[u] ;
  184. 		if(uchain == vchain){
  185. 			res = gcd(res, query(1, 1, n, pos[v], pos[u])) ;
  186. 			break ;
  187. 		}
  188. 		res = gcd(res, query(1, 1, n, pos[chainHead[uchain]], pos[u])) ;
  189. 		u = chainHead[uchain] ;
  190. 		u = par[u][0] ;
  191. 	}
  192. 	return res ;
  193. }
  194.  
  195. int getResult(int a, int b){
  196. 	int x = getLca(a, b) ;
  197. 	int u = chain_query(a, x) ;
  198. 	int v = chain_query(b, x) ;
  199. 	return gcd(u, v) ;
  200. }
  201.  
  202. int main(){
  203. 	//freopen("input.txt","r",stdin) ;
  204. 	//freopen("output.txt","w",stdout) ;
  205.     while(scanf("%d",&n) == 1){
  206.     	assert(n <= 50000) ;
  207.         fresh() ;
  208.         g.resize(n) ;
  209.         for(int i = 0 ; i < n ; ++i)cost[i] = Int ;
  210.         int x, y ;
  211.         for(int i = 1 ; i < n ; ++i){
  212.         	scanf("%d %d",&x, &y) ;
  213.         	g[x].pb(y) ;
  214.         	g[y].pb(x) ;
  215.         	assert(x >= 0 and x <= n - 1) ;
  216.         	assert(y >= 0 and y <= n - 1) ;
  217.         }
  218.         dfs(0) ;
  219.         HLD(0) ;
  220.         build(1, 1, n) ;
  221.         int q = Int, tp ;
  222.         while(q--){
  223.         	scanf("%d %d %d",&tp, &x, &y) ;
  224.         	assert(x >= 0 and x <= n - 1) ;
  225.         	assert(y >= 0 and y <= n - 1) ;
  226.         	if(tp == 1){
  227.         		printf("%d\n",getResult(x, y));
  228.         	}
  229.         	else{
  230.         		update(1, 1, n, pos[x], y) ;
  231.         		cost[x] = y ;
  232.         	}
  233.         }
  234.     }
  235.     return 0 ;
  236. }
  237.  
  238. /*...Always look at the part - 04...*/
  239. /*...............END................*/
  240.  
  241.  
  242.  
Success #stdin #stdout 0s 20712KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uCiBsz
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!