fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define fi first
  4. #define se second
  5.  
  6. #define For(i, a, b) for (int i = (a); i <= (b); ++i)
  7. #define ForD(i, a, b) for (int i = (a); i >= (b); --i)
  8. #define rep(i, n) for (int i = 0; i < (n); ++i)
  9. #define repD(i, n) for (int i = (n) - 1; i >= 0; --i)
  10. #define coutE(x) {cout << x << '\n'; return;}
  11. #define pb push_back
  12. #define pf push_front
  13.  
  14. #define all(x) x.begin(), x.end()
  15. #define bs binary_search
  16. #define ub upper_bound
  17. #define lb lower_bound
  18.  
  19. #define endl '\n'
  20.  
  21. #define db long double
  22. #define ll long long
  23. #define ii pair<int, int>
  24. #define vi vector<int>
  25. #define vii vector<ii>
  26.  
  27. #define int long long
  28.  
  29.  
  30. using namespace std;
  31.  
  32. const int N = 2e5 + 5;
  33.  
  34. const int INF = 1e9;
  35. const long long LINF = 1e18;
  36.  
  37. void add(ii &a, ii b){
  38. 	a.fi += b.fi;
  39. 	a.se += b.se;
  40. }
  41.  
  42. int n, m, q;
  43. int a[N], b[N], x[N], y[N];
  44. vi g[N];
  45. ii ed[N], sec[N];
  46. int up[N][20], h[N];
  47. int in[N], out[N], timer;
  48. int l[N], r[N], ans[N];
  49. vi quer[N];
  50.  
  51. struct BIT{
  52.  
  53. 	int sum[N], cnt[N];
  54.  
  55. 	void reset(){
  56. 		For(i, 1, 2*n) sum[i] = cnt[i] = 0;
  57. 	}
  58.  
  59. 	void Update(int i, int v1, int v2){
  60. 		for (; i <= 2*n; i += i & -i) sum[i] += v1, cnt[i] += v2;
  61. 	}
  62.  
  63. 	void update(int l, int r, int v){
  64. 		Update(l, v, 1);
  65. 		Update(r, -v, -1);
  66. 	}
  67.  
  68. 	ii get(int i){
  69. 		ii res = {0, 0};
  70. 		for (; i; i -= i & -i) add(res, {sum[i], cnt[i]});
  71. 		return res;
  72. 	}
  73.  
  74. } BIT;
  75.  
  76. void dfs(int u){
  77.  
  78. 	in[u] = ++timer;
  79. 	for (int v: g[u]) if (v != up[u][0]){
  80. 		h[v] = h[u] + 1;
  81. 		up[v][0] = u;
  82. 		For(j, 1, 17)
  83. 			up[v][j] = up[up[v][j - 1]][j - 1];
  84.  
  85. 		dfs(v);
  86. 	}
  87. 	out[u] = ++timer;
  88. }
  89.  
  90. int lca(int u, int v)
  91. {
  92.     if (h[u] < h[v]) swap(u,v);
  93.     int z = (int)(log2(h[u]));
  94.     for (int i = z; i>=0; i--)
  95.     {
  96.         if (h[u] - h[v] >= (1<<i)) u = up[u][i];
  97.     }
  98.     if (u == v) return u;
  99.     for (int i = z; i>=0; i--)
  100.     {
  101.         if (up[u][i]  != up[v][i])
  102.         {
  103.             u = up[u][i];
  104.             v = up[v][i];
  105.         }
  106.     }
  107.     return up[u][0];
  108. }
  109.  
  110. ii get(int u, int v){
  111.  
  112. 	ii a = BIT.get(in[u]), b = BIT.get(in[v]), c = BIT.get(in[lca(u, v)]);
  113. 	return {a.fi + b.fi - 2 * c.fi, a.se + b.se - 2 * c.se};
  114. }
  115.  
  116. void solve(){
  117.  
  118. 	cin >> n >> m >> q;
  119. 	For(i, 1, n - 1){
  120. 		int u, v; cin >> u >> v;
  121. 		g[u].pb(v); g[v].pb(u);
  122. 		ed[i] = {u, v};
  123. 	}
  124.  
  125. 	dfs(1);
  126. 	For(i, 1, n - 1){
  127. 		if (h[ed[i].fi] > h[ed[i].se]){
  128. 			swap(ed[i].fi, ed[i].se);
  129. 		}
  130. 	}
  131.  
  132. 	For(i, 1, m) cin >> sec[i].se >> sec[i].fi;
  133. 	sort(sec + 1, sec + m + 1);
  134. 	For(i, 1, m) sec[i].se = ed[sec[i].se].se;
  135.  
  136. 	For(i, 1, q){
  137. 		cin >> a[i] >> b[i] >> x[i] >> y[i];
  138. 		l[i] = 0; r[i] = m;
  139. 		ans[i] = LINF;
  140. 	}
  141.  
  142. 	int ok = 1;
  143. 	while (ok){
  144. 		ok = 0;
  145.  
  146. 		BIT.reset();
  147. 		For(i, 0, m) quer[i].clear();
  148. 		For(i, 1, q){
  149. 			if (l[i] > r[i]) continue;
  150.  
  151. 			ok = 1;
  152. 			quer[(l[i] + r[i])/2].pb(i);
  153. 		}
  154.  
  155. 		For(t, 0, m){
  156. 			if (t){
  157. 				auto [c, u] = sec[t];
  158. 				BIT.update(in[u], out[u], c);
  159. 			}
  160.  
  161. 			for (int i: quer[t]){
  162. 				auto [s, c] = get(a[i], b[i]);
  163. 				int u = a[i], v = b[i];
  164. 				if (s <= y[i]) l[i] = t + 1, ans[i] = c;
  165. 				else r[i] = t - 1;
  166. 			}
  167. 		}
  168. 	}
  169.  
  170. 	For(i, 1, q){
  171. 		auto [s, c] = get(a[i], b[i]);
  172. 		cout << max(x[i] - c + ans[i], -1ll) << endl;
  173. 	}
  174. }
  175.  
  176.  
  177. signed main(){
  178.  
  179. 	ios_base::sync_with_stdio(0);
  180. 	cin.tie(0); cout.tie(0);
  181.  
  182. 	solve();
  183.  
  184. 	return 0;
  185. }
  186.  
Success #stdin #stdout 0.01s 18028KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/D83oBD
language:
C++14 (gcc 8.3)
created:
77 days 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!