fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long lld;
  4. const int MN = 1e5 + 10;
  5. const int M = 18;
  6. int n, m;
  7. vector<int> adj[MN];
  8. vector<int> child[MN];
  9. vector<int> st[MN];
  10. int s[MN], t[MN], dep[MN], sz[MN], p[M][MN];
  11. lld alldep[MN], subdep[MN];
  12. int curTime;
  13.  
  14. void dfs1(int cur, int par)
  15. {
  16. 	p[0][cur] = par;
  17. 	for(auto nxt : adj[cur]){
  18. 		if(nxt == par) continue;
  19. 		child[cur].emplace_back(nxt);
  20. 		dfs1(nxt, cur);
  21. 	}
  22. }
  23.  
  24. void dfs2(int cur, int depth)
  25. {
  26. 	s[cur] = ++curTime;
  27. 	dep[cur] = depth;
  28. 	alldep[cur] = depth;
  29. 	sz[cur] = 1;
  30. 	for(auto nxt : child[cur]){
  31. 		dfs2(nxt, depth + 1);
  32. 		st[cur].emplace_back(t[nxt]);
  33. 		sz[cur] += sz[nxt];
  34. 		alldep[cur] += alldep[nxt];
  35. 	}
  36. 	t[cur] = ++curTime;
  37. }
  38.  
  39. void dfs3(int cur)
  40. {
  41. 	for(auto nxt : child[cur]){
  42. 		alldep[nxt] = alldep[cur] + n - 2 * sz[nxt];
  43. 		dfs3(nxt);
  44. 		subdep[cur] += subdep[nxt] + sz[nxt];
  45. 	}
  46. }
  47.  
  48. bool isSubtree(int u, int v)
  49. {
  50. 	return s[v] < s[u] && t[u] < t[v]; 
  51. }
  52.  
  53.  
  54. int LCA(int u, int v)
  55. {
  56.  
  57. 	if(dep[u] < dep[v]) swap(u, v);
  58. 	int d = dep[u] - dep[v];
  59. 	for(int i = 0; i < M; ++i){
  60. 		if(d & 1 << i) u = p[i][u];
  61. 	}
  62.  
  63. 	if(u == v) return u;
  64.  
  65. 	for(int i = M - 1; i >= 0; --i){
  66. 		if(p[i][u] != p[i][v]){
  67. 			u = p[i][u];
  68. 			v = p[i][v];
  69. 		}
  70. 	}
  71. 	return p[0][u];
  72. }
  73.  
  74. int main()
  75. {
  76. 	ios_base::sync_with_stdio(false);
  77. 	cin.tie(0);
  78. 	cin >> n >> m;
  79. 	for(int i = 0; i < n - 1; ++i){
  80. 		int u, v;
  81. 		cin >> u >> v;
  82. 		adj[u].emplace_back(v);
  83. 		adj[v].emplace_back(u);
  84. 	}
  85. 	dfs1(1, 0);
  86. 	dfs2(1, 0);
  87. 	dfs3(1);
  88.  
  89. 	for(int i = 0; i < M - 1; ++i){
  90. 		for(int j = 1; j <= n; ++j){
  91. 			p[i + 1][j] = p[i][p[i][j]];
  92. 		}
  93. 	}
  94.  
  95. 	cout << fixed;
  96. 	cout << setprecision(10);
  97.  
  98. 	for(int i = 0; i < m; ++i){
  99. 		int u, v;
  100. 		cin >> u >> v;
  101. 		int lca = LCA(u, v);
  102. 		int dist = dep[u] + dep[v] - 2 * dep[lca];
  103. 		int usz = sz[u];
  104. 		int vsz = sz[v];
  105. 		lld udep = subdep[u];
  106. 		lld vdep = subdep[v];
  107. 		if(isSubtree(u, v)){
  108. 			int idx = lower_bound(st[v].begin(), st[v].end(), s[u]) - st[v].begin();
  109. 			vsz = n - sz[child[v][idx]];
  110. 			vdep = alldep[v] - (subdep[child[v][idx]] + sz[child[v][idx]]);
  111. 		}
  112. 		if(isSubtree(v, u)){
  113. 			int idx = lower_bound(st[u].begin(), st[u].end(), s[v]) - st[u].begin();
  114. 			usz = n - sz[child[u][idx]];
  115. 			udep = alldep[u] - (subdep[child[u][idx]] + sz[child[u][idx]]);
  116. 		}
  117. 		double ans = (double)vdep / vsz + (double)udep / usz + dist + 1.0;
  118. 		cout << ans << '\n';
  119. 	}
  120. }
  121.  
Success #stdin #stdout 0s 17128KB
comments (?)
stdin
copy 
4 3
2 4
4 1
3 2
3 1
2 3
4 1
stdout
copy 
4.0000000000
3.0000000000
3.0000000000
https://ideone.com/WfPGWp
codeforces round 343 div2 E
language:
C++14 (gcc 8.3)
created:
8 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!