HackerEarth Minimum distance in Tree problem solution

In this HackerEarth Minimum distance in Tree problem solution You are given a tree and q queries. Each query consists of ki vertices: v(i,1), ..., v(i,k).

Let fi(u) be the minimum between distances from u to each v(i,j), for 1 <= j <= kj. For each query you have to find value of max(u belongs to V) fi(u).

HackerEarth Minimum distance problem solution.

`#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <string>#include <vector>#include <algorithm>#include <set>#include <map>#include <cmath>#include <ctime>#include <functional>#include <sstream>#include <fstream>#include <valarray>#include <complex>#include <queue>#include <cassert>#include <bitset>using namespace std;#ifdef LOCAL#define debug_flag 1#else#define debug_flag 0#endif  template <class T1, class T2 >std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p) {  os << "[" << p.first << ", " << p.second << "]";  return os;}  template <class T >std::ostream& operator << (std::ostream& os, const std::vector<T>& v) {  os << "[";  bool first = true;  for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it)  {    if (!first)      os << ", ";    first = false;    os << *it;  }  os << "]";  return os;}  template <class T >std::ostream& operator << (std::ostream& os, const std::set<T>& v) {  os << "[";  bool first = true;  for (typename std::set<T>::const_iterator it = v.begin(); it != v.end(); ++it)  {    if (!first)      os << ", ";    first = false;    os << *it;  }  os << "]";  return os;}  template <class T >std::ostream& operator << (std::ostream& os, const std::multiset<T>& v) {  os << "[";  bool first = true;  for (typename std::multiset<T>::const_iterator it = v.begin(); it != v.end(); ++it)  {    if (!first)      os << ", ";    first = false;    os << *it;  }  os << "]";  return os;}#define dbg(args...) { if (debug_flag) { _print(_split(#args, ',').begin(), args); cerr << endl; } else { void(0);} }vector<string> _split(const string& s, char c) {  vector<string> v;  stringstream ss(s);  string x;  while (getline(ss, x, c))    v.emplace_back(x);  return v;}void _print(vector<string>::iterator) {}template<typename T, typename... Args>void _print(vector<string>::iterator it, T a, Args... args) {  string name = it -> substr((*it)[0] == ' ', it -> length());  if (isalpha(name[0]))    cerr << name  << " = " << a << " ";  else    cerr << name << " ";  _print(++it, args...);}typedef long long int int64;const int N = (int)3e5;const int LOGN = 20;const int INF = (int)1e9;int n;vector<int> graph[N];int par[N][LOGN];int timer;int t_in[N], t_out[N];int h[N];int depth[N];multiset<int> depth_set[N];int dist_to_nearest[N];int up_dp[N][LOGN];int down_dp[N][LOGN];void init_par(int v, int p){  if (p != -1)    graph[v].erase(find(graph[v].begin(), graph[v].end(), p));  par[v][0] = p;  for (int i = 1; i < LOGN; i++)  {    if (par[v][i - 1] == -1)      break;    par[v][i] = par[par[v][i - 1]][i - 1];  }  for (int to : graph[v])  {    assert(to != p);    init_par(to, v);  }}void init_tree0(int v, int cur_h){  t_in[v] = timer++;  h[v] = cur_h;  for (int to : graph[v])    init_tree0(to, cur_h + 1);  t_out[v] = timer++;}bool is_par(int a, int b){  return t_in[a] <= t_in[b] && t_out[b] <= t_out[a];}int get_lca(int a, int b){  if (is_par(a, b))    return a;  if (is_par(b, a))    return b;  for (int i = LOGN - 1; i >= 0; i--)  {    int new_a = par[a][i];    if (new_a != -1 && !is_par(new_a, b))      a = new_a;  }  return par[a][0];}int get_dist(int a, int b){  int l = get_lca(a, b);  return h[a] + h[b] - 2 * h[l];}void init_depth(int v){  depth[v] = 0;  for (int to : graph[v])  {    init_depth(to);    depth_set[v].insert(depth[to] + 1);    depth[v] = max(depth[v], depth[to] + 1);  }}void init_up_dp(int v){  int p = par[v][0];  if (p != -1)  {    depth_set[p].erase(find(depth_set[p].begin(), depth_set[p].end(), depth[v] + 1));    if (depth_set[p].empty())      up_dp[v][0] = 0;    else      up_dp[v][0] = *depth_set[p].rbegin();    depth_set[p].insert(depth[v] + 1);  }  for (int i = 1; i < LOGN; i++)  {    if (par[v][i] == -1)      break;    int pp = par[v][i - 1];    int val1 = up_dp[v][i - 1] + (1 << (i - 1));    int val2 = up_dp[pp][i - 1];    up_dp[v][i] = max(val1, val2);  }  for (int to : graph[v])    init_up_dp(to);}void init_down_dp(int v){  int p = par[v][0];  if (p != -1)  {    depth_set[p].erase(find(depth_set[p].begin(), depth_set[p].end(), depth[v] + 1));    if (depth_set[p].empty())      down_dp[v][0] = 1;    else      down_dp[v][0] = *depth_set[p].rbegin() + 1;    depth_set[p].insert(depth[v] + 1);  }  for (int i = 1; i < LOGN; i++)  {    if (par[v][i] == -1)      break;    int pp = par[v][i - 1];    int val1 = down_dp[v][i - 1];    int val2 = down_dp[pp][i - 1] + (1 << (i - 1));    down_dp[v][i] = max(val1, val2);  }  for (int to : graph[v])    init_down_dp(to);}void init_tree(){  //init par[][] and erase edge to parent  for (int i = 0; i < N; i++)    for (int j = 0; j < LOGN; j++)      par[i][j] = -1;  init_par(0, -1);  //init h t_in t_out  init_tree0(0, 0);  //init depth and depth_set  init_depth(0);  //init up_dp and down_up  init_up_dp(0);  init_down_dp(0);}int get_down_max(int a, int b){  int old_a = a;  int ans = 0;  for (int i = LOGN - 1; i >= 0; i--)  {    int new_a = par[a][i];    if (new_a == -1 || !is_par(b, new_a))      continue;    ans = max(ans, down_dp[a][i] + get_dist(a, old_a));    a = new_a;  }  return ans;}int get_up_max(int a, int b){  //dbg(a, b);  int ans = 0;  for (int i = LOGN - 1; i >= 0; i--)  {    int new_a = par[a][i];    if (new_a == -1 || !is_par(b, new_a))      continue;    ans = max(ans, up_dp[a][i] + get_dist(new_a, b));    a = new_a;  }  return ans;}int go_up(int v, int delta){  assert(delta >= 0);  assert(delta <= h[v]);  for (int i = LOGN - 1; i >= 0; i--)  {    if (delta >= (1 << i))    {      v = par[v][i];      delta -= (1 << i);    }  }  return v;}int IT;void solve(){  int k;  scanf("%d", &k);  set<int> v_set;  vector<int> v_list(k);  for (int i = 0; i < k; i++)  {    int v;    scanf("%d", &v);    v--;    v_list[i] = v;    v_set.insert(v);  }  while (true)  {    set<int> new_v_set;    for (int v1 : v_set)      for (int v2 : v_set)        new_v_set.insert(get_lca(v1, v2));    if (new_v_set == v_set)      break;    v_set = new_v_set;  }  //dbg(k, v_list, v_set);  for (int v : v_set)  {    dist_to_nearest[v] = INF;    for (int u : v_list)      dist_to_nearest[v] = min(dist_to_nearest[v], get_dist(v, u));    //dbg(v, dist_to_nearest[v]);  }  vector<pair<int, int> > ab_pairs;  for (int a : v_set)  {    for (int b : v_set)    {      if (a == b || !is_par(b, a))        continue;      bool has_node_on_path = false;      for (int v : v_set)        if (v != a && v != b && is_par(b, v) && is_par(v, a))          has_node_on_path = true;      if (has_node_on_path)        continue;      ab_pairs.emplace_back(a, b);    }  }  //dbg(ab_pairs.size());  int ans = 0;  //go_up single  for (int v : v_set)  {    bool is_root = true;    for (int u : v_set)      if (u != v && is_par(u, v))        is_root = false;    if (!is_root)      continue;    ans = max(ans, get_down_max(v, 0) + dist_to_nearest[v]);    ans = max(ans, dist_to_nearest[v] + h[v]);  }  //go_down single  for (auto ab_p : ab_pairs)  {    int a = ab_p.first;    int b = ab_p.second;    int c = go_up(a, h[a] - h[b] - 1);    depth_set[b].erase(depth_set[b].find(depth[c] + 1));  }  for (int v : v_set)  {    if (!depth_set[v].empty())      ans = max(ans, *depth_set[v].rbegin() + dist_to_nearest[v]);    else      ans = max(ans, dist_to_nearest[v]);  }  for (auto ab_p : ab_pairs)  {    int a = ab_p.first;    int b = ab_p.second;    int c = go_up(a, h[a] - h[b] - 1);    depth_set[b].insert(depth[c] + 1);  }  //go path  for (auto ab_p : ab_pairs)  {    int a = ab_p.first;    int b = ab_p.second;    int c = a;    for (int i = LOGN - 1; i >= 0; i--)    {      int new_c = par[c][i];      if (new_c == -1 || is_par(new_c, b))        continue;      //O(1)      int dist1 = dist_to_nearest[a] + get_dist(a, new_c);      int dist2 = dist_to_nearest[b] + get_dist(b, new_c);      if (dist1 <= dist2)        c = new_c;    }    //[a, c] and (c, b]    int val1 = get_down_max(a, c) + dist_to_nearest[a];    int val2 = 0;    int b2 = go_up(c, h[c] - h[b] - 1);    if (c != b2)      val2 = get_up_max(c, b2) + 1 + dist_to_nearest[b];    //dbg(a, b, b2, c, val1, val2);    ans = max(ans, val1);    ans = max(ans, val2);  }  printf("%d\n", ans);}int main(){#ifdef LOCAL  freopen ("input.txt", "r", stdin);#endif  int q;  scanf("%d%d", &n, &q);  for (int i = 0; i < n - 1; i++)  {    int a, b;    scanf("%d%d", &a, &b);    a--;    b--;    //dbg(a, b);    graph[a].push_back(b);    graph[b].push_back(a);  }  init_tree();  for (int it = 0; it < q; it++)  {    solve();  }  return 0;}`