目标:Java web开发
问题树的重心
import java.io.*;
public class Main {
static final int N=(int)1e5+10,M=N<<1,INF=(int)1e9;
static int n,idx,min=INF;
static int[] h=new int[N],e=new int[M],ne=new int[M];
static boolean[] status=new boolean[N];
static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in)));
static void add(int u,int v) {
e[idx]=v;
ne[idx]=h[u];
h[u]=idx++;
}
static int dfs(int u){
status[u]=true;
int s,sum=1,max=-INF;
for (int i=h[u];i!=-1;i=ne[i]){
if(status[e[i]]) continue;
s=dfs(e[i]);
max=Math.max(max,s);
sum+=s;
}
max=Math.max(max,n-sum);
min=Math.min(min,max);
return sum;
}
public static void main(String[] args)throws IOException{
bf.nextToken();
n = (int)st.nval;
for (int i = 1; i <= n; ++i) {
h[i] = -1;
}
int a, b;
for (int i = 1; i < n; ++i) {
st.nextToken();
a=(int)st.nval;
st.nextToken();
b=(int)st.nval;
add(a, b);
add(b, a);
}
dfs(1);
bw.write(min + "");
bw.close();
}
}