Advertisement
Guest User

Untitled

a guest
Dec 19th, 2016
217
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.01 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <string>
  6. #include <vector>
  7. #include <stack>
  8. #include <queue>
  9. #include <set>
  10. #include <cstring>
  11. #include <map>
  12. #include <cstdlib>
  13. #include <ctime>
  14. #include <cassert>
  15. #include <bitset>
  16. #define f first
  17. #define s second
  18. #define ll long long
  19. #define ull unsigned long long
  20. #define mp make_pair
  21. #define pb push_back
  22. #define vi vector <int>
  23. #define ld long double
  24. #define pii pair<int, int>
  25. #define y1 sda
  26. using namespace std;
  27. const int N = int(3e5), mod = int(1e9) + 7;
  28. int n,m;
  29. int x[N],y[N],d[N],up[N][18], tin[N], tout[N];
  30.  
  31. bool used[N];
  32. int ti;
  33. vi g[N];
  34.  
  35. void dfs(int v,int dep = 0){
  36. used[v] = 1;
  37. d[v] = dep;
  38. tin[v] = ++ti;
  39. for(int i = 0; i < g[v].size(); i++){
  40. int to = g[v][i];
  41. if(!used[to]) {
  42. up[to][0] = v;
  43. dfs(to,dep + 1);
  44. }
  45. }
  46. tout[v] = ++ti;
  47. }
  48.  
  49. bool ok(int u,int v){
  50. return (tin[u] <= tin[v] && tout[u] >= tout[v]);
  51. }
  52.  
  53. int lca(int v,int u){
  54. if(ok(v,u)) return v;
  55. if(ok(u,v)) return u;
  56. for(int i = 17; i >= 0; i--){
  57. if(up[v][i] && !ok(up[v][i],u)) v = up[v][i];
  58. }
  59. return up[v][0];
  60. }
  61.  
  62. int dist(int u,int v){
  63. return d[u] + d[v] - 2 * d[lca(v,u)];
  64. }
  65.  
  66.  
  67. int main () {
  68. scanf("%d%d",&n,&m);
  69. for(int i = 1,u,v; i < n; i++){
  70. scanf("%d%d",&u,&v);
  71. g[u].pb(v);
  72. g[v].pb(u);
  73. }
  74. dfs(1);
  75. for(int j = 1; j <= 17; j++){
  76. for(int i = 1; i <= n; i++) if(up[i][j - 1]){
  77. up[i][j] = up[up[i][j - 1]][j - 1];
  78. }
  79. }
  80.  
  81. for(int i = 1; i <= m; i++){
  82. scanf("%d%d",&x[i],&y[i]);
  83. }
  84. int ans = 0;
  85. int p = 0, _max = 0;
  86. for(int i = 1; i <= m; i++){
  87. if(d[x[i]] + d[y[i]] > _max){
  88. _max = d[x[i]] + d[y[i]];
  89. p = i;
  90. }
  91. }
  92. for(int i = 1; i <= m; i++){
  93. ans = max(ans, dist(x[p],x[i]) + dist(y[p],y[i]));
  94. }
  95. _max = 0;
  96. for(int i = 1; i <= m; i++){
  97. if(dist(x[i],y[i]) > _max){
  98. _max = dist(x[i],y[i]);
  99. p = i;
  100. }
  101. }
  102. for(int i = 1; i <= m; i++){
  103. ans = max(ans, dist(x[p],x[i]) + dist(y[p],y[i]));
  104. }
  105. cout << ans;
  106.  
  107.  
  108. return 0;
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement