fork download
copy 
  1. /*
  2. * @Author: hungeazy
  3. * @Date:   2024-09-12 22:14:27
  4. * @Last Modified by:   hungeazy
  5. * @Last Modified time: 2024-12-12 21:35:00
  6. */
  7. #include <bits/stdc++.h>
  8. #include <ext/pb_ds/assoc_container.hpp> 
  9. #include <ext/pb_ds/tree_policy.hpp> 
  10. // #pragma GCC optimize("O3")  
  11. // #pragma GCC optimize("unroll-loops")  
  12. // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")  
  13. using namespace std;
  14. using namespace __gnu_pbds; 
  15. #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  16. #define int long long
  17. #define ll long long 
  18. #define ull unsigned long long
  19. #define sz(x) x.size()
  20. #define sqr(x) (1LL * (x) * (x))
  21. #define all(x) x.begin(), x.end()
  22. #define fill(f,x) memset(f,x,sizeof(f))
  23. #define FOR(i,l,r) for(int i=l;i<=r;i++)
  24. #define FOD(i,r,l) for(int i=r;i>=l;i--)
  25. #define debug(x) cout << #x << " = " << x << '\n'
  26. #define ii pair<int,int>
  27. #define iii pair<int,ii>
  28. #define di pair<ii,ii>
  29. #define vi vector<int>
  30. #define vii vector<ii>
  31. #define mii map<int,int>
  32. #define fi first
  33. #define se second
  34. #define pb push_back
  35. #define MOD 1000000007
  36. #define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
  37. #define YES cout << "YES\n"
  38. #define NO cout << "NO\n"
  39. #define MASK(i) (1LL << (i))
  40. #define c_bit(i) __builtin_popcountll(i)
  41. #define BIT(x,i) ((x) & MASK(i))
  42. #define SET_ON(x,i) ((x) | MASK(i))
  43. #define SET_OFF(x,i) ((x) & ~MASK(i))
  44. #define oo 1e18
  45. #define name ""
  46. #define endl '\n'
  47. // #define time() cerr << endl << "-------------Time:" << 1000.0 * clock() / CLOCKS_PER_SEC << "ms.";
  48. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
  49. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
  50. template <class T> using ordered_set = tree <T, null_type, less_equal <T>, rb_tree_tag,tree_order_statistics_node_update>;
  51. mt19937 rnd;
  52. const int N = (int)2e5+10;
  53. int a[N],n,q;
  54. vi g[N];
  55. ii query[N];
  56.  
  57. namespace hungeazy {
  58.  
  59. 	struct Query {
  60. 		int l,r,id,lca;
  61. 	} b[N];
  62.  
  63. 	int in[N],out[N],tour[N],cnt=0,S;
  64. 	int par[N][20],h[N],dem[N],ans[N];
  65. 	bool visited[N];
  66.  
  67. 	int randRange(int l, int r)
  68. 	{
  69. 		return uniform_int_distribution<int>(l,r)(rnd);
  70. 	}
  71.  
  72. 	void DFS(int u, int p)
  73. 	{
  74. 		in[u] = ++cnt;
  75. 		tour[cnt] = u;
  76. 		for (int v : g[u])
  77. 			if (v != p) 
  78. 			{
  79. 				h[v] = h[u]+1;
  80. 				par[v][0] = u;
  81. 				DFS(v,u);
  82. 			}
  83. 		out[u] = ++cnt;
  84. 		tour[cnt] = u;
  85. 	}
  86.  
  87. 	void init()
  88. 	{
  89. 		FOR(j,1,log2(n))
  90. 			FOR(i,1,n) par[i][j] = par[par[i][j-1]][j-1];
  91. 	}
  92.  
  93. 	int LCA(int x, int y)
  94. 	{
  95. 		if (h[x] < h[y]) swap(x,y);
  96. 		int z = log2(n);
  97. 		FOD(i,z,0)
  98. 			if (h[x]-h[y] >= MASK(i)) x = par[x][i];
  99. 		if (x == y) return x;
  100. 		FOD(i,z,0)
  101. 			if (par[x][i] != par[y][i]) x = par[x][i], y = par[y][i];
  102. 		return par[x][0];
  103. 	}
  104.  
  105. 	bool cmp(Query &x, Query &y)
  106. 	{
  107. 		if (x.l/S != y.l/S) return x.l < y.l;
  108. 		return x.r < y.r;
  109. 	}
  110.  
  111. 	void calc(int x)
  112. 	{
  113. 		if (visited[x]) dem[a[x]]--;
  114. 		else dem[a[x]]++;
  115. 		visited[x] ^= 1;
  116. 	}
  117.  
  118. 	void solve(void)
  119. 	{
  120. 		DFS(1,-1);
  121. 		init();
  122. 		// FOR(i,1,n) cout << in[i] << " " << out[i] << endl;
  123. 		S = sqrt(q);
  124. 		FOR(i,1,q)
  125. 		{
  126. 			int u,v;
  127. 			tie(u,v) = query[i];
  128. 			b[i].lca = LCA(u,v);
  129. 			if (in[u] > in[v]) swap(u,v);
  130. 			if (b[i].lca == u) b[i].l = in[u], b[i].r = in[v];
  131. 			else b[i].l = out[u], b[i].r = in[v];
  132. 			b[i].id = i;
  133. 		}
  134. 		sort(b+1,b+q+1,cmp);
  135. 		int l = 1, r = 0;
  136. 		FOR(i,1,q)
  137. 		{
  138. 			while (l < b[i].l)
  139. 			{
  140. 				calc(tour[l]);
  141. 				l++;
  142. 			}
  143. 			while (l > b[i].l)
  144. 			{
  145. 				l--;
  146. 				calc(tour[l]);
  147. 			}
  148. 			while (r < b[i].r)
  149. 			{
  150. 				r++;
  151. 				calc(tour[r]);
  152. 			}
  153. 			while (r > b[i].r)
  154. 			{
  155. 				calc(tour[r]);
  156. 				r--;
  157. 			}
  158. 			if (b[i].lca != tour[b[i].l] and b[i].lca != tour[b[i].r])
  159. 				calc(b[i].lca);
  160. 			int val = -1, u = tour[b[i].l], v = tour[b[i].r], k = h[u]+h[v]-2*h[LCA(u,v)];
  161. 			FOR(rep,1,50)
  162. 			{
  163. 				int x = randRange(1,n);
  164. 				if (dem[a[x]] >= (k+1)/2+1)
  165. 				{
  166. 					val = a[x];
  167. 					break;
  168. 				}
  169. 			}
  170. 			ans[b[i].id] = val;
  171. 			if (b[i].lca != tour[b[i].l] and b[i].lca != tour[b[i].r])
  172. 				calc(b[i].lca);
  173. 		}
  174. 		FOR(i,1,q) cout << ans[i] << endl;
  175. 	}
  176.  
  177. }
  178.  
  179. signed main()
  180. {
  181.     fast;
  182.     if (fopen(name".inp","r"))
  183.     {
  184.     	freopen(name".inp","r",stdin);
  185.     	freopen(name".out","w",stdout);
  186.     }
  187.     rnd.seed(time(0));
  188.     cin >> n >> q;
  189.     FOR(i,1,n) cin >> a[i];
  190.     FOR(i,1,n-1)
  191.     {
  192.     	int u,v;
  193.     	cin >> u >> v;
  194.     	g[u].pb(v); g[v].pb(u);
  195.     }
  196.     FOR(i,1,q) cin >> query[i].fi >> query[i].se;
  197.     hungeazy::solve();
  198.     // time();
  199.     return 0;
  200. }
Success #stdin #stdout 0.01s 13884KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Ixwfpi
language:
C++14 (gcc 8.3)
created:
6 hours 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!