SUBCENTR - Editorial

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Daanish Mahajan
Tester: Manan Grover
Editorialist: Aman Dwivedi

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Tree, Graph Theory, LCA

PROBLEM:

You are given a tree with N nodes (numbered 1 through N) and Q queries (numbered 1 through Q). For each valid i, in the i-th query, you are given K_i nodes x_1, x_2, \ldots, x_{K_i}. Consider the smallest subtree which contains all of these nodes; you should find all centers of this subtree.

A node is called a center of a tree if it lies in the middle of at least one longest path in that tree. Note that there may be multiple longest paths (paths with the same maximum length) and for a longest path which contains an even number of nodes, there are two nodes lying in the middle of this path.

Note: A subtree here refers to a connected subgraph of the tree. Selecting a node does not mean all its descendants have to be selected.

EXPLANATION:

As we are concerned about the minimal subtree, it means that all the leaves of this subtree are the nodes that are in the given query. Since selecting descendants of those query nodes is not optimal as it increases the size of the subtree.

The diameter of any tree is the longest path of the tree. Since diameter always exists between two leaves in the tree and all the leaves of our minimal subtree are query nodes. Hence we just need to find the pair of nodes from the query nodes that has the maximum distance between among all such pairs.

What happens when there is more than one such pair?

There can be multiple pairs of nodes whose distance is equal to the longest path of the minimal subtree. However, the center of all such pairs remains the same.

  • Let’s say there are two pairs (a,b) and (c,d), such that both pairs have a distance equal to the longest path of the tree.

    • It is quite clear that the lca(a,b) = lca(c,d). If it is not so then both of these pairs cannot be equal to the longest path of the tree. As we can take one node from pair (a,b), say b (depth[a]<depth[b]) and similarly one node from pair (c,d), say d (depth[c]<depth[d]). Then the pair (b,d) will have the distance which is longer than both of the pairs.

    • If both pairs of a node have the same lca, then the center of all such pairs which has the longest path will be the same. To find the longest path we select two such leaves which are farthest from the lca, say x and y. If x=y, then the center will be the lca, else the center lies on the path from lca to x.

Now, we can easily found the end nodes of the diameter, and finally, we can find the center of the longest path.

One of the end nodes is the query node which is at the maximum depth of the tree. And to find the other end node of the diameter we can find the distance of the first node with every other node and the node which has maximum distance is our another end node. The distance between two nodes can be found by using the lca technique. To find lca we can use the binary lifting technique.

TIME COMPLEXITY:

O(N*log(N) + sumK*log(N) + Q*log(N))

SOLUTIONS:

Setter
#include<bits/stdc++.h>
# define pb push_back 
#define pii pair<int, int>
#define mp make_pair
# define ll long long int
 
using namespace std;
 
const int maxtk = 1e6, maxtn = 5e5, maxn = 1e5;
const string newln = "\n", space = " ";
vector<int> g[maxn + 10], nodes; 
bool visit[maxn + 10], visitk[maxn + 10];
int depth[maxn + 10], parent[maxn + 10][20];
int n, q;
bool isGraph(int u, int pa){
    parent[u][0] = pa;
    if(visit[u])return false;
    visit[u] = true;
    for(int v : g[u]){
        if(v == pa)continue;
        depth[v] = depth[u] + 1;
        if(!isGraph(v, u))return false;
    }
    return true;
}
 
