4.9小红书笔试第一题

太菜了，直接把这个题弃了，后来写完也不知道正确与否，记录一下，以后遇到这样的题至少思路是有的

平衡
时间限制： 1000MS
内存限制： 65536KB
题目描述：
输入一棵树 T，你需要删除一条边，这棵树会被分成A 和 B 两棵树。你需要让两部分的节点数的差的绝对值| |A|-|B| |尽可能小。输出最小的| |A|-|B| |和最优方案的数量。



输入描述
第一行一个整数 n表示节点的数量，节点从1 到 n编号。

接下来n-1行每行两个正整数 s t，表示s的父亲是t。

输入保证是一棵树。

对于所有数据 1<=n<=100000。

输出描述
输出一行，两个整数，用空格分开，分别表示最优解和最优方案数。


样例输入
3
2 1
3 1
样例输出
1 2
*/

import java.util.*;
public class Main
{    
  static ArrayList<Integer>[] g = new ArrayList[100005];   
  static int[] num = new int[1000005];  
  static int n; 
  static int res = 0;   
  static int min = Integer.MAX_VALUE;   
  public static void main(String[] args) {   
	Scanner sc = new Scanner(System.in);    
	Arrays.fill(num,1);      
	n = sc.nextInt();     
	boolean [] notRoot = new boolean[n+1];     
	for(int i = 1; i <= n; i++)
	{          
	  g[i] = new ArrayList<Integer>();      
	}       
	int root = 0;        
	for(int i = 1; i < n; i++) {     
	  int tail = sc.nextInt();      
	  int head = sc.nextInt();         
	  g[tail].add(head);     
	  g[head].add(tail);           
	  notRoot[tail] = true;      
	}     
	for(int i = 1; i <= n; i++) {    
	  if(!notRoot[i])
	  {       
		root = i;          
	  }       
	}       
	dfs(root,-1);     
	dfs2(root,-1);       
	System.out.println(min +" " + res);   
  }    
  public static int dfs(int cur, int prev) {    
	for(int next:g[cur]) {      
	  if(next == prev)        
		continue;         
	  num[cur] += dfs(next,cur); 
	}         
	return num[cur]; 
  }    
  public static void dfs2(int cur, int prev) { 
	if(Math.abs(n-2*num[cur]) < min) {  
	  res = 1;       
	  min = Math.abs(n-2*num[cur]); 
	} else if(Math.abs(n-2*num[cur]) == min) {  
	  res ++;  
	}       
	for(int next:g[cur]) {  
	  if(next == prev)   
		continue;    
	  dfs2(next,cur);  
	}        
	return;    }}