AcWing 846. 树的重心java
原题链接
简单
作者:
huaqingren
,
2021-02-08 20:18:20
,
所有人可见
,
阅读 191
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main
{
private static int N=100010;
private static boolean[] st=new boolean[N];
private static List<Integer>[] list;
private static int ans=N;
private static int n;
public static void main(String[] args)
{
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
//邻接表
list=new ArrayList[N];
for(int i=1;i<=n;i++)
list[i]=new ArrayList<>();
for(int i=0;i<n-1;i++)
{
int a=scan.nextInt();
int b=scan.nextInt();
list[a].add(b);
list[b].add(a);
}
dfs(1);
System.out.println(ans);
scan.close();
}
//以u为根节点的节点数量
private static int dfs(int u)
{
st[u]=true;
int sum=1,size=0;
for(int i=0;i<list[u].size();i++)
{
int t=list[u].get(i);
if(st[t]) continue;
int s=dfs(t);
size=Math.max(size, s);
sum+=s;
}
size=Math.max(size, n-sum);
ans=Math.min(ans, size);
return sum;
}
}