{"id":43,"date":"2026-04-05T16:01:57","date_gmt":"2026-04-05T08:01:57","guid":{"rendered":"https:\/\/blog.sjll.top\/?p=43"},"modified":"2026-04-05T16:01:57","modified_gmt":"2026-04-05T08:01:57","slug":"%e6%a0%91%e5%bd%a2%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92%e7%ae%97%e6%b3%95%e8%af%a6%e8%a7%a3%ef%bc%9ac%e5%ae%9e%e7%8e%b0%e6%9c%80%e5%a4%a7%e7%8b%ac%e7%ab%8b%e9%9b%86%e4%b8%8e%e6%a0%91%e7%9a%84","status":"publish","type":"post","link":"https:\/\/www.sjll.top\/index.php\/2026\/04\/05\/%e6%a0%91%e5%bd%a2%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92%e7%ae%97%e6%b3%95%e8%af%a6%e8%a7%a3%ef%bc%9ac%e5%ae%9e%e7%8e%b0%e6%9c%80%e5%a4%a7%e7%8b%ac%e7%ab%8b%e9%9b%86%e4%b8%8e%e6%a0%91%e7%9a%84\/","title":{"rendered":"\u6811\u5f62\u52a8\u6001\u89c4\u5212\u7b97\u6cd5\u8be6\u89e3\uff1aC++\u5b9e\u73b0\u6700\u5927\u72ec\u7acb\u96c6\u4e0e\u6811\u7684\u76f4\u5f84"},"content":{"rendered":"\n

\u4ec0\u4e48\u662f\u6811\u5f62DP\uff1f<\/h2>\n\n\n\n

\u6811\u5f62\u52a8\u6001\u89c4\u5212\uff08Tree DP\uff09<\/strong> \u662f\u5728\u6811\u5f62\u6570\u636e\u7ed3\u6784\u4e0a\u8fdb\u884c\u52a8\u6001\u89c4\u5212\u7684\u7279\u6b8a\u5f62\u5f0f\u3002\u7531\u4e8e\u6811\u6ca1\u6709\u73af\u72b6\u7ed3\u6784\uff0c\u5929\u7136\u9002\u5408\u4f7f\u7528 DP \u5904\u7406\u3002\u6811\u5f62 DP \u901a\u5e38\u91c7\u7528DFS\uff08\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\uff09<\/strong> \u7684\u987a\u5e8f\uff0c\u81ea\u5e95\u5411\u4e0a\u5730\u8ba1\u7b97\u72b6\u6001\uff0c\u662f\u7b97\u6cd5\u7ade\u8d5b\u4e2d\u7684\u91cd\u8981\u9898\u578b\u3002<\/p>\n\n\n\n

\u6811\u5f62DP\u7684\u6838\u5fc3\u601d\u60f3<\/h3>\n\n\n\n
  1. \u6811\u5f62\u7ed3\u6784 + \u52a8\u6001\u89c4\u5212<\/strong>\uff1a\u5229\u7528\u6811\u7684\u7236\u5b50\u5173\u7cfb\u5b9a\u4e49\u72b6\u6001<\/li>
  2. \u81ea\u5e95\u5411\u4e0a\u8ba1\u7b97<\/strong>\uff1a\u5148\u8ba1\u7b97\u5b50\u6811\u7684\u6700\u4f18\u89e3\uff0c\u518d\u5408\u5e76\u5230\u7236\u8282\u70b9<\/li>
  3. \u65e0\u540e\u6548\u6027<\/strong>\uff1a\u5b50\u6811\u7684\u51b3\u7b56\u4e0d\u4f1a\u5f71\u54cd\u5176\u4ed6\u5b50\u6811<\/li><\/ol>\n\n\n\n

    \u5e38\u89c1\u7684\u6811\u5f62DP\u95ee\u9898<\/h3>\n\n\n\n
    1. \u6811\u7684\u6700\u5927\u72ec\u7acb\u96c6<\/strong>\uff1a\u9009\u62e9\u82e5\u5e72\u8282\u70b9\uff0c\u4f7f\u5f97\u6ca1\u6709\u8fb9\u76f8\u8fde<\/li>
    2. \u6811\u7684\u91cd\u5fc3<\/strong>\uff1a\u5220\u9664\u67d0\u8282\u70b9\u540e\uff0c\u4f7f\u6700\u5927\u5b50\u6811\u6700\u5c0f<\/li>
    3. \u6811\u7684\u76f4\u5f84<\/strong>\uff1a\u6811\u4e2d\u6700\u957f\u8def\u5f84<\/li>
    4. \u6811\u4e0a\u80cc\u5305<\/strong>\uff1a\u5728\u6811\u4e0a\u8fdb\u884c\u80cc\u5305DP<\/li><\/ol>\n\n\n\n

      C++ \u4ee3\u7801\u5b9e\u73b0<\/h3>\n\n\n\n
      #include <iostream>\n#include <vector>\nusing namespace std;\n\n\/\/ \u6811\u5f62DP - \u6811\u7684\u6700\u5927\u72ec\u7acb\u96c6\n\/\/ \u6700\u5927\u72ec\u7acb\u96c6\uff1a\u9009\u4e2d\u7684\u8282\u70b9\u4e4b\u95f4\u6ca1\u6709\u8fb9\u76f8\u8fde\n\nstruct TreeNode {\n    int val;\n    vector<TreeNode*> children;\n    TreeNode(int x) : val(x) {}\n};\n\nstruct State {\n    int select;   \/\/ \u9009\u62e9\u8be5\u8282\u70b9\u65f6\u7684\u6700\u5927\u72ec\u7acb\u96c6\u5927\u5c0f\n    int not_select;  \/\/ \u4e0d\u9009\u62e9\u8be5\u8282\u70b9\u65f6\u7684\u6700\u5927\u72ec\u7acb\u96c6\u5927\u5c0f\n};\n\nState dfs_max_independent_set(TreeNode* root) {\n    if (!root) return {0, 0};\n    \n    State state;\n    state.select = 1;  \/\/ \u9009\u62e9\u8be5\u8282\u70b9\uff0c\u8ba1\u6570+1\n    \n    for (auto child : root->children) {\n        State childState = dfs_max_independent_set(child);\n        \n        \/\/ \u5982\u679c\u9009\u62e9\u4e86\u5f53\u524d\u8282\u70b9\uff0c\u5b50\u8282\u70b9\u53ea\u80fd\u4e0d\u9009\n        state.select += childState.not_select;\n        \n        \/\/ \u5982\u679c\u4e0d\u9009\u5f53\u524d\u8282\u70b9\uff0c\u5b50\u8282\u70b9\u53ef\u4ee5\u9009\u4e5f\u53ef\u4ee5\u4e0d\u9009\uff0c\u53d6\u6700\u5927\u503c\n        state.not_select += max(childState.select, childState.not_select);\n    }\n    \n    return state;\n}\n\n\/\/ \u6811\u7684\u91cd\u5fc3\uff1a\u4f7f\u5f97\u6240\u6709\u5b50\u6811\u8282\u70b9\u6570\u6700\u5927\u503c\u6700\u5c0f\u7684\u8282\u70b9\npair<int, int> find_tree_centroid(int n, const vector<vector<int>>& adj) {\n    \/\/ \u8fd4\u56de {\u91cd\u5fc3\u8282\u70b9, \u6700\u5927\u5b50\u6811\u5927\u5c0f}\n    vector<int> subtree_size(n + 1);\n    vector<bool> visited(n + 1, false);\n    \n    function<int(int)> dfs = [&](int u) -> int {\n        visited[u] = true;\n        int size = 1;\n        int max_subtree = 0;\n        \n        for (int v : adj[u]) {\n            if (!visited[v]) {\n                int child_size = dfs(v);\n                size += child_size;\n                max_subtree = max(max_subtree, child_size);\n            }\n        }\n        \n        max_subtree = max(max_subtree, n - size);  \/\/ \u7236\u65b9\u5411\u5b50\u6811\n        subtree_size[u] = size;\n        \n        return subtree_size[u];\n    };\n    \n    dfs(1);  \/\/ \u4ece\u4efb\u610f\u8282\u70b9\u5f00\u59cb\n    \n    \/\/ \u627e\u91cd\u5fc3\n    int centroid = 1;\n    int min_max_subtree = n;\n    \n    for (int i = 1; i <= n; i++) {\n        int max_sub = max(subtree_size[i], n - subtree_size[i]);\n        if (max_sub < min_max_subtree) {\n            min_max_subtree = max_sub;\n            centroid = i;\n        }\n    }\n    \n    return {centroid, min_max_subtree};\n}\n\n\/\/ \u6811\u7684\u76f4\u5f84\uff08\u6700\u957f\u8def\u5f84\uff09\npair<int, pair<int, int>> tree_diameter(const vector<vector<int>>& adj) {\n    \/\/ \u8fd4\u56de {\u76f4\u5f84\u957f\u5ea6, {\u8d77\u70b9, \u7ec8\u70b9}}\n    int n = adj.size() - 1;\n    vector<int> dist(n + 1, -1);\n    vector<bool> visited(n + 1, false);\n    \n    function<void(int)> bfs = [&](int start) {\n        queue<int> q;\n        q.push(start);\n        dist[start] = 0;\n        visited[start] = true;\n        \n        while (!q.empty()) {\n            int u = q.front();\n            q.pop();\n            \n            for (int v : adj[u]) {\n                if (!visited[v]) {\n                    visited[v] = true;\n                    dist[v] = dist[u] + 1;\n                    q.push(v);\n                }\n            }\n        }\n    };\n    \n    \/\/ \u7b2c\u4e00\u6b21BFS\u627e\u6700\u8fdc\u70b9\n    bfs(1);\n    int farthest = 1;\n    for (int i = 1; i <= n; i++) {\n        if (dist[i] > dist[farthest]) farthest = i;\n    }\n    \n    \/\/ \u7b2c\u4e8c\u6b21BFS\u4ece\u6700\u8fdc\u70b9\u51fa\u53d1\n    fill(visited.begin(), visited.end(), false);\n    bfs(farthest);\n    int other_end = 1;\n    for (int i = 1; i <= n; i++) {\n        if (dist[i] > dist[other_end]) other_end = i;\n    }\n    \n    return {dist[other_end], {farthest, other_end}};\n}<\/code><\/pre>\n\n\n\n
      \u6811\u4e0a\u80cc\u5305<\/h3>\n\n\n\n
      \u5728\u6811\u5f62\u7ed3\u6784\u4e0a\u8fdb\u884c\u80cc\u5305DP\uff0c\u662f\u6811\u5f62DP\u7684\u7ecf\u5178\u5e94\u7528\uff1a<\/p>\n\n\n\n
      \/\/ \u6811\u4e0a\u80cc\u5305\uff1a\u9009\u62e9\u82e5\u5e72\u8282\u70b9\uff0c\u603b\u4ef7\u503c\u6700\u5927\uff0c\u53d7\u5bb9\u91cf\u9650\u5236\nvoid tree_knapsack(int u, int parent, const vector<vector<int>>& adj,\n                   const vector<int>& weight, const vector<int>& value,\n                   vector<vector<int>>& dp, int W) {\n    \/\/ dp[v][w] \u8868\u793a\u4ee5 v \u4e3a\u6839\u7684\u5b50\u6811\u4e2d\uff0c\u5bb9\u91cf\u4e3a w \u65f6\u7684\u6700\u5927\u4ef7\u503c\n    \n    \/\/ \u521d\u59cb\u5316\uff1a\u9009\u62e9\u5f53\u524d\u8282\u70b9\n    dp[u][weight[u]] = value[u];\n    \n    for (int v : adj[u]) {\n        if (v == parent) continue;\n        \n        tree_knapsack(v, u, adj, weight, value, dp, W);\n        \n        \/\/ \u80cc\u5305\u5408\u5e76\uff1a\u5c06\u5b50\u6811\u7684DP\u7ed3\u679c\u5408\u5e76\u5230\u5f53\u524d\u8282\u70b9\n        for (int w = W; w >= 0; w--) {\n            for (int k = 0; k + w <= W; k++) {\n                if (dp[v][k] > 0) {\n                    dp[u][w + k] = max(dp[u][w + k], dp[u][w] + dp[v][k]);\n                }\n            }\n        }\n    }\n}<\/code><\/pre>\n\n\n\n
      \u5b8c\u5168\u793a\u4f8b\uff1a\u4e8c\u53c9\u6811\u7684\u6700\u5927\u72ec\u7acb\u96c6<\/h3>\n\n\n\n
      \/\/ \u6784\u5efa\u4e8c\u53c9\u6811\nTreeNode* build_tree() {\n    TreeNode* root = new TreeNode(1);\n    root->left = new TreeNode(2);\n    root->right = new TreeNode(3);\n    root->left->left = new TreeNode(4);\n    root->left->right = new TreeNode(5);\n    root->right->left = new TreeNode(6);\n    return root;\n}\n\n\/\/ \u8f6c\u6362\u4e3a\u4e00\u822c\u6811\u7684\u90bb\u63a5\u8868\u8868\u793a\nvoid tree_to_adj(TreeNode* root, vector<vector<int>>& adj, int parent = -1) {\n    if (!root) return;\n    int u = root->val;\n    \n    for (auto child : root->children) {\n        if (child->val != parent) {\n            adj[u].push_back(child->val);\n            adj[child->val].push_back(u);\n            tree_to_adj(child, adj, u);\n        }\n    }\n}\n\nint main() {\n    \/\/ \u793a\u4f8b\uff1a\u6811\u7684\u90bb\u63a5\u8868\u8868\u793a\n    \/\/       1\n    \/\/      \/|\\\n    \/\/     2 3 4\n    \/\/    \/| |\\\n    \/\/   5 6 7 8\n    \n    int n = 8;\n    vector<vector<int>> adj(n + 1);\n    adj[1] = {2, 3, 4};\n    adj[2] = {1, 5, 6};\n    adj[3] = {1, 7};\n    adj[4] = {1, 8};\n    adj[5] = {2};\n    adj[6] = {2};\n    adj[7] = {3};\n    adj[8] = {4};\n    \n    \/\/ 1. \u6811\u7684\u91cd\u5fc3\n    auto [centroid, max_sub] = find_tree_centroid(n, adj);\n    cout << \"\u6811\u7684\u91cd\u5fc3: \u8282\u70b9\" << centroid << \", \u6700\u5927\u5b50\u6811\u5927\u5c0f: \" << max_sub << endl;\n    \n    \/\/ 2. \u6811\u7684\u76f4\u5f84\n    auto [diameter, endpoints] = tree_diameter(adj);\n    cout << \"\u6811\u7684\u76f4\u5f84: \" << diameter << \", \u7aef\u70b9: \" \n         << endpoints.first << \" - \" << endpoints.second << endl;\n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n
      \u590d\u6742\u5ea6\u5206\u6790<\/h3>\n\n\n\n
      \u95ee\u9898<\/th>\u65f6\u95f4\u590d\u6742\u5ea6<\/th>\u7a7a\u95f4\u590d\u6742\u5ea6<\/th><\/tr><\/thead>
      \u6700\u5927\u72ec\u7acb\u96c6<\/td>O(n)<\/td>O(n)<\/td><\/tr>
      \u6811\u7684\u91cd\u5fc3<\/td>O(n)<\/td>O(n)<\/td><\/tr>
      \u6811\u7684\u76f4\u5f84<\/td>O(n)<\/td>O(n)<\/td><\/tr>
      \u6811\u4e0a\u80cc\u5305<\/td>O(n \u00d7 W)<\/td>O(n \u00d7 W)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
      \u603b\u7ed3<\/h3>\n\n\n\n
      \u6811\u5f62DP\u662f\u52a8\u6001\u89c4\u5212\u7684\u91cd\u8981\u5206\u652f\uff0c\u5145\u5206\u5229\u7528\u4e86\u6811\u7684\u7ed3\u6784\u7279\u6027\uff1a<\/p>\n\n\n\n
      • \u65e0\u73af<\/strong>\uff1a\u786e\u4fdd DP \u7684\u65e0\u540e\u6548\u6027<\/li>
      • \u9012\u5f52\u7ed3\u6784<\/strong>\uff1a\u81ea\u7136\u5bf9\u5e94 DP \u7684\u9012\u5f52\u8ba1\u7b97<\/li>
      • \u7236\u5b50\u5173\u7cfb<\/strong>\uff1a\u6e05\u6670\u7684\u4f9d\u8d56\u65b9\u5411<\/li><\/ul>\n\n\n\n
        \u638c\u63e1\u6811\u5f62DP\u5bf9\u4e8e\u89e3\u51b3\u590d\u6742\u7684\u6811\u5f62\u95ee\u9898\uff08\u5982\u6811\u5f62\u533a\u95f4DP\u3001\u6811\u5f62\u72b6\u6001\u538b\u7f29DP\u7b49\uff09\u81f3\u5173\u91cd\u8981\uff0c\u4e5f\u662f\u7b97\u6cd5\u7ade\u8d5b\u4e2d\u4e0d\u53ef\u6216\u7f3a\u7684\u6280\u80fd\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
        \u4ec0\u4e48\u662f\u6811\u5f62DP\uff1f \u6811\u5f62\u52a8\u6001\u89c4\u5212\uff08Tree DP\uff09 \u662f\u5728\u6811\u5f62\u6570\u636e\u7ed3\u6784\u4e0a\u8fdb\u884c\u52a8\u6001\u89c4\u5212\u7684\u7279\u6b8a\u5f62\u5f0f\u3002\u7531\u4e8e\u6811\u6ca1\u6709\u73af\u72b6\u7ed3\u6784 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[65,53,66,64,62,63,61],"class_list":["post-43","post","type-post","status-publish","format-standard","hentry","category-3","tag-auto-child","tag-const-vector","tag-int-parent","tag-new-treenode","tag-state","tag-tree","tag-cdp"],"_links":{"self":[{"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/posts\/43","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/comments?post=43"}],"version-history":[{"count":1,"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/posts\/43\/revisions"}],"predecessor-version":[{"id":44,"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/posts\/43\/revisions\/44"}],"wp:attachment":[{"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/media?parent=43"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/categories?post=43"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/tags?post=43"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}