ECAUG207 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author: Sandeep Singh
Tester: Arnab Chanda
Editorialist: Sandeep SIngh

DIFFICULTY:

MEDIUM

PREREQUISITES:

DFS

EXPLANATION:

Let M_u be the size of the biggest component we get on removing node u. We have to find the node removing which will give the smallest M_u. We can do this by finding an answer for each node and displaying the minimum.

Let’s assume the tree is rooted at node 1 and find the size of subtrees for each node and store it in the array sz such tat sz[u] gives the size of subtree u.

How?

This can be done with standard dfs and dp. See the solution.

Let’s focus on finding M_u for any node and then we can find the minimum amongst all M_us.

if a node is removed, the components formed will be rooted at all its children and 1 at its parent. Size of those at children is sz[child] and the size of the parent one is
N - (sum of the sizes of child subtrees). The max amongst them is our M_u.

We can calculate this for each node and find the optimal answer. Don’t forget to print the smallest node incase of multiple answers.

TIme complexity - O(N)

SOLUTIONS:

Setter's Solution 
//What a drag
#include <bits/stdc++.h>
#include <assert.h>
#define ll long long 
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ln cout << '\n'
#define mod 1000000007
#define MxN 100005
#define all(x) x.begin(), x.end()
using namespace std;
 
vector <int> G[MxN], sz(MxN), par(MxN);
int n;
void dfs(int u, int p){
 
	par[u] = p, sz[u] = 1;
	
	for(int child : G[u]){
		if(child != p){
			dfs(child, u);
			sz[u] += sz[child];
		}
	}
			
}
 
void solve(){
 
	int i, j;
	cin >> n;
	for(i = 0; i <= n; ++i) G[i].clear();
 
	for(i = 1; i < n; ++i){
		int u, v;
		cin >> u >> v;
		assert(u != v);
		G[u].push_back(v); G[v].push_back(u);
	}
	
	dfs(1, 0);
	
	int mn = n, ans = 0;
	
	for(i = 1; i <= n; ++i){
		
		int mx = 0, total = 0;
 
		for(int child : G[i]){
 
			if(child == par[i]) continue;
 
			mx = max(mx, sz[child]);
			total += sz[child];
		}
		assert(total < n);
		mx = max(mx, (n - total - 1));
 
		if(mx < mn){
			ans = i;
			mn = mx;
		}
	}
 
	cout << ans << " " << mn << '\n';
}
int main(){
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
 
	#ifndef ONLINE_JUDGE
		freopen("worstcase.in","r",stdin);
		freopen("worstcase.out","w",stdout);
	#endif
 
	int t = 1;
	cin >> t;
	while(t--)
		solve();
}
Tester Solution 
/*
    Arnab Chanda 
*/
 
// All imports here
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.stream.Collectors;
 
// Template code starts here //
 
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Debugger debug = new Debugger(out);
        Objectify objectify = new Objectify(debug);
        Task solver = new Task();
        int test = in.nextInt();
        while(test-->0){
            solver.solve(1, in, out, debug, objectify);
        }
		out.close();
	}
}
 
class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;
 
    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }
 
    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
 
    public int nextInt() {
        return Integer.parseInt(next());
    }
 
    public long nextLong() {
        return Long.parseLong(next());
    }
 
    public Double nextDouble() {
        return Double.parseDouble(next());
    }
 
    public float nextFloat() {
        return Float.parseFloat(next());
    }
 
}
 
class Debugger{
    PrintWriter out;
 
    Debugger(PrintWriter out){    
        this.out = out;
    }
 
    public <T> void printList(List<T> arrayList){
        for( Object ob: arrayList){
            out.print(ob+" ");
        }
        out.println();
    }
 
    public <T> void printSet(Set<T> set){
        for(Object ob: set){
            out.print(ob+" ");
        }
        out.println();
    }
 
    public <T> void printMap(Map<?,?> map){
        for(Object ob: map.keySet()){
            System.out.println(ob+" : "+map.get(ob));
        }
    }
}
 
class Objectify{
    
    Debugger debug;
 
    Objectify(Debugger ob){ debug = ob; }
 
    public void printArr(int[] arr){ debug.printList(Arrays.stream(arr).boxed().collect(Collectors.toList())); }
    public void printArr(double[] arr){ debug.printList(Arrays.stream(arr).boxed().collect(Collectors.toList())); }
    public void printArr(long[] arr){ debug.printList(Arrays.stream(arr).boxed().collect(Collectors.toList())); }
    public void printArr(char[] arr){ debug.printList( String.valueOf(arr).chars().mapToObj(c -> (char) c).collect(Collectors.toList())); }
    public void printArr(String[] arr){ debug.printList(Arrays.asList(arr)); }
 
    public void printMatrix(int[][] arr){ for(int a[]:arr) printArr(a); }
    public void printMatrix(double[][] arr){ for(double a[]:arr) printArr(a); }
    public void printMatrix(long[][] arr){ for(long a[]:arr) printArr(a); }
    public void printMatrix(char[][] arr){ for(char a[]:arr) printArr(a); }
    public void printMatrix(String[][] arr){ for(String a[]:arr) printArr(a); }
 
}
 
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
// Template code ends here
 
 
class Task {
 
    final long MOD = (int)Math.pow(10,9)+7;
	int n;
    public void solve(int testNumber, InputReader sc, PrintWriter out, Debugger debug, Objectify objectify) {
        
        // write your code here
		n = sc.nextInt();
		
		List<List<Integer>> map = new ArrayList<>();
 
		for(int i = 0; i <= n; i++){
			map.add(new ArrayList<>());
		}
 
		for(int i = 0; i < n-1; i++){
			int u = sc.nextInt();
			int v = sc.nextInt();
 
			map.get(u).add(v);
			map.get(v).add(u);
		}
 
		int [] ans = new int[n+1];
 
		dfs(map, ans, 1, 0);
 
		int X = 0;
		int W = Integer.MAX_VALUE;
		for(int i = n; i >= 1; i--){
			if (ans[i] <= W){
				W = ans[i];
				X = i;
			}
		}
 
		out.println(X+" "+W);
	}
	
	public int dfs(List<List<Integer>> map, int[] ans, int node, int parent){
		int sum = 0;
 
		for(int i: map.get(node)){
			if (i!=parent){
				int a = dfs(map, ans, i, node);
				ans[node] = Math.max(ans[node], a);
				sum+=a; 
			}
		}
		ans[node] = Math.max(ans[node], n - sum - 1);
 
		return sum + 1;
	}
}
5 Likes