int lca(int u, int v){
    if(u == v)return u;
    if(depth[u] < depth[v])swap(u, v);
    for(int i = 19; i >= 0; i--){
        if(depth[u] - (1 << i) >= depth[v]){
            u = parent[u][i];
        }
    }
    if(u == v)return u;
    for(int i = 19; i >= 0; i--){
        if(parent[u][i] != parent[v][i]){
            u = parent[u][i]; v = parent[v][i];
        }
    }
    return parent[u][0];
}
int main()
{   
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
    int tn = 0, tk = 0;
    while(t--){
        cin >> n >> q; tn += n;
        for(int i = 0; i <= n; i++){
            g[i].clear();
            visit[i] = false;
        }
        int u, v;
        for(int i = 1; i < n; i++){
            cin >> u >> v;
            assert(u != v); assert(u != 0); assert(v != 0);
            g[u].pb(v); g[v].pb(u);
        }
        depth[1] = 0;
        assert(isGraph(1, 0));
        for(int i = 1; i <= n; i++)assert(visit[i]);
 
        for(int i = 1; i < 20; i++){
            for(int j = 1; j <= n; j++){
                parent[j][i] = parent[parent[j][i - 1]][i - 1];
            }
        }
 
        while(q--){
            int k; cin >> k; tk += k;
            nodes.clear();
            int maxd = -1, n1 = -1;
            int x;
            for(int i = 1; i <= k; i++){
                cin >> x;
                nodes.pb(x);
                assert(!visitk[x]);
                visitk[x] = true;
                if(depth[x] > maxd){
                    maxd = depth[x]; n1 = x;
                }
            }
            int dia = -1;
            for(int i = 0; i < k; i++){
                int node = nodes[i];
                int pdia = depth[n1] + depth[node] - 2 * depth[lca(n1, node)];
                if(pdia > dia){
                    dia = pdia; 
                }
                visitk[node] = false;
            }
            int jump = dia / 2;
            for(int i = 19; i >= 0; i--){
                if(jump >= (1 << i)){
                    n1 = parent[n1][i];
                    jump -= (1 << i);
                }
            }
            if(dia & 1){
                cout << 2 << " " << min(n1, parent[n1][0]) << " " << max(n1, parent[n1][0]) << endl;            
            }else{
                cout << 1 << " " << n1 << endl;            
            }
        }
    }
} 
Tester
#include <bits/stdc++.h>
using namespace std;
class binl{
public:
  vector<int> lvl;
  vector<vector<int>> anc;
  void dfs(int x, int pr, vector<int> tr[]){
    if(pr == -1){
      lvl[x] = 0;
    }else{
      lvl[x] = lvl[pr] + 1;
      anc[x].push_back(pr);
      int curr = 0;
      while(curr < anc[anc[x].back()].size()){
        anc[x].push_back(anc[anc[x].back()][curr]);
        curr++;
      }
    }
    for(int i = 0; i < tr[x].size(); i++){
      if(tr[x][i] != pr){
        dfs(tr[x][i],x,tr);
      }
    }
  }
  binl(int n, vector<int> tr[], int x){
    anc.resize(n);
    lvl.resize(n);
    dfs(x, -1, tr);
  }
  int lca(int u, int v){
    if(lvl[u] < lvl[v]){
      swap(u, v);
    }
    int cnt = 0;
    int m = lvl[u] - lvl[v];
    while(m){
      if(m % 2){
        u = anc[u][cnt];
      }
      cnt++;
      m /= 2;
    }
    if(u == v){
      return u;
    }
    int k = anc[u].size();
    for(int i = k - 1; i > -1; i--){
      if(i < anc[u].size()){
        if(anc[u][i] != anc[v][i]){
          u = anc[u][i];
          v = anc[v][i];
        }
      }
    }
    return anc[u][0];
  }
  int dis(int u, int v){
    return lvl[u] + lvl[v] - 2 * lvl[lca(u, v)];
  }
};
int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  int t;
  cin>>t;
  while(t--){
    int n,q;
    cin>>n>>q;
    vector<int> tr[n + 1];
    for(int i = 0; i < n - 1; i++){
      int u,v;
      cin>>u>>v;
      tr[u].push_back(v);
      tr[v].push_back(u);
    }
    binl x(n + 1, tr, 1);
    while(q--){
      int k;
      cin>>k;
      int a[k];
      for(int i = 0; i < k; i++){
        cin>>a[i];
      }
      int lf;
      int temp = -1;
      for(int i = 0; i < k; i++){
        if(x.lvl[a[i]]>temp){
          temp = x.lvl[a[i]];
          lf = a[i];
        }
      }
      temp = -1;
      for(int i = 0; i < k; i++){
        int dis = x.dis(lf, a[i]);
        if(dis > temp){
          temp = dis;
        }
      }
      int y = temp / 2;
      int cnt = 0;
      while(y){
        if(y%2){
          lf = x.anc[lf][cnt];
        }
        cnt++;
        y /= 2;
      }
      if(temp % 2 == 0){
        cout<<1<<" "<<lf<<"\n";
      }else{
        y = x.anc[lf][0];
        cout<<2<<" "<<min(lf, y)<<" "<<max(lf, y)<<"\n";
      }
    }
  }
  return 0;
}

List item

Editorialsit
#include<bits/stdc++.h>
using namespace std;

