一、AcWing 846. 樹的重心

1.1題目

1.2思路分析

題意：什么是樹的重心？

樹的重心是指，刪除某個結(jié)點后剩下的最大連通子樹的結(jié)點數(shù)目最小，如下圖是根據(jù)樣列生成的樹，若刪除結(jié)點1，則剩下三個子樹最大的是中間那顆結(jié)點有4個，即剩下的最大連通子樹的結(jié)點數(shù)目為4；若刪除結(jié)點2，則剩下兩個數(shù)目為1的子樹和一個數(shù)目為6的子樹，即剩下的最大連通子樹的結(jié)點數(shù)目為6；若刪除結(jié)點3，剩下一個數(shù)目為1的子樹，和一個數(shù)目為7的子樹，即剩下的最大連通子樹的結(jié)點數(shù)目為7……枚舉可得剩下的最小的最大連通子樹的結(jié)點數(shù)目為4也就是說結(jié)點1是樹的重心。另外注意題目要求答案是輸出剩下的最小的最大連通子樹的結(jié)點數(shù)目。

思路

深搜，算出每個結(jié)點被刪除后剩下的最大連通子樹的結(jié)點數(shù)目，輸出最小值即可，那么問題就是怎么求一個結(jié)點被刪除后的最大連通子樹的結(jié)點數(shù)目，刪除一個結(jié)點后，剩下的子樹可以被分為兩個部分，例如刪除結(jié)點4：

藍色部分是結(jié)點4的子樹，紅色部分我們暫時稱為其他部門，因為我們知道樹的總結(jié)點數(shù)n，只要能算出藍色部分的數(shù)目s，那么其他部分的數(shù)目就是n-s。

1.3Ac代碼

import java.io.*;
import java.util.Arrays;public class Main {static int N = 100010;static int M=2*N; //n-1條無向邊需要兩倍空間來存儲static int[] h = new int[N]; //鄰接表存儲樹，有n個節(jié)點，所以需要n個隊列頭節(jié)點static boolean[] st = new boolean[N]; //記錄節(jié)點是否被訪問過，訪問過則標(biāo)記為truestatic int[] e = new int[M]; //存儲元素static int[] ne = new int[M]; //存儲列表的next值static int n, idx; //題目所給的輸入，n個節(jié)點以及單鏈表指針static int ans=N;   //表示重心的所有的子樹中，最大的子樹的結(jié)點數(shù)目public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));n=Integer.parseInt(br.readLine());Arrays.fill(h,1,n+1,-1);    //結(jié)點從1開始，開始時邊為空，即h數(shù)組值為-1表示無出邊f(xié)or (int i = 0; i < n-1; i++) {String []s=br.readLine().split(" ");int a=Integer.parseInt(s[0]);int b=Integer.parseInt(s[1]);add(a,b);   add(b,a);}dfs(1);System.out.println(ans);}private static int  dfs(int u) {st[u]=true;int sum=1;  //當(dāng)前子樹大小，包括自己故從1開始int res=0;  //刪除該結(jié)點后每一個連通塊大小的最大值for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(!st[j]){int s=dfs(j);    //其兒子子樹的大小res=Math.max(res,s); //找出兒子子樹中的最大值sum+=s;}}res=Math.max(res,n-sum);//每個結(jié)點dfs最終得出的這個res即為以該結(jié)點為重心，刪除后各個連通塊中點數(shù)的最大值ans=Math.min(res,ans);return sum;}private static void add(int a, int b) {e[idx]=b;ne[idx]=h[a];h[a]=idx++;}
}

二、AcWing 847. 圖中點的層次

2.1題目

2.2思路分析

用 d數(shù)組保存1號節(jié)點到各個節(jié)點的距離。

用 st 數(shù)組標(biāo)記各個節(jié)點有沒有走到過。

從 1 號節(jié)點開始，廣度優(yōu)先遍歷：

1 號節(jié)點入隊列，d[1] 的值更新為 0。

如果隊列非空，就取出隊頭，找到隊頭節(jié)點能到的所有節(jié)點。如果隊頭節(jié)點能到走到的節(jié)點沒有標(biāo)記過，就將節(jié)點的d值更新為隊頭的d值+1，然后入隊。

重復(fù)步驟 2 直到隊列為空。

這個時候，d數(shù)組中就存儲了 1 號節(jié)點到各個節(jié)點的距離了。

圖的存儲：鄰接表

用 h 數(shù)組保存各個節(jié)點能到的第一個節(jié)點的編號。開始時，h[i] 全部為 -1。

用 e 數(shù)組保存節(jié)點編號，ne 數(shù)組保存 e 數(shù)組對應(yīng)位置的下一個節(jié)點所在的索引。

用 idx 保存下一個 e 數(shù)組中，可以放入節(jié)點位置的索引

插入邊使用的頭插法，例如插入：a->b。首先把b節(jié)點存入e數(shù)組，e[idx] = b。然后 b 節(jié)點的后繼是h[a]，ne[idx] = h[a]。最后，a 的后繼更新為 b 節(jié)點的編號，h[a] = idx，索引指向下一個可以存儲節(jié)點的位置，idx ++ 。

2.3Ac代碼

import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Map;
import java.util.Queue;public class Main {static int N = 100010;static int[] h = new int[N]; //鄰接表存儲樹，有n個節(jié)點，所以需要n個隊列頭節(jié)點static boolean[] st = new boolean[N]; //記錄節(jié)點是否被訪問過，訪問過則標(biāo)記為truestatic int[] d = new int[N]; //存儲距離static int[] e = new int[N]; //存儲元素static int[] ne = new int[N]; //存儲列表的next值static int n,m, idx; //題目所給的輸入，n個節(jié)點以及單鏈表指針public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String []s=br.readLine().split(" ");n=Integer.parseInt(s[0]);    m=Integer.parseInt(s[1]);Arrays.fill(h,-1);for (int i = 0; i < m; i++) {s=br.readLine().split(" ");int a=Integer.parseInt(s[0]);int b=Integer.parseInt(s[1]);add(a,b);}bfs();System.out.println(d[n]);}private static void bfs() {Queue<Integer> q=new ArrayDeque<>();Arrays.fill(d,-1);q.add(1);d[1]=0;st[1]=true;while (!q.isEmpty()){int he=q.poll();for(int i=h[he] ;i!=-1;i=ne[i]){int t=e[i];if(!st[t]){d[t]=d[he]+1;q.add(t);st[t]=true;}}}}private static void add(int a, int b) {e[idx] = b;ne[idx] = h[a];h[a] = idx++;}}