{"id":2966,"date":"2023-06-02T10:43:40","date_gmt":"2023-06-02T02:43:40","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=2966"},"modified":"2023-06-02T19:03:40","modified_gmt":"2023-06-02T11:03:40","slug":"spoj-twopaths-two-paths","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/spoj-twopaths-two-paths\/","title":{"rendered":"SPOJ TWOPATHS. Two Paths"},"content":{"rendered":"<ul>\n<li><a href=\"https:\/\/www.spoj.com\/problems\/TWOPATHS\/\">https:\/\/www.spoj.com\/problems\/TWOPATHS\/<\/a><\/li>\n<li><a href=\"https:\/\/codeforces.com\/problemset\/problem\/14\/D\">https:\/\/codeforces.com\/problemset\/problem\/14\/D<\/a><\/li>\n<\/ul>\n<p>\u9898\u610f\uff1a\u6c42\u4e24\u6761\u4e0d\u76f8\u4ea4\u8def\u5f84\u7684\u79ef\u7684\u6700\u5927\u503c\u3002<\/p>\n<p>\u5206\u6790\uff1a<a href=\"https:\/\/www.shuizilong.com\/house\/archives\/dfs-%e5%ba%8f%e6%b1%82-lca\/\">dfs \u5e8f\u7ef4\u62a4\u76f4\u5f84<\/a> \u6709\u4e00\u4e2a\u975e\u5e38\u68d2\u7684\u6027\u8d28\u3002\u3002\u3002\u5c31\u662f\u53ef\u4ee5\u6c42\u5b50\u6811\u5185\u7684\u76f4\u5f84\u548c\u5b50\u6811\u5916\u7684\u76f4\u5f84\u3002\u3002\u6240\u4ee5\u6211\u4eec\u53ea\u8981\u518d dfs \u4e00\u6b21\uff0c\u7136\u540e\u6bcf\u6b21 query \u51fa\u6765\u4e24\u4e2a\u76f4\u5f84\u4e58\u4e00\u4e0b\u3002\u3002\u53ef\u60dc O(nlogn) \u4e5f\u8bb8\u8fc7\u4e0d\u4e86\u5927\u6570\u636e\u3002\u3002\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/io&gt;\r\nusing namespace lastweapon;\r\n\r\nconst int N = int(1e5) + 9;\r\n\r\nint L&#x5B;N], R&#x5B;N], dep&#x5B;N], id&#x5B;N], nn;\r\nVI adj&#x5B;N]; int n;\r\n\r\nstruct rec{\r\n    int d, dd, ld, rd, D;\r\n    void init(LL _d, LL _dd) {\r\n        d = _d; dd = 2*_dd;\r\n        D = ld = -INF; rd = _d - dd;\r\n    }\r\n} T&#x5B;N*4];\r\n\r\n\/\/ max d&#x5B;l] + d&#x5B;r] - dd&#x5B;m]\r\n\/\/ l &lt; m &lt;= r\r\n\/\/ d \u6df1\u5ea6\r\n\/\/ dd \u7236\u4eb2\u7684\u6df1\u5ea6\r\n\r\n#define lx (x&lt;&lt;1)\r\n#define rx (lx|1)\r\n#define ml ((l+r)&gt;&gt;1)\r\n#define mr (ml+1)\r\n#define lc lx,l,ml\r\n#define rc rx,mr,r\r\nvoid upd(int x) {\r\n    T&#x5B;x].d = max(T&#x5B;lx].d, T&#x5B;rx].d);\r\n    T&#x5B;x].dd = min(T&#x5B;lx].dd, T&#x5B;rx].dd);\r\n    T&#x5B;x].ld = max(T&#x5B;lx].ld, T&#x5B;rx].ld, T&#x5B;lx].d - T&#x5B;rx].dd);\r\n    T&#x5B;x].rd = max(T&#x5B;lx].rd, T&#x5B;rx].rd, T&#x5B;rx].d - T&#x5B;lx].dd);\r\n    T&#x5B;x].D = max(T&#x5B;lx].D, T&#x5B;rx].D, T&#x5B;lx].ld + T&#x5B;rx].d, T&#x5B;lx].d + T&#x5B;rx].rd);\r\n}\r\n\r\nrec upd(rec l, rec r) {\r\n    rec x;\r\n    x.d = max(l.d, r.d);\r\n    x.dd = min(l.dd, r.dd);\r\n    x.ld = max(l.ld, r.ld, l.d - r.dd);\r\n    x.rd = max(l.rd, r.rd, r.d - l.dd);\r\n    x.D = max(l.D, r.D, l.ld + r.d, l.d + r.rd);\r\n    return x;\r\n}\r\n\r\nvoid Build(int x, int l, int r) {\r\n    if (l == r) {\r\n        T&#x5B;x].init(dep&#x5B;id&#x5B;l]], dep&#x5B;id&#x5B;l]]-1);\r\n    } else {\r\n        Build(lc);\r\n        Build(rc);\r\n        upd(x);\r\n    }\r\n}\r\nvoid dfs(int u = 1, int p = 0) {\r\n    id&#x5B;L&#x5B;u] = ++nn] = u;\r\n    for (auto v: adj&#x5B;u]) if (v != p) {\r\n        dep&#x5B;v] = dep&#x5B;u] + 1;\r\n        dfs(v, u);\r\n    }\r\n    R&#x5B;u] = nn;\r\n}\r\n\r\nrec Query(int x, int l, int r, int a, int b) {\r\n    \/*if (b &lt; l || r &lt; a) {\r\n        rec x; x.init(-INF,INF);\r\n        return x;\r\n    }*\/\r\n    if (a &lt;= l &amp;&amp; r &lt;= b) {\r\n        return T&#x5B;x];\r\n    } else {\r\n\r\n        if (b &lt; mr) return Query(lc, a, b);\r\n        if (ml &lt; a) return Query(rc, a, b);\r\n        return upd(Query(lc, a, b), Query(rc, a, b));\r\n    }\r\n}\r\n\r\nLL z = 0;\r\nvoid gao(int u = 1, int p = 0) {\r\n    for (auto v: adj&#x5B;u]) if (v != p) {\r\n        LL D = Query(1,1,n,L&#x5B;v],R&#x5B;v]).D;\r\n        checkMax(z, D * upd(Query(1,1,n,1,L&#x5B;v]-1), Query(1,1,n,R&#x5B;v]+1,n)).D);\r\n\r\n        \/*cout &lt;&lt; L&#x5B;v] &lt;&lt; &quot; &quot; &lt;&lt; R&#x5B;v] &lt;&lt; &quot; &quot; &lt;&lt; v &lt;&lt; &quot; &quot; &lt;&lt; Query(1,1,n,L&#x5B;v],R&#x5B;v]).D &lt;&lt; &quot; &quot; &lt;&lt;\r\n         upd(Query(1,1,n,1,L&#x5B;v]-1), Query(1,1,n,R&#x5B;v]+1,n)).D\r\n         &lt;&lt; &quot; &quot; &lt;&lt; z &lt;&lt; endl;*\/\r\n        gao(v, u);\r\n    }\r\n}\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen(&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    dep&#x5B;0] = INF;\r\n\r\n    DO(RD(n)-1) {\r\n        int x, y; RD(x, y);\r\n        adj&#x5B;x].PB(y);\r\n        adj&#x5B;y].PB(x);\r\n    }\r\n\r\n    if (n &gt; 3) {\r\n        dfs(); Build(1, 1, n); gao();\r\n    }\r\n    cout &lt;&lt; z &lt;&lt; endl;\r\n}\r\n<\/pre>\n<p>\u6ca1\u529e\u6cd5\uff0c\u53ea\u80fd\u6362\u6839 dp \u4e86\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/io&gt;\r\nusing namespace lastweapon;\r\n\r\nconst int N = int(1e5) + 9;\r\n\r\nint dn&#x5B;N], up&#x5B;N]; \/\/ \u5b50\u6811\u5185\u76f4\u5f84\uff0c\u5b50\u6811\u5916\u76f4\u5f84\r\nint d&#x5B;N]&#x5B;3], e&#x5B;N]; \/\/ \u5b50\u6570\u5185 top3 \u6700\u957f\u8ddd\u79bb\uff0c\u5b50\u6811\u5916\u6700\u957f\u8ddd\u79bb\r\nVI adj&#x5B;N]; int n;\r\n\r\nvoid upd(int d&#x5B;], int v) {\r\n    if (v &gt; d&#x5B;0]) d&#x5B;2] = d&#x5B;1], d&#x5B;1] = d&#x5B;0], d&#x5B;0] = v;\r\n    else if (v &gt; d&#x5B;1]) d&#x5B;2] = d&#x5B;1], d&#x5B;1] = v;\r\n    else if (v &gt; d&#x5B;2]) d&#x5B;2] = v;\r\n}\r\n\r\nvoid dfs1(int u = 1, int p = 0) {\r\n    for (auto v: adj&#x5B;u]) if (v != p) {\r\n        dfs1(v, u);\r\n        upd(d&#x5B;u], d&#x5B;v]&#x5B;0] + 1);\r\n        checkMax(dn&#x5B;u], dn&#x5B;v]);\r\n    }\r\n    checkMax(dn&#x5B;u], d&#x5B;u]&#x5B;0] + d&#x5B;u]&#x5B;1]);\r\n}\r\n\r\nvoid dfs2(int u = 1, int p = 0) {\r\n    for (auto v: adj&#x5B;u]) if (v != p) {\r\n        checkMax(up&#x5B;v], up&#x5B;u]);\r\n        checkMax(e&#x5B;v], e&#x5B;u] + 1);\r\n        int t = d&#x5B;v]&#x5B;0] + 1;\r\n        if (d&#x5B;u]&#x5B;0] == t) {\r\n            checkMax(up&#x5B;v], d&#x5B;u]&#x5B;1] + d&#x5B;u]&#x5B;2]);\r\n            checkMax(up&#x5B;v], d&#x5B;u]&#x5B;1] + e&#x5B;u]);\r\n            checkMax(e&#x5B;v], d&#x5B;u]&#x5B;1] + 1);\r\n        }\r\n        else {\r\n            if (d&#x5B;u]&#x5B;1] == t) checkMax(up&#x5B;v], d&#x5B;u]&#x5B;0] + d&#x5B;u]&#x5B;2]);\r\n            else checkMax(up&#x5B;v], d&#x5B;u]&#x5B;0] + d&#x5B;u]&#x5B;1]);\r\n            checkMax(up&#x5B;v], d&#x5B;u]&#x5B;0] + e&#x5B;u]);\r\n            checkMax(e&#x5B;v], d&#x5B;u]&#x5B;0] + 1);\r\n        }\r\n        dfs2(v, u);\r\n    }\r\n}\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen(&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    DO(RD(n)-1) {\r\n        int x, y; RD(x, y);\r\n        adj&#x5B;x].PB(y);\r\n        adj&#x5B;y].PB(x);\r\n    }\r\n\r\n    dfs1(); dfs2();\r\n\r\n    LL z = 0; FOR_1(i, 2, n) checkMax(z, (LL)dn&#x5B;i] * up&#x5B;i]);\r\n    cout &lt;&lt; z &lt;&lt; endl;\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/www.spoj.com\/problems\/TWOPATHS\/ https:\/\/codeforces.com\/problemset\/problem\/14\/D \u9898\u610f\uff1a\u6c42\u4e24\u6761\u4e0d\u76f8\u4ea4\u8def\u5f84\u7684\u79ef\u7684\u6700\u5927\u503c\u3002 \u5206\u6790\uff1adfs \u5e8f\u7ef4\u62a4\u76f4\u5f84 \u6709\u4e00\u4e2a\u975e\u5e38\u68d2\u7684\u6027\u8d28\u3002\u3002\u3002\u5c31\u662f\u53ef\u4ee5\u6c42\u5b50\u6811\u5185\u7684\u76f4\u5f84\u548c\u5b50\u6811\u5916\u7684\u76f4\u5f84\u3002\u3002\u6240\u4ee5\u6211\u4eec\u53ea\u8981\u518d dfs \u4e00\u6b21\uff0c\u7136\u540e\u6bcf\u6b21 query \u51fa\u6765\u4e24\u4e2a\u76f4\u5f84\u4e58\u4e00\u4e0b\u3002\u3002\u53ef\u60dc O(nlogn) \u4e5f\u8bb8\u8fc7\u4e0d\u4e86\u5927\u6570\u636e\u3002\u3002\u3002 #include &lt;lastweapon\/io&gt; using namespace lastweapon; const int N = int(1e5) + 9; int L&#x5B;N], R&#x5B;N], dep&#x5B;N], id&#x5B;N], nn; VI adj&#x5B;N]; int n; struct rec{ int d, dd, ld, rd, D; void init(LL _d, LL _dd) { d = _d; dd = 2*_dd; D [&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":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-2966","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-LQ","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2966","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=2966"}],"version-history":[{"count":5,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2966\/revisions"}],"predecessor-version":[{"id":2971,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2966\/revisions\/2971"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=2966"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=2966"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=2966"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}