Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <string>
- #include <vector>
- #include <stack>
- #include <queue>
- #include <set>
- #include <cstring>
- #include <map>
- #include <cstdlib>
- #include <ctime>
- #include <cassert>
- #include <bitset>
- #define f first
- #define s second
- #define ll long long
- #define ull unsigned long long
- #define mp make_pair
- #define pb push_back
- #define vi vector <int>
- #define ld long double
- #define pii pair<int, int>
- #define y1 sda
- using namespace std;
- const int N = int(3e5), mod = int(1e9) + 7;
- int n,m;
- int x[N],y[N],d[N],up[N][18], tin[N], tout[N];
- bool used[N];
- int ti;
- vi g[N];
- void dfs(int v,int dep = 0){
- used[v] = 1;
- d[v] = dep;
- tin[v] = ++ti;
- for(int i = 0; i < g[v].size(); i++){
- int to = g[v][i];
- if(!used[to]) {
- up[to][0] = v;
- dfs(to,dep + 1);
- }
- }
- tout[v] = ++ti;
- }
- bool ok(int u,int v){
- return (tin[u] <= tin[v] && tout[u] >= tout[v]);
- }
- int lca(int v,int u){
- if(ok(v,u)) return v;
- if(ok(u,v)) return u;
- for(int i = 17; i >= 0; i--){
- if(up[v][i] && !ok(up[v][i],u)) v = up[v][i];
- }
- return up[v][0];
- }
- int dist(int u,int v){
- return d[u] + d[v] - 2 * d[lca(v,u)];
- }
- int main () {
- scanf("%d%d",&n,&m);
- for(int i = 1,u,v; i < n; i++){
- scanf("%d%d",&u,&v);
- g[u].pb(v);
- g[v].pb(u);
- }
- dfs(1);
- for(int j = 1; j <= 17; j++){
- for(int i = 1; i <= n; i++) if(up[i][j - 1]){
- up[i][j] = up[up[i][j - 1]][j - 1];
- }
- }
- for(int i = 1; i <= m; i++){
- scanf("%d%d",&x[i],&y[i]);
- }
- int ans = 0;
- int p = 0, _max = 0;
- for(int i = 1; i <= m; i++){
- if(d[x[i]] + d[y[i]] > _max){
- _max = d[x[i]] + d[y[i]];
- p = i;
- }
- }
- for(int i = 1; i <= m; i++){
- ans = max(ans, dist(x[p],x[i]) + dist(y[p],y[i]));
- }
- _max = 0;
- for(int i = 1; i <= m; i++){
- if(dist(x[i],y[i]) > _max){
- _max = dist(x[i],y[i]);
- p = i;
- }
- }
- for(int i = 1; i <= m; i++){
- ans = max(ans, dist(x[p],x[i]) + dist(y[p],y[i]));
- }
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement