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;
}