{"id":1313,"date":"2016-08-26T13:30:58","date_gmt":"2016-08-26T05:30:58","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1313"},"modified":"2023-06-06T00:17:58","modified_gmt":"2023-06-05T16:17:58","slug":"tree-dp","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/tree-dp\/","title":{"rendered":"\u6811\u5f62 DP"},"content":{"rendered":"<ul>\n<li>\u76f4\u5f84<\/li>\n<li>\u70b9\u8986\u76d6\u96c6<\/li>\n<li>\u8def\u5f84\u8986\u76d6<\/li>\n<li>\u652f\u914d\u96c6<\/li>\n<\/ul>\n<p>\u96be\u5ea6\uff1a2<br \/>\n\u524d\u63d0\uff1a<a href=\"https:\/\/www.shuizilong.com\/house\/archives\/dynamic-programming\/\">\u52a8\u6001\u89c4\u5212<\/a><br \/>\n\u540e\u7ee7\uff1a<\/p>\n<h3>\u8d44\u6599\uff1a<\/h3>\n<ul>\n<li><a href=\"http:\/\/pan.baidu.com\/s\/1mi8QFBa\" target=\"_blank\" rel=\"noopener\">&#8230;<\/a><\/li>\n<\/ul>\n<ul>\n<li>\n<p><a href=\"https:\/\/cses.fi\/problemset\/task\/1133\">https:\/\/cses.fi\/problemset\/task\/1133<\/a><\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/io&gt;\r\n\r\nusing namespace lastweapon;\r\n\r\nconst int N = int(2e5) + 9;\r\n\r\nint n, h&#x5B;N]; LL f&#x5B;N], g&#x5B;N];\r\nVVI v;\r\n\r\nvoid dfs1(int r, int p = -1) {\r\n    for(int&amp; a : v&#x5B;r]) if (a != p) {\r\n        dfs1(a, r);\r\n        h&#x5B;r] += h&#x5B;a];\r\n        f&#x5B;r] += f&#x5B;a] + h&#x5B;a];\r\n    }\r\n    h&#x5B;r]++;\r\n}\r\n\r\nvoid dfs2(int r, int p = -1) {\r\n    for(int&amp; a : v&#x5B;r]) if (a != p) {\r\n        g&#x5B;a] = (f&#x5B;r] - (f&#x5B;a] + h&#x5B;a])) + g&#x5B;r] + (n - h&#x5B;a]);\r\n        dfs2(a, r);\r\n    }\r\n}\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\nfreopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n\/\/freopen(&quot;\/Users\/minakokojima\/Documents\/GitHub\/ACM-Training\/Workspace\/out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    RD(n);\r\n    v.resize(n);\r\n    int a, b;\r\n    while(cin &gt;&gt; a &gt;&gt; b) {\r\n        v&#x5B;a-1].PB(b-1);\r\n        v&#x5B;b-1].PB(a-1);\r\n    }\r\n    dfs1(0);\r\n    dfs2(0);\r\n    REP(i, n) printf(&quot;%lld &quot;, f&#x5B;i] + g&#x5B;i]);\r\n}\r\n\r\n<\/pre>\n<\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/usaco.guide\/problems\/ac-subtree\/solution\">https:\/\/usaco.guide\/problems\/ac-subtree\/solution<\/a><\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/io&gt;\r\n#include &lt;lastweapon\/number&gt;\r\n\r\nusing namespace lastweapon;\r\n\r\nconst int N = int(1e5) + 9;\r\n\r\nVI adj&#x5B;N]; Int f&#x5B;N], fl&#x5B;N], fr&#x5B;N], g&#x5B;N];\r\nint n;\r\n\r\nvoid dfs1(int u = 0, int p = -1) {\r\n    f&#x5B;u] = 1;\r\n    for(auto&amp; v: adj&#x5B;u]) if (v != p) {\r\n        dfs1(v, u);\r\n        fl&#x5B;v] = f&#x5B;u];\r\n        f&#x5B;u] *= f&#x5B;v] + 1;\r\n    }\r\n    f&#x5B;u] = 1;\r\n    for (auto it = adj&#x5B;u].rbegin(); it != adj&#x5B;u].rend(); ++it) {\r\n        int v = *it; if (v == p) continue;\r\n        fr&#x5B;v] = f&#x5B;u];\r\n        f&#x5B;u] *= f&#x5B;v] + 1;\r\n    }\r\n}\r\n\r\nvoid dfs2(int u = 0, int p = -1) {\r\n    for(auto&amp; v: adj&#x5B;u]) if (v != p) {\r\n        g&#x5B;v] = (g&#x5B;u] + 1) * fl&#x5B;v] * fr&#x5B;v]; \/\/f&#x5B;u] \/ (f&#x5B;v] + 1);\r\n        dfs2(v, u);\r\n    }\r\n}\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\nfreopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n\/\/freopen(&quot;\/Users\/minakokojima\/Documents\/GitHub\/ACM-Training\/Workspace\/out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    RD(n, MOD); DO(n - 1) {\r\n        int a, b; RD(a, b); --a; --b;\r\n        adj&#x5B;a].PB(b);\r\n        adj&#x5B;b].PB(a);\r\n    }\r\n\r\n    dfs1(); dfs2();\r\n\r\n    REP(i, n) printf(&quot;%d\\n&quot;, f&#x5B;i] * (g&#x5B;i] + 1));\r\n}\r\n\r\n<\/pre>\n<\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/codeforces.com\/contest\/1187\/problem\/E\">https:\/\/codeforces.com\/contest\/1187\/problem\/E<\/a><\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n<\/pre>\n<\/p>\n<\/li>\n<\/ul>\n<h3>\u4e60\u9898\uff1a<\/h3>\n<ul>\n<li><a href=\"http:\/\/acm.hust.edu.cn\/vjudge\/problem\/23736\">SPOJ PT07Z. Longest path in a tree<\/a> \u6811\u7684\u76f4\u5f84<\/li>\n<li><a href=\"http:\/\/codeforces.com\/contest\/708\/problem\/C\">Codeforces Round AIM Tech Round 3 Problem C. Centroids<\/a><\/li>\n<li><a href=\"http:\/\/acm.hust.edu.cn\/vjudge\/problem\/18067\">HDU 2196.\u00a0Computer<\/a><\/li>\n<li><a href=\"http:\/\/acm.hust.edu.cn\/vjudge\/problem\/463352\">HDU 5834.\u00a0Magic boy Bi Luo with his excited tree<\/a><\/li>\n<li><a href=\"http:\/\/user.qzone.qq.com\/251815992\/blog\/1410720943\">http:\/\/user.qzone.qq.com\/251815992\/blog\/1410720943<\/a><\/li>\n<li><a href=\"http:\/\/acm.hust.edu.cn\/vjudge\/problem\/259937\">2014-2015 ACM-ICPC, Asia Mudanjiang Regional Contest, Problem F. Fiber-optic Network<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>\u76f4\u5f84 \u70b9\u8986\u76d6\u96c6 \u8def\u5f84\u8986\u76d6 \u652f\u914d\u96c6 \u96be\u5ea6\uff1a2 \u524d\u63d0\uff1a\u52a8\u6001\u89c4\u5212 \u540e\u7ee7\uff1a \u8d44\u6599\uff1a &#8230; https:\/\/cses.fi\/problemset\/task\/1133 #include &lt;lastweapon\/io&gt; using namespace lastweapon; const int N = int(2e5) + 9; int n, h&#x5B;N]; LL f&#x5B;N], g&#x5B;N]; VVI v; void dfs1(int r, int p = -1) { for(int&amp; a : v&#x5B;r]) if (a != p) { dfs1(a, r); h&#x5B;r] += h&#x5B;a]; f&#x5B;r] += f&#x5B;a] [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[169],"tags":[],"class_list":["post-1313","post","type-post","status-publish","format-standard","hentry","category-169"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-lb","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1313","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=1313"}],"version-history":[{"count":5,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1313\/revisions"}],"predecessor-version":[{"id":2983,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1313\/revisions\/2983"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1313"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1313"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1313"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}