題干：

題目描述?Description

給出一棵樹，求出樹的中心。

為了定義樹的中心，首先給每個(gè)結(jié)點(diǎn)進(jìn)行標(biāo)號。對于一個(gè)結(jié)點(diǎn)K，如果把K從樹中刪除（連同與它相連的邊一起），剩下的被分成了很多塊，每一塊顯然又是一棵樹（即剩下的部分構(gòu)成了一個(gè)森林）。則給結(jié)點(diǎn)K所標(biāo)的號就是森林中結(jié)點(diǎn)個(gè)數(shù)最多的樹所擁有的結(jié)點(diǎn)數(shù)。如果結(jié)點(diǎn)K的標(biāo)號不大于其他任何一個(gè)結(jié)點(diǎn)的標(biāo)號，則結(jié)點(diǎn)K被稱為是樹的中心。

輸入描述?Input Description

輸入：

輸入的第一行包含一個(gè)整數(shù)N（1≤N≤16 000），表示樹中的結(jié)點(diǎn)數(shù)。接下來N-1行，每個(gè)兩個(gè)整數(shù)a,b，由一個(gè)空格分隔，表示a與b之間有一條邊。

輸出描述?Output Description

輸出：

輸出兩行，第一行兩個(gè)整數(shù)v,T，v表示樹的中心結(jié)點(diǎn)的標(biāo)號，T表示樹有多少個(gè)中心。第二行包含T個(gè)數(shù)，為所有樹的中心的編號，按升序排列。

樣例輸入?Sample Input

樣例輸入：

7

1 2

2 3

2 4

1 5

5 6

6 7

樣例輸出?Sample Output

樣例輸出：

3 1

1

數(shù)據(jù)范圍及提示?Data Size & Hint

數(shù)據(jù)范圍: 20% N<=100 100% N<=16 000

解題報(bào)告：

? ? ?裸題模板不解釋了。。。注意輸出的時(shí)候有空格、、、他這個(gè)樣例體現(xiàn)不出來、、開了個(gè)num數(shù)組記錄

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; vector<int> vv[MAX]; int dp[MAX],sum[MAX]; int n; int dfs(int cur,int root) {int up = vv[cur].size();int res = 1,tmp;//if(up == 1) return 1;for(int i = 0; i<up; i++) {int v = vv[cur][i];if(v == root) continue;tmp = dfs(v,cur);dp[cur] = max(dp[cur],tmp);res += tmp;}dp[cur] = max(dp[cur],n-res);return sum[cur] = res; } int main() {while(~scanf("%d",&n)) {for(int i = 1; i<=n; i++) vv[i].clear(),dp[i]=1;for(int i = 1; i<=n-1; i++) {int x,y;scanf("%d%d",&x,&y);vv[x].pb(y);vv[y].pb(x);}dfs(1,-1);int minn = 0x3f3f3f3f;for(int i = 1; i<=n; i++) {minn = min(minn,dp[i]);}int cnt = 0,flag = 0;for(int i = 1; i<=n; i++) {if(dp[i] == minn ) cnt++;}printf("%d %d\n",minn ,cnt);for(int i = 1; i<=n; i++) {if(dp[i] == minn ) {if(flag != 0) putchar(' ');flag=1;printf("%d",i);}}printf("\n");}return 0 ;}

?

總結(jié)

以上是生活随笔為你收集整理的【CodeVS - 3639】（树的重心模板，裸题）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。