const int mxN=1e5+5;
vector <int> tree[mxN];
int depth[mxN];

int timer;
vector<int> tin,tout;
vector<vector<int>> up;
int n,l;

void dfs(int v,int p)
{
  tin[v]=++timer;
  up[v][0]=p;

  for(int i=1;i<=l;i++)
    up[v][i]=up[up[v][i-1]][i-1];

  for(int u: tree[v])
  {
    if(u!=p)
    {
      depth[u]=depth[v]+1;
      dfs(u,v);
    }
  }

  tout[v]=++timer;
}

bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = l; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}

void preprocess(int root)
{
  tin.resize(n);
  tout.resize(n);
  timer=0;
  l=ceil(log2(n));
  up.assign(n,vector<int>(l+1));
  dfs(root,root);
}

void solve()
{
  int q;
  cin>>n>>q;

  for(int i=0;i<n;i++)
  {
    tree[i].clear();
    depth[i]=0;
  }

  for(int i=0;i<n-1;i++)
  {
    int x,y;
    cin>>x>>y;
    x--;
    y--;

    tree[x].push_back(y);
    tree[y].push_back(x);
  }

  preprocess(0);

  while(q--)
  {
    int k;
    cin>>k;

    int a[k];
    int fst_node=-1,dis=-1;

    for(int i=0;i<k;i++)
    {
      cin>>a[i];
      a[i]--;
      if(depth[a[i]]>dis)
      {
        fst_node=a[i];
        dis=depth[a[i]];
      }
    }

    if(k==1)
      cout<<1<<" "<<a[0]+1<<"\n";
    else
    {
      dis=-1;
      int sec_node=-1;

      for(int i=0;i<k;i++)
      {
        int temp=depth[a[i]]+depth[fst_node]-2*depth[lca(a[i],fst_node)];
        // cout<<lca(a[i],fst_node)<<endl;
        if(temp>dis)
        {
          dis=temp;
          sec_node=a[i];
        }
      }


      if(depth[fst_node]>depth[sec_node])
          swap(fst_node,sec_node);

      int hal=dis/2;

      for(int i=l;i>=0;i--)
      {
        if(hal>=(1 << i))
        {
            hal-=(1 << i);
            sec_node=up[sec_node][i];
        }
      }

      if(dis%2==0)
        cout<<1<<" "<<sec_node+1<<"\n";
      else
        cout<<2<<" "<<min(sec_node,up[sec_node][0])+1<<" "<<max(sec_node,up[sec_node][0])+1<<"\n";
    }
  }
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}

4 Likes

What drugs are you guys doing? (I am asking for a friend) No way this is Easy-Medium! Even in Div.1 only 10 people solved it (including myself).

23 Likes

Expected a better sample test case :frowning:

4 Likes

Well said.

Yes

Can someone tell me what are the prerequisites of this problem. I have seen such problem for the first time

2 line of the editorial

Can we solve the same problem for a general graph in polynomial time? I can’t even think of a way to find the radius of the minimal subgraph for each query optimally. Any thoughts?

PS: Kindly prioritize giving non-conventional definitions if any from next time, as the subtree definition was added quite late in the contest and By then, many div-1 contestants already left the contest. Also why unnecessarily create an ambiguity by calling it a subtree at the first place, you could have simply called it a minimal connected subgraph.

1 Like

Here, according to the code provided, for finding the first node, if we get nodes with the same depth then we are not updating the first node. So we need to prove that if there are multiple nodes at the lowest depth then no matter which one of them we choose we will always get the correct answer. I am not able to figure out how to prove this.

@cherry0697

please help me out. i refered to setter’s solution

You’ve shared the link to submit page instead of your submission.
You can check this submission too , I think it is neat enough for you to follow.

2 Likes

Can ypu please help me why my code is giving TLE?

LCA concept: LCA in a tree using Binary Lifting Technique - GeeksforGeeks
And rest concept of Editorialsit’s solutions

Code: CodeChef: Practical coding for everyone

Thanks

Can anybody please help me why my code is giving TLE?

LCA concept: LCA in a tree using Binary Lifting Technique - GeeksforGeeks
And rest concept of Editorialsit’s solutions

Code: CodeChef: Practical coding for everyone

Thanks

i am so sorry, here is the link of my recent submission CodeChef: Practical coding for everyone

can you please tell me what is wrong with this

https://www.codechef.com/viewsolution/47340297