1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  5. #define endl "\n"
  6. #define int long long
  7.  
  8. const int N = 1e5 + 5;
  9. const int LG = log2(N) + 1;
  10.  
  11. int n, q, ct = 0, num = 1e5;
  12. int a[N], root[N], level[N];
  13. int st[21*N], st2[21*N], lc[21*N], rc[21*N];
  14. int tim=0;
  15. int parent[LG][N];
  16. vector<int> g[N];
  17.  
  18. void dfs0(int k, int par, int lvl)
  19. {
  20. 	parent[0][k] = par;
  21. 	level[k] = lvl;
  22. 	for(auto it:g[k])
  23. 	{
  24. 		if(it==par)
  25. 			continue;
  26. 		dfs0(it, k, lvl+1);
  27. 	}
  28. }
  29.  
  30. void precompute()
  31. {
  32. 	for(int i=1;i<LG;i++)
  33. 		for(int j=1;j<=n;j++)
  34. 			if(parent[i-1][j])
  35. 				parent[i][j]=parent[i-1][parent[i-1][j]];
  36. }
  37.  
  38. int LCA(int u, int v)
  39. {
  40. 	if(level[u]<level[v])
  41. 		swap(u,v);
  42. 	int diff=level[u]-level[v];
  43. 	for(int i=LG-1;i>=0;i--)
  44. 	{
  45. 		if((1<<i) & diff)
  46. 		{
  47. 			u=parent[i][u];
  48. 		}
  49. 	}
  50. 	if(u==v)
  51. 		return u;
  52. 	for(int i=LG-1;i>=0;i--)
  53. 	{
  54. 		if(parent[i][u] && parent[i][u]!=parent[i][v])
  55. 		{
  56. 			u=parent[i][u];
  57. 			v=parent[i][v];
  58. 		}
  59. 	}
  60. 	return parent[0][u];
  61. }
  62.  
  63.  
  64. int build(int L, int R)
  65. {
  66. 	int node = ++ct;
  67. 	if(L==R)
  68. 		return node;
  69. 	int M = (L+R)/2;
  70. 	lc[node] = build(L, M);
  71. 	rc[node] = build(M+1, R);
  72. 	return node;
  73. }
  74.  
  75. int update(int onode, int L, int R, int pos)
  76. {
  77. 	int node = ++ct;
  78. 	if(L==R)
  79. 	{
  80. 		st[node] = st[onode] + 1;
  81. 		st2[node] = st2[onode] + L;
  82. 		return node;
  83. 	}
  84. 	int M = (L+R)/2;
  85. 	lc[node] = lc[onode];
  86. 	rc[node] = rc[onode];
  87. 	if(pos <= M)
  88. 		lc[node] = update(lc[onode], L, M, pos);
  89. 	else
  90. 		rc[node] = update(rc[onode], M+1, R, pos);
  91. 	st[node] = st[lc[node]] + st[rc[node]];
  92. 	st2[node] = st2[lc[node]] + st2[rc[node]];
  93. 	return node;
  94. }
  95.  
  96. int query(int nodeu, int nodev, int nodelca, int nodelcapar, int L, int R, int pos)
  97. {
  98. 	if(L==R)
  99. 	{
  100. 		int have = st[nodeu] + st[nodev] - st[nodelca] - st[nodelcapar];
  101. 		int canDefeat = pos/L;
  102. 		return min(have, canDefeat);
  103. 	}
  104. 	int M = (L+R)/2;
  105. 	int leftval = st2[lc[nodeu]] + st2[lc[nodev]] - st2[lc[nodelca]] - st2[lc[nodelcapar]];
  106. 	int rightval = st2[rc[nodeu]] + st2[rc[nodev]] - st2[rc[nodelca]] - st2[rc[nodelcapar]];
  107. 	int defeated = st[lc[nodeu]] + st[lc[nodev]] - st[lc[nodelca]] - st[lc[nodelcapar]];
  108. 	if(leftval > pos)
  109. 		return query(lc[nodeu], lc[nodev], lc[nodelca], lc[nodelcapar], L, M, pos);
  110. 	else
  111. 		return defeated + query(rc[nodeu], rc[nodev], rc[nodelca], rc[nodelcapar], M+1, R, pos - leftval);
  112. }
  113.  
  114. void dfs(int u, int par)
  115. {
  116. 	int onode = root[par];
  117. 	root[u] = update(onode, 1, num, a[u]);
  118. 	for(auto &it:g[u])
  119. 	{
  120. 		if(it==par)
  121. 			continue;
  122. 		dfs(it, u);
  123. 	}
  124. }
  125.  
  126. int32_t main()
  127. {
  128. 	IOS;
  129. 	cin>>n;
  130. 	for(int i=1;i<=n;i++)
  131. 		cin>>a[i];
  132. 	for(int i=1;i<=n-1;i++)
  133. 	{
  134. 		int u, v;
  135. 		cin>>u>>v;
  136. 		g[u].push_back(v);
  137. 		g[v].push_back(u);
  138. 	}
  139. 	cin>>q;
  140. 	root[0] = build(1, num);
  141. 	dfs0(1, 0, 1);
  142. 	precompute();
  143. 	dfs(1, 0);
  144. 	while(q--)
  145. 	{
  146. 		int u, v, k;
  147. 		cin>>u>>v>>k;
  148. 		int lca = LCA(u, v);
  149. 		int parlca = parent[0][lca];
  150. 		int ans = query(root[u], root[v], root[lca], root[parlca], 1, num, k);
  151. 		cout<<ans<<endl;
  152. 	}
  153. 	return 0;
  154. }