樹的重心POJ 1655樹的最長路徑最遠點對POJ 1985樹的最大獨立集POJ 2342
對于一棵n個結點的無根樹，找到一個點，使得把樹變成以該點為根的有根樹時，最大子樹的結點數最小，該點即為重心。換句話說，刪除這個點后最大連通塊（一定是樹）的結點數最小。
一道典型的求樹的重心的題目，用dfs實現 用數組dp[i]記錄i的最大子樹的大小，son[i]記錄兒子的個數 樹的重心即為所有節點中最大子樹大小最小的節點
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#define L 20010using namespace std;struct node{ int nxt, to;} a[L << 1];int n, T, u, v, head[L], cnt, son[L], siz, ans, dp[L];inline void add(int x, int y) { a[++cnt].nxt = head[x]; a[cnt].to = y; head[x] = cnt;}inline void dfs(int s, int fa) { dp[s] = 0, son[s] = 1; for (int i = head[s]; i; i = a[i].nxt) { int u = a[i].to; if (u == fa) continue; dfs(u, s); dp[s] = max(dp[s], son[u]); son[s] += son[u]; } dp[s] = max(dp[s], n - son[s]);}int main() { scanf("%d", &T); while (T--) { memset(a, 0, sizeof(a)); memset(head, 0, sizeof(head)); memset(dp, 0, sizeof(dp)); memset(son, 0, sizeof(son)); cnt = 0; scanf("%d", &n); for (int i = 1; i < n; ++i) { scanf("%d %d", &u, &v); add(u, v), add(v, u); } dfs(1, 0); ans = 1, siz = dp[1]; for (int i = 2; i <= n; ++i) if (dp[i] < siz) ans = i, siz = dp[i]; 樹的最長路徑（最遠點對）樹形DP的板子題 不斷dfs更新出以每個點為根節點最遠及次遠的長度，輸出長度和的最大值即可
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#define L 1000010using namespace std;struct node{ int nxt, to; long long l;} e[L];int n, m, a, b, head[L], cnt;long long c, dp1[L], dp2[L], ans;char pd[3];inline void add(int a, int b, long long d) { e[++cnt].nxt = head[a]; e[cnt].to = b; e[cnt].l = d; head[a] = cnt;}inline void dfs(int x, int fa) { for (int i = head[x]; i; i = e[i].nxt) { int u = e[i].to; if (u == fa) continue; dfs(u, x); if (dp1[x] < dp1[u] + e[i].l) dp2[x] = dp1[x], dp1[x] = dp1[u] + e[i].l; else dp2[x] = max(dp2[x], dp1[u] + e[i].l); } ans = max(ans, dp1[x] + dp2[x]);}int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= m; ++i) { scanf("%d %d %lld %s", &a, &b, &c, pd); add(a, b, c), add(b, a, c); } dfs(1, 0); printf("%lld/n", ans); return 0;}對于每一個節點有兩種情況，去或者不去，可用二維狀態表示 若i去了，則i的兒子不能去，dfs更新值即可
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#define L 6000 + 10using namespace std;int n, a, b, root, fa[L], vis[L], dp[L][2];inline void dfs(int x) { vis[x] = 1; for (int i = 1; i <= n; ++i) if (fa[i] == x && !vis[i]) { dfs(i); dp[x][1] += dp[i][0]; dp[x][0] += max(dp[i][1], dp[i][0]); }}int main() { while (scanf("%d", &n) == 1){ for (int i = 1; i <= n; ++i) scanf("%d", &dp[i][1]); root = 0; while(scanf("%d %d", &a, &b) && a && b) fa[a] = b, root = b; memset(vis, 0, sizeof(vis)); dfs(root); printf("%d/n", max(dp[root][1], dp[root][0])); } return 0;}新聞熱點
疑難解答
