# ECAUG207 - Editorial

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

MEDIUM

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.IOException;
import java.io.InputStream;
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;
PrintWriter out = new PrintWriter(outputStream);
Debugger debug = new Debugger(out);
Objectify objectify = new Objectify(debug);
int test = in.nextInt();
while(test-->0){
solver.solve(1, in, out, debug, objectify);
}
out.close();
}
}

public StringTokenizer tokenizer;

tokenizer = null;
}

public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}

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

final long MOD = (int)Math.pow(10,9)+7;
int n;
public void solve(int testNumber, InputReader sc, PrintWriter out, Debugger debug, Objectify objectify) {

n = sc.nextInt();

List<List<Integer>> map = new ArrayList<>();

for(int i = 0; i <= n; i++){
}

for(int i = 0; i < n-1; i++){
int u = sc.nextInt();
int v = sc.nextInt();

}

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

``````
4 Likes