裸的树的重心，要注意的问题是此题的边并没有给出准确的父子拓扑关系，所以需要建双向的边，所以以后要看清题意做仔细分析。
可以知道一个结点的子树必定是 它的拓扑子树 和 根树去掉这个拓扑结点树本身，思路也就很明显了。
1 // poj1655 Balancing Act 2 #include <iostream> 3 #include <cstring> 4 #define NDEBUG 5 6 #ifndef NDEBUG 7 #include <cstdio> 8 #endif 9 10 #define MAXN 20005 11 12 using namespace std; 13 14 int N; 15 int edgefw[MAXN*2], edge[MAXN*2], head[MAXN], eptr; 16 17 #define EI(j, k) ({ 18 edge[eptr] = k, edgefw[eptr] = head[j]; 19 head[j] = eptr++; 20 }) 21 22 int dp[MAXN], dp2[MAXN]; 23 char vis[MAXN]; 24 25 void dfs(int i) 26 { 27 vis[i] = 1; 28 int p, maxk = 0, sumn = 1; 29 for(p = head[i]; p>=0; p = edgefw[p]) { 30 int t = edge[p]; 31 if (!vis[t]) { 32 if (!dp2[t]) dfs(t); 33 sumn += dp2[t]; 34 if (maxk < dp2[t]) 35 maxk = dp2[t]; 36 } 37 } 38 if (sumn != N && N - sumn > maxk) maxk = N - sumn; 39 dp[i] = maxk, dp2[i] = sumn; 40 } 41 42 int main(void) 43 { 44 #ifndef NDEBUG 45 freopen("poj1655.in", "r", stdin); 46 #endif // NDEBUG 47 int T; 48 for(cin >> T; T; --T) { 49 cin >> N; 50 memset(vis, 0, sizeof(vis)); 51 memset(dp2, 0, sizeof(dp2)); 52 memset(head, -1, sizeof(head)), eptr = 0; 53 int i, j, root; 54 root = 0; 55 for(i=0; i<N-1; ++i) { 56 int k; 57 cin >> j >> k; 58 --j,--k; EI(j, k), EI(k, j); 59 if (root == k) root = j; 60 } 61 dfs(root); 62 j = 0; 63 for(i = 1; i < N; ++i) 64 if (dp[i] < dp[j]) 65 j = i; 66 cout << j+1 << ' ' << dp[j] << endl; 67 } 68 return 0; 69 }
提交记录：
| Accepted | 1292K | 610MS | G++ | 1269B | 2014-04-30 21:28:41 |
