{"id":429,"date":"2020-05-02T17:01:11","date_gmt":"2020-05-02T09:01:11","guid":{"rendered":"http:\/\/www.zyhcoding.club\/?p=429"},"modified":"2020-05-14T15:56:06","modified_gmt":"2020-05-14T07:56:06","slug":"%e7%ae%80%e5%8d%95%e6%a0%91%e5%bd%a2dp%e9%a2%98%e7%9b%ae","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2020\/05\/02\/%e7%ae%80%e5%8d%95%e6%a0%91%e5%bd%a2dp%e9%a2%98%e7%9b%ae\/","title":{"rendered":"\u7b80\u5355\u6811\u5f62dp\u9898\u76ee"},"content":{"rendered":"

\u6d1b\u8c37P1352 \u6ca1\u6709\u4e0a\u53f8\u7684\u821e\u4f1a<\/a><\/h4>\n

\u6811\u4e0adp\u3002a[i]\u8868\u793a\u7ed3\u70b9i\u4e0d\u9009\u65f6\u7684\u6700\u4f18\u89e3\uff0cb[i]\u8868\u793a\u9009\u4e0a\u7ed3\u70b9i\u65f6\u7684\u6700\u4f18\u89e3\u3002a[i] = max(b[j],j\u4e3ai\u7684\u5b69\u5b50)\uff0cb[i] = max(a[j],j\u4e3ai\u7684\u5b69\u5b50).
\n\u8fd9\u9898\u7ed9\u51fa\u7684\u662f\u660e\u786e\u7684\u4e00\u9897\u6811\uff0c\u5373\u6709\u5411\u56fe\uff0c\u7236\u4eb2\uff0c\u5b69\u5b50\u7ed3\u70b9\u90fd\u662f\u660e\u786e\u7684\u3002<\/p>\n

\/\/#include <bits\/stdc++.h>\n#include <iostream>\n#include <algorithm>\n#include <vector>\nusing namespace std;\nconst int maxn = 6050;\nint w[maxn];\nvector<int> v[maxn];\nint a[maxn],b[maxn];      \/\/i \u4e0d\u6765  \u6765\nint vis[maxn],vis1[maxn],vis2[maxn];   \/\/vis1 \u4e0d\u6765   vis2 \u6765\nint dfs(int root,int flag);        \/\/flag=0\u8868\u793a\u6c42root\u4e0d\u6765\u7684\u6700\u5927\u503c   flag=1\u8868\u793a\u6c42root\u6765\u7684\u6700\u5927\u503c\nint main(){\n    \/\/std::ios::sync_with_stdio(false);\n    int n,k,l,root;\n    cin >> n;\n    for (int i=1;i<=n;i++)  cin >> w[i];\n    for (int i=1;i<n;i++){\n        cin >> l >> k;\n        v[k].push_back(l);\n        vis[l] = 1;\n    }\n    for (int i=1;i<=n;i++)  if (vis[i]==0){\n        root = i;\n        break;\n    }\n    \/\/int ans = max(dfs(root,1),dfs(root,0));\n    \/\/cout << ans;\n    cout << max(dfs(root,1),dfs(root,0));\n    return 0;\n}\nint dfs(int root,int flag){\n    if (flag){\n        if (vis2[root]) return b[root];\n        b[root] = w[root];\n        int len = v[root].size();\n        for (int i=0;i<len;i++)\n            b[root] += dfs(v[root][i],0);\n        vis2[root] = 1;\n        return b[root];\n    }else{\n        if (vis1[root]) return a[root];\n        int len = v[root].size();\n        for (int i=0;i<len;i++)\n            a[root] += max(dfs(v[root][i],0),dfs(v[root][i],1));\n        vis1[root] = 1;\n        return a[root];\n    }\n    return 0;\n}<\/code><\/pre>\n
\u6d1b\u8c37P1122 \u6700\u5927\u5b50\u6811\u548c<\/a><\/h4>\n
\u548c\u4e0a\u4e00\u9898\u4e0d\u540c\uff0c\u8fd9\u9898\u6ca1\u6709\u660e\u786e\u54ea\u4e2a\u662f\u7236\u6bcd\u7ed3\u70b9\uff0c\u54ea\u4e2a\u662f\u5b69\u5b50\u7ed3\u70b9\u3002
\nG\u5b58\u56fe\uff0ca\u5b58\u6743\u503c\uff0cans[i]\u8868\u793a\u7ed3\u70b9i\u9009\u4e0a\u65f6\u7684\u6700\u4f18\u89e3\uff0cans\u91cc\u7684\u6700\u5927\u503c\u5c31\u662f\u7b54\u6848\u3002
\n\u5982\u4f55\u89e3\u51b3\u7236\u4eb2\u5b69\u5b50\u7ed3\u70b9\u4e0d\u660e\u786e\u7684\u60c5\u51b5\uff1f\u7528vis\u6765\u6807\u8bb0\u4e00\u4e0b\uff0c\u5982\u679cvis[i]=1\uff0c\u90a3\u4e48\u8bf4\u660ei\u7ed3\u70b9\u5728\u8bbf\u95ee\u5f53\u524droot\u7ed3\u70b9\u4e4b\u524d\u5c31\u5df2\u7ecf\u8bbf\u95ee\u8fc7\u4e86\uff0ci\u4e0d\u53ef\u4ee5\u662froot\u7684\u5b69\u5b50\uff0c\u4e00\u5b9a\u662f\u7236\u6bcd\u7ed3\u70b9\uff0c\u5c31\u8fd9\u6837\uff0c\uff0c\uff0c\u3002<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nconst int maxn = 16500;\nint n,c,b;\nvector<int> G[maxn];\nint vis[maxn],a[maxn],ans[maxn],res;\nint dfs(int root){\n    vis[root] = 1;\n    int len = G[root].size();\n    ans[root] = a[root];\n    for (int i=0;i<len;i++) if (!vis[G[root][i]])\n        ans[root] = max(ans[root],ans[root]+dfs(G[root][i]));\n    res = max(res,ans[root]);\n    return ans[root];\n}\nint main(){\n    cin >> n;\n    for (int i=1;i<=n;i++)  cin >> a[i];\n    for (int i=1;i<n;i++){\n        cin >> c >> b;\n        G[c].push_back(b);\n        G[b].push_back(c);\n    }\n    dfs(1);\n    cout << res;\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u6d1b\u8c37P1352 \u6ca1\u6709\u4e0a\u53f8\u7684\u821e\u4f1a \u6811\u4e0adp\u3002a[i]\u8868\u793a\u7ed3\u70b9i\u4e0d\u9009\u65f6\u7684\u6700\u4f18\u89e3\uff0cb[i]\u8868\u793a\u9009\u4e0a\u7ed3\u70b9i\u65f6 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[42],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/429"}],"collection":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/comments?post=429"}],"version-history":[{"count":4,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/429\/revisions"}],"predecessor-version":[{"id":433,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/429\/revisions\/433"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=429"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=429"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=429"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}