fork download
copy 
  1. #if 1
  2. #include <cstdlib>
  3. #include <cstdio>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <functional>
  7. #include <cstring>
  8. #include <string>
  9. #include <vector>
  10. #include <list>
  11. #include <set>
  12. #include <map>
  13. #include <stack>
  14. #include <queue>
  15. #include <ctime>
  16. #include <cassert>
  17. #include <sstream>
  18. #include <iostream>
  19. #include <bitset>
  20.  
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef long double LD;
  25. typedef pair<int , int> pii;
  26. typedef vector <int> veci;
  27. typedef vector <veci> graph;
  28. const LD eps = 1e-9;
  29. const LD pi = acos(-1.0);
  30. const int inf = 1000 * 1000 * 1000;
  31. const LL inf64 = LL(inf) * inf;
  32.  
  33. #define mp make_pair
  34. #define pb push_back
  35. #define X first
  36. #define Y second
  37. #define iss istringstream
  38. #define oss ostringstream
  39. #define dbg(x) {cerr << #x << " = " << x << endl;}
  40. #define dbgv(x) {cerr << #x << " ={"; for (int _i = 0; _i < x.size(); _i++) {if (_i) cerr << ", "; cerr << x[_i];} cerr << "}" << endl;}
  41. #define NAME "problem"
  42.  
  43. struct LCAQueries
  44. {
  45. 	static const int maxn = 100011;
  46. 	static const int maxlgn = 20;
  47. 	int up[maxn][maxlgn], tin[maxn], tout[maxn], timer;
  48. 	int lgn;
  49.  
  50. 	void dfs(const graph &g, int u, int pred) {
  51. 		tin[u] = timer++;
  52. 		for(int i = 0; i < lgn; ++i)
  53. 			up[u][i] = i ? up[up[u][i - 1]][i - 1] : pred;
  54. 		for(int i = 0; i < g[u].size(); ++i)
  55. 			if(g[u][i] != pred)
  56. 				dfs(g, g[u][i], u);
  57. 		tout[u] = timer++;
  58. 	}
  59.  
  60. 	void build(const graph &g, int s = 0) {
  61. 		lgn = 0; while((1 << lgn) <= g.size()) ++lgn;
  62. 		timer = 0; dfs(g, s, s);
  63. 	}
  64.  
  65. 	bool anc(int u, int v)
  66. 	{ return tin[u] <= tin[v] && tout[v] <= tout[u]; }
  67.  
  68. 	int get(int u, int v) {
  69. 		if(anc(u, v)) return u;
  70. 		if(anc(v, u)) return v;
  71. 		for(int i = lgn - 1; i >= 0; --i)
  72. 			if(!anc(up[u][i], v))
  73. 				u = up[u][i];
  74. 		return up[u][0];
  75. 	}
  76.  
  77. 	int get_k_up(int u, int k)
  78. 	{
  79. 		for(int i = lgn - 1; i >= 0; --i)
  80. 			if(k & (1 <<i))
  81. 				u = up[u][i];
  82. 		return u;
  83. 	}
  84. };
  85.  
  86. struct fenwick_t
  87. {
  88. 	vector<int> f;
  89. 	void init(int n)
  90. 	{
  91. 		f.assign(n, 0);
  92. 	}
  93.  
  94. 	void add(int idx, int val)
  95. 	{
  96. 		for (int i = idx; i < f.size(); i |= i + 1)
  97. 			f[i] += val;
  98. 	}
  99.  
  100. 	int sum(int right)
  101. 	{
  102. 		int res = 0;
  103. 		for (int i = right; i >= 0; i &= i + 1, --i)
  104. 			res += f[i];
  105. 		return res;
  106. 	}
  107. 	int sum(int left, int right)
  108. 	{
  109. 		return sum(right) - sum(left - 1);
  110. 	}
  111. };
  112.  
  113. LCAQueries qlca;
  114. vector< pair<int, int> > pathes;
  115. fenwick_t fenwick;
  116. vector< vector<int> > by_lca;
  117. LL intersected;
  118. graph g;
  119. void add_path(int id, int val)
  120. {
  121. 	int u = pathes[id].first;
  122. 	int v = pathes[id].second;
  123. 	fenwick.add(qlca.tin[u], val);
  124. 	fenwick.add(qlca.tin[v], val);	
  125. }
  126.  
  127. void dfs(int u, int pred = -1)
  128. {
  129. 	LL cnt = by_lca[u].size();
  130. 	intersected += cnt * (cnt - 1) / 2;
  131. 	intersected += cnt * fenwick.sum(qlca.tin[u], qlca.tout[u]);
  132.  
  133. 	for (size_t i = 0; i < by_lca[u].size(); ++i)
  134. 		add_path(by_lca[u][i], +1);
  135.  
  136. 	for (size_t i = 0; i < g[u].size(); ++i)
  137. 	{
  138. 		int v = g[u][i];
  139. 		if (v == pred)
  140. 			continue;
  141. 		dfs(v, u);
  142. 	}
  143.  
  144. 	for (size_t i = 0; i < by_lca[u].size(); ++i)
  145. 		add_path(by_lca[u][i], -1);
  146. }
  147.  
  148. int main()
  149. {
  150. 	//freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout);
  151. 	//freopen(NAME ".in","r",stdin);freopen(NAME ".out","w",stdout);
  152.  
  153. 	int n;
  154. 	scanf("%d", &n);
  155. 	g.resize(n);
  156. 	for (int i = 1; i < n; ++i)
  157. 	{
  158. 		int u, v;
  159. 		scanf("%d%d", &u, &v);
  160. 		--u; --v;
  161. 		g[u].push_back(v);
  162. 		g[v].push_back(u);
  163. 	}
  164.  
  165. 	qlca.build(g);
  166. 	by_lca.resize(n);
  167. 	int k;
  168. 	scanf("%d", &k);
  169. 	for (int i = 0; i < k; ++i)
  170. 	{
  171. 		int u, v;
  172. 		scanf("%d%d", &u, &v);
  173. 		--u; --v;
  174. 		pathes.push_back(make_pair(u, v));
  175. 		int w = qlca.get(u, v);
  176. 		by_lca[w].push_back(i);
  177. 	}
  178.  
  179. 	fenwick.init(qlca.timer);
  180. 	intersected = 0;
  181. 	dfs(0);
  182.  
  183. 	LL res = LL(k) * LL(k - 1) / 2LL;
  184. 	res -= intersected;
  185. 	cout << res << endl;
  186. 	return 0;
  187. }
  188. /*************************
  189. *************************/
  190. #endif
  191.  
Runtime error #stdin #stdout 0s 4364KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oQFacf
language:
C++14 (gcc 8.3)
created:
6 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!