[基礎算法6] 樹的重心
題目描述
題目描述：
? ? ? 給定一顆樹，樹中包含N個結(jié)點（編號從1-N），和N- 1 條無向邊。請你找到樹的重心，并輸出 將重心刪除后，剩余各個連通塊中點數(shù)的最大值。
? ? ? 重心定義：重心是指樹中的一個結(jié)點，如果將這個點刪除后，剩余各個連通塊中點數(shù)的最大值最小，那么這個結(jié)點被 稱為樹的重心。
輸入格式：??
? ? ?第一行包含整數(shù)N，表示 樹的結(jié)點數(shù)，１＜＝Ｎ＜＝１ｅ５ ，接下來Ｎ－１行，每行包含兩個整數(shù)ａ和ｂ，表示 ａ和ｂ之 間存在一條邊。
輸出格式：
? ? ?輸出一個整數(shù) N，表示 將重心刪除后，剩余各個連通塊中點數(shù)的最大值。
樣例輸入?復制
9
1 4
1 2
2 6
2 5
6 3
6 7
7 9
7 8
樣例輸出?復制
4
來源/分類
樹DP
程序：
#include <iostream>using namespace std;const int N=1e5+10;bool vis[N];int E[2*N],ne[2*N],h[N],id,ans=0x3f3f3f3f,n;?
int dfs(int u){????vis[u]=true;//標記u這個點被搜過????int size=0;//記錄u的最大子樹的結(jié)點數(shù)????int sum=1;//記錄以u為根的子樹的結(jié)點數(shù)????for(int i=h[u];i!=0;i=ne[i])//i是邊的編號????{????????int j=E[i];//j是u的鄰接點????????if(vis[j])????????????continue;//避免向上查找????????int s=dfs(j);//s是以j為根的子樹的結(jié)點數(shù)????????size=max(size,s);//記錄u的最大子樹的結(jié)點數(shù)????????sum+=s;//累加u的各個子樹的結(jié)點數(shù)????}????ans=min(ans,max(size,n-sum));//更新答案????return sum;//返回以u為根的子樹的結(jié)點數(shù)}?
void add(int x,int y)//鄰接表{????E[++id]=y;????ne[id]=h[x];????h[x]=id;}//加邊?
int main(){????cin>>n;????for(int i=1;i<=n;i++)????{????????int x,y;????????cin>>x>>y;????????add(x,y);????????add(y,x);//建圖????}????dfs(1);????cout<<ans<<endl;????return 0;}標簽：
