{"id":2172,"date":"2023-01-18T03:49:34","date_gmt":"2023-01-17T19:49:34","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=2172"},"modified":"2024-05-03T19:33:52","modified_gmt":"2024-05-03T11:33:52","slug":"dfs-%e5%ba%8f%e6%b1%82-lca","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/dfs-%e5%ba%8f%e6%b1%82-lca\/","title":{"rendered":"dfs \u5e8f\u6c42 lca"},"content":{"rendered":"<h2><span class=\"ez-toc-section\" id=\"%E5%89%8D%E6%83%85%E6%8F%90%E8%A6%81\"><\/span>\u524d\u60c5\u63d0\u8981<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u524d\u51e0\u5929\u505a\u4e86\u4e00\u4e0b Educational Codeforces Round 141 \u7684 F \u9898\u3002\u3002\u3002\u770b\u8d77\u6765\u662f\u4e2a\u52a8\u6001\u76f4\u5f84\uff0c<a href=\"https:\/\/vjudge.net\/problem\/%E8%AE%A1%E8%92%9C%E5%AE%A2-41398\">\u4e4b\u524d\u7f51\u8d5b\u6211\u51fa\u8fc7\u4e00\u6b21<\/a>\uff0c\u7ffb\u51fa\u6807\u7a0b\u5e94\u8be5\u80fd\u79d2\u3002\u4f46\u662f\u5199\u8d77\u6765\u53d1\u73b0\u8981\u6539\u7684\u5730\u65b9\u5b9e\u5728\u5f88\u591a\uff0c\u5927\u6982\u662f\u6211\u7684\u6807\u7a0b\u5b9e\u5728\u4e0d\u600e\u4e48\u9ad8\u660e\u3002<\/p>\n<p>\u4e8e\u662f\u770b\u4e86\u4e00\u4e0b\u4ee3\u7801\u6700\u77ed\u7684\u5bb6\u4f19\u4eec\u90fd\u5199\u4e86\u5565\uff0c\u4e8e\u662f\u6211\u88ab <a href=\"https:\/\/codeforces.com\/contest\/1783\/submission\/188649176\">\u8fd9\u4efd\u4ee3\u7801<\/a> \u9707\u60ca\u4e86\u3002<\/p>\n<p>\u7b2c\u4e00\u53cd\u5e94\u662f\uff0c\u867d\u7136\u8f6c\u79fb\u6211\u770b\u4e0d\u61c2\uff0c\u4f46\u662f\u5e94\u8be5\u5c31\u662f\u4e00\u9897 zkw \u6811\uff0c\u7b49\u4ef7\u4e8e <a href=\"https:\/\/www.cnblogs.com\/TinyWong\/p\/11260601.html\">\u8fd9\u7bc7\u6587\u7ae0\u91cc\u6240\u63d0\u5230\u7684\u7b97\u6cd5\u4e09<\/a> \u561b\u3002\u3002\u3002<br \/>\n&#8230;but wait, \u4f60\u7684 lca \u5728\u54ea\u91cc\u3002\u3002\u3002<\/p>\n<p>\u4e4b\u524d Dynamic Diameter \u91cc\u6211\u4eec\u662f\u5728 euler \u5e8f\u4e0a\u5efa\u7ebf\u6bb5\u6811\u3002\u3002\u3002\u5b9e\u9645\u4e0a\u662f\u9690\u542b\u4e86\u4e00\u4e2a\u6c42 lca \u7684\u8fc7\u7a0b\u7684\u3002\u3002\u3002<br \/>\n\u4f46\u662f\u8fd9\u91cc\u660e\u663e\u662f dfs \u5e8f\u5427\u3002\u3002\u3002\u3002\u3002\u3002<\/p>\n<p>\u307e\u3055\u304b\uff1f&#8230;<\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_65 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<p class=\"ez-toc-title\">Table of Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-69e4af2a22c44\" class=\"ez-toc-cssicon-toggle-label\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-69e4af2a22c44\"  aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/dfs-%e5%ba%8f%e6%b1%82-lca\/#%E5%89%8D%E6%83%85%E6%8F%90%E8%A6%81\" title=\"\u524d\u60c5\u63d0\u8981\">\u524d\u60c5\u63d0\u8981<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/dfs-%e5%ba%8f%e6%b1%82-lca\/#LCA\" title=\"LCA\">LCA<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/dfs-%e5%ba%8f%e6%b1%82-lca\/#Luogu_P3379_%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88%EF%BC%88LCA%EF%BC%89\" title=\"Luogu. P3379 \u3010\u6a21\u677f\u3011\u6700\u8fd1\u516c\u5171\u7956\u5148\uff08LCA\uff09\">Luogu. P3379 \u3010\u6a21\u677f\u3011\u6700\u8fd1\u516c\u5171\u7956\u5148\uff08LCA\uff09<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/dfs-%e5%ba%8f%e6%b1%82-lca\/#BZOJ_2819_Nim\" title=\"BZOJ 2819. Nim\">BZOJ 2819. Nim<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/dfs-%e5%ba%8f%e6%b1%82-lca\/#Codeforces_Round_520_Problem_E_Company\" title=\"Codeforces Round #520, Problem E. Company\">Codeforces Round #520, Problem E. Company<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/dfs-%e5%ba%8f%e6%b1%82-lca\/#%E7%9B%B4%E5%BE%84\" title=\"\u76f4\u5f84\">\u76f4\u5f84<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/dfs-%e5%ba%8f%e6%b1%82-lca\/#SPOJ_PT07Z_Longest_path_in_a_tree\" title=\"SPOJ PT07Z. Longest path in a tree\">SPOJ PT07Z. Longest path in a tree<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/dfs-%e5%ba%8f%e6%b1%82-lca\/#CEOI_2019_day_1_B_Dynamic_Diameter\" title=\"CEOI 2019 day 1 B. Dynamic Diameter\">CEOI 2019 day 1 B. Dynamic Diameter<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/dfs-%e5%ba%8f%e6%b1%82-lca\/#2019_ICPC_%E4%B8%8A%E6%B5%B7%E8%B5%9B%E5%8C%BA%E7%BD%91%E7%BB%9C%E8%B5%9B_Problem_A_Lightning_Routing_I\" title=\"2019 ICPC \u4e0a\u6d77\u8d5b\u533a\u7f51\u7edc\u8d5b Problem A. Lightning Routing I\">2019 ICPC \u4e0a\u6d77\u8d5b\u533a\u7f51\u7edc\u8d5b Problem A. Lightning Routing I<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/dfs-%e5%ba%8f%e6%b1%82-lca\/#Educational_Codeforces_Round_141_Problem_G_Weighed_Tree_Radius\" title=\"Educational Codeforces Round 141, Problem G. Weighed Tree Radius\">Educational Codeforces Round 141, Problem G. Weighed Tree Radius<\/a><\/li><\/ul><\/li><\/ul><\/nav><\/div>\n\n<h2><span class=\"ez-toc-section\" id=\"LCA\"><\/span>LCA<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>dfs \u5e8f\u4e5f\u53ef\u4ee5\u6c42 lca\uff1f<\/p>\n<p>\u641c\u4e86\u4e00\u4e0b\uff0c<a href=\"https:\/\/www.luogu.com.cn\/blog\/AlexWei\/leng-men-ke-ji-dfs-xu-qiu-lca\">\u539f\u6765\u8fd8\u771f\u6709<\/a>\uff01<br \/>\n\u6838\u5fc3\u601d\u60f3\uff1a\u867d\u7136 lca \u81ea\u5df1\u4e0d\u4f1a\u51fa\u73b0\u5728\u533a\u95f4\u91cc\u3002\u3002\u4f46\u662f\u4f60\u7684\u5b69\u5b50\u4f1a\u554a\u3002\u3002\u3002\u627e\u5230\u8fd9\u4e2a\u70b9\u518d\u6c42\u7236\u4eb2\uff0c\u6216\u8005\uff0c\u76f4\u63a5\u5728\u5efa st \u8868\u7684\u65f6\u5019\u5c31\u76f4\u63a5\u653e\u7236\u7ed3\u70b9\u5c31\u884c\u4e86\uff01<br \/>\n\u597d\u5427\u3002\u3002\u53cd\u6b63\u6211\u662f\u60f3\u4e0d\u5230\u3002\u3002\u56e7\u3002\u3002<\/p>\n<p>\u8fd9\u4e2a\u677f\u5b50\u663e\u7136\u5404\u65b9\u9762\u90fd\u662f\u5b8c\u80dc euler \u5e8f lca \u7684\u3002\u3002\u3002\u7279\u522b\u662f\u6709\u7684\u9898\u91cc\u540c\u65f6\u51fa\u73b0 dfs \u5e8f\u548c lca \u7684\u65f6\u5019 \u2014\u2014 \u5988\u5988\u518d\u4e5f\u4e0d\u7528\u62c5\u5fc3\u641e\u4e0d\u6e05\u65f6\u95f4\u6233\u54ea\u4e2a\u5bf9\u54ea\u4e2a\u4e86\u3002\u3002\u3002<\/p>\n<p>\u627e\u70b9\u4f8b\u9898\u7ec3\u4e60\u4e00\u4e0b\u5427\u3002\u3002<\/p>\n<h3><span class=\"ez-toc-section\" id=\"Luogu_P3379_%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88%EF%BC%88LCA%EF%BC%89\"><\/span>Luogu. P3379 \u3010\u6a21\u677f\u3011\u6700\u8fd1\u516c\u5171\u7956\u5148\uff08LCA\uff09<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/P3379\">https:\/\/www.luogu.com.cn\/problem\/P3379<\/a><\/li>\n<\/ul>\n<pre class=\"brush: cpp; light: false; title: \u500d\u589e\u7956\u5148; toolbar: true; notranslate\" title=\"\u500d\u589e\u7956\u5148\">\n#include &amp;lt;lastweapon\/bitwise&amp;gt;\nusing namespace lastweapon;\nconst int N = int(5e5) + 9, LV = 20;\nint fa&#x5B;LV]&#x5B;N], dep&#x5B;N];\nVI adj&#x5B;N]; int n;\n\nint move_up(int x, int d) {\n    for (int lv=0;d;++lv,d&amp;gt;&amp;gt;=1)\n        if (d&amp;amp;1) x = fa&#x5B;lv]&#x5B;x];\n    return x;\n}\n\ninline int lca(int x, int y) {\n    if (dep&#x5B;y] &amp;lt; dep&#x5B;x]) swap(x, y); y = move_up(y, dep&#x5B;y] - dep&#x5B;x]); if (x == y) return x;\n    DWN(lv, LV, 0) if (fa&#x5B;lv]&#x5B;x] != fa&#x5B;lv]&#x5B;y]) x = fa&#x5B;lv]&#x5B;x], y = fa&#x5B;lv]&#x5B;y];\n    return fa&#x5B;0]&#x5B;x];\n}\nvoid dfs(int u = 1, int p = 0) {\n    for (auto v: adj&#x5B;u]) if (v != p) {\n        dep&#x5B;v] = dep&#x5B;u] + 1;\n        fa&#x5B;0]&#x5B;v] = u; for (int lv=0;fa&#x5B;lv+1]&#x5B;v]=fa&#x5B;lv]&#x5B;fa&#x5B;lv]&#x5B;v]];++lv);\n        dfs(v, u);\n    }\n}\n\nint main() {\n\n#ifndef ONLINE_JUDGE\n    freopen(&amp;quot;in.txt&amp;quot;, &amp;quot;r&amp;quot;, stdin);\n#endif\n\n&lt;pre&gt;&lt;code&gt;int m, s; RD(n, m, s);\n\nDO(n-1) {\n    int x, y; RD(x, y);\n    adj&#x5B;x].PB(y);\n    adj&#x5B;y].PB(x);\n}\n\ndfs(s);\n\nDO(m) {\n    int a, b; RD(a, b);\n    printf(&amp;amp;quot;%d\\n&amp;amp;quot;, lca(a, b));\n}\n&lt;\/code&gt;&lt;\/pre&gt;\n\n}\n\n<\/pre>\n<pre class=\"brush: cpp; light: false; title: Sparse Table; toolbar: true; notranslate\" title=\"Sparse Table\">\n#include &amp;lt;lastweapon\/bitwise&amp;gt;\nusing namespace lastweapon;\nconst int N = int(5e5) + 9, LM = 19;\nint dfn&#x5B;N], ST&#x5B;LM]&#x5B;N], dep&#x5B;N], nn;\nVI adj&#x5B;N]; int n;\n\ninline bool cmp(int a, int b) {\n    return dep&#x5B;a] &amp;lt; dep&#x5B;b];\n}\ninline int lca(int a, int b) {\n    if (a == b) return a;\n    int l = dfn&#x5B;a], r = dfn&#x5B;b];\n    if (l &amp;gt; r) swap(l, r); int lv = lg2(r-l++);\n    return min(ST&#x5B;lv]&#x5B;l], ST&#x5B;lv]&#x5B;r-(1&amp;lt;&amp;lt;lv)+1], cmp);\n}\nvoid dfs(int u = 1, int p = 0) {\n    ST&#x5B;0]&#x5B;dfn&#x5B;u] = ++nn] = p;\n    for (auto v: adj&#x5B;u]) if (v != p) {\n        dep&#x5B;v] = dep&#x5B;u] + 1;\n        dfs(v, u);\n    }\n}\nvoid init_rmq() {\n    for ( int lv = 1 ; _1(lv) &amp;lt;= nn ; lv ++ ) {\n        for ( int i = 1 ; i + _1(lv)  &amp;lt;= nn + 1 ; i ++ ) {\n            ST&#x5B;lv]&#x5B;i] = min(ST&#x5B;lv-1]&#x5B;i], ST&#x5B;lv-1]&#x5B;i + _1(lv-1)], cmp);\n        }\n    }\n}\n\nint main() {\n\n#ifndef ONLINE_JUDGE\n    freopen(&amp;quot;in.txt&amp;quot;, &amp;quot;r&amp;quot;, stdin);\n    \/\/freopen(&amp;quot;\/Users\/minakokojima\/Documents\/GitHub\/ACM-Training\/Workspace\/out.txt&amp;quot;, &amp;quot;w&amp;quot;, stdout);\n#endif\n\n&lt;pre&gt;&lt;code&gt;int m, s; RD(n, m, s);\n\nDO(n-1) {\n    int x, y; RD(x, y);\n    adj&#x5B;x].PB(y);\n    adj&#x5B;y].PB(x);\n}\n\ndfs(s); init_rmq();\n\nDO(m) {\n    int a, b; RD(a, b);\n    printf(&amp;amp;quot;%d\\n&amp;amp;quot;, lca(a, b));\n}\n&lt;\/code&gt;&lt;\/pre&gt;\n\n}\n<\/pre>\n<pre class=\"brush: cpp; light: false; title: Segment Tree; toolbar: true; notranslate\" title=\"Segment Tree\">\n#include &amp;lt;lastweapon\/bitwise&amp;gt;\nconst int N = int(5e5) + 9;\nint A&#x5B;N], T&#x5B;4*N];\nint dfn&#x5B;N], dep&#x5B;N], nn;\nVI adj&#x5B;N]; int n;\n\n#define lx (x&amp;lt;&amp;lt;1)\n#define rx (lx|1)\n#define ml ((l+r)&amp;gt;&amp;gt;1)\n#define mr (ml+1)\n#define lc lx,l,ml\n#define rc rx,mr,r\n\nbool cmp(int a, int b) {\n    return dep&#x5B;a] &amp;lt; dep&#x5B;b];\n}\nvoid upd(int x) {\n    T&#x5B;x] = min(T&#x5B;lx], T&#x5B;rx], cmp);\n}\nvoid Build(int x, int l, int r) {\n    if (l == r) {\n        T&#x5B;x] = A&#x5B;l];\n    } else {\n        Build(lc);\n        Build(rc);\n        upd(x);\n    }\n}\nint Query(int x, int l, int r, const int a, const int b) {\n    if (b &amp;lt; l || r &amp;lt; a) return 0;\n    if (a &amp;lt;= l &amp;amp;&amp;amp; r &amp;lt;= b) {\n        return T&#x5B;x];\n    } else {\n        return min(Query(lc, a, b), Query(rc, a, b), cmp);\n    }\n}\nint lca(int a, int b) {\n    if (a == b) return a;\n    a = dfn&#x5B;a]; b = dfn&#x5B;b]; if (a &amp;gt; b) swap(a, b); ++a;\n    return Query(1, 1, n, a, b);\n}\n\nvoid dfs(int u = 1, int p = 0) {\n    A&#x5B;dfn&#x5B;u] = ++nn] = p;\n    for (auto v: adj&#x5B;u]) if (v != p) {\n        dep&#x5B;v] = dep&#x5B;u] + 1;\n        dfs(v, u);\n    }\n}\n\nint main() {\n\n#ifndef ONLINE_JUDGE\n    freopen(&amp;quot;in.txt&amp;quot;, &amp;quot;r&amp;quot;, stdin);\n    \/\/freopen(&amp;quot;\/Users\/minakokojima\/Documents\/GitHub\/ACM-Training\/Workspace\/out.txt&amp;quot;, &amp;quot;w&amp;quot;, stdout);\n#endif\n\n&lt;pre&gt;&lt;code&gt;dep&#x5B;0] = INF;\n\nint m, s; RD(n, m, s);\n\nDO(n-1) {\n    int x, y; RD(x, y);\n    adj&#x5B;x].PB(y);\n    adj&#x5B;y].PB(x);\n}\n\ndfs(s); Build(1, 1, n);\n\nDO(m) {\n    int a, b; RD(a, b);\n    printf(&amp;amp;quot;%d\\n&amp;amp;quot;, lca(a, b));\n}\n&lt;\/code&gt;&lt;\/pre&gt;\n\n}\n<\/pre>\n<h3><span class=\"ez-toc-section\" id=\"BZOJ_2819_Nim\"><\/span>BZOJ 2819. Nim<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li><a href=\"https:\/\/darkbzoj.cc\/problem\/2819\">https:\/\/darkbzoj.cc\/problem\/2819<\/a><br \/>\n\u3002\u3002\u3002\u9996\u5148\u8fd9\u4e2a\u9898\u8fd8\u5fc5\u987b\u5f97\u7528\u6211\u4eec\u65b0\u5b66\u4f1a\u7684\u62db\u5f0f\u3002\u3002\u56e0\u4e3a euler \u5e8f\u6070\u597d\u88ab\u5361\u5185\u5b58\u3002\u3002\u3002\uff08\u602a\u4e0d\u5f97\u5927\u5bb6\u90fd\u53ea\u5199\u500d\u589e\u548c\u6811\u5256\u3002\u3002\uff09<\/li>\n<\/ul>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\n#include &amp;lt;lastweapon\/bitwise&amp;gt;\nusing namespace lastweapon;\nconst int N = int(5e5) + 9, LM = 19;\nint W&#x5B;N], L&#x5B;N], R&#x5B;N], ST&#x5B;LM]&#x5B;N], dep&#x5B;N], nn;\nVI adj&#x5B;N]; int n; int fa&#x5B;N];\n\nnamespace BIT{\n    int C&#x5B;N];\n    int Sum(int x){\n        int z=0; for (;x;x^=low_bit(x)) z ^= C&#x5B;x];\n        return z;\n    }\n    void Xor(int x, int w){\n        for(;x&amp;lt;=n;x+=low_bit(x)) C&#x5B;x] ^= w;\n    }\n} using namespace BIT;\n\ninline bool elder(int a, int b) {\n    return dep&#x5B;a] &amp;lt; dep&#x5B;b];\n}\n\ninline int lca(int a, int b) {\n    if (a == b) return a;\n    int l = L&#x5B;a], r = L&#x5B;b];\n    if (l &amp;gt; r) swap(l, r); int lv = lg2(r-l++);\n    return min(ST&#x5B;lv]&#x5B;l], ST&#x5B;lv]&#x5B;r-(1&amp;lt;&amp;lt;lv)+1], elder);\n}\n\nvoid upd(int u, int w) {\n    Xor(L&#x5B;u], w);\n    Xor(R&#x5B;u]+1, w);\n}\n\nvoid dfs(int u = 1, int p = -1) {\n    ST&#x5B;0]&#x5B;L&#x5B;u] = ++nn] = p;\n    for (auto v: adj&#x5B;u]) if (v != p) {\n        dep&#x5B;v] = dep&#x5B;u] + 1;\n        dfs(v, u);\n    }\n    R&#x5B;u] = nn;\n    upd(u, W&#x5B;u]);\n}\n\nint main() {\n\n#ifndef ONLINE_JUDGE\n    freopen(&amp;quot;in.txt&amp;quot;, &amp;quot;r&amp;quot;, stdin);\n    \/\/freopen(&amp;quot;\/Users\/minakokojima\/Documents\/GitHub\/ACM-Training\/Workspace\/out.txt&amp;quot;, &amp;quot;w&amp;quot;, stdout);\n#endif\n\n&lt;pre&gt;&lt;code&gt;RD(n); REP_1(i, n) RD(W&#x5B;i]); DO(n-1) {\n    int a, b; RD(a, b);\n    adj&#x5B;a].PB(b);\n    adj&#x5B;b].PB(a);\n}\n\ndfs();\n\nfor ( int lv = 1 ; _1(lv) &amp;amp;lt;= nn ; lv ++ ){\n    for ( int i = 1 ; i + _1(lv)  &amp;amp;lt;= nn + 1 ; i ++ )\n        ST&#x5B;lv]&#x5B;i] = min(ST&#x5B;lv-1]&#x5B;i], ST&#x5B;lv-1]&#x5B;i + _1(lv-1)], elder);\n}\n\nRush {\n    if (RC() == &amp;amp;#039;Q&amp;amp;#039;) {\n        int a, b; RD(a, b);\n        puts(Sum(L&#x5B;a])^Sum(L&#x5B;b])^W&#x5B;lca(a, b)] ? &amp;amp;quot;Yes&amp;amp;quot; : &amp;amp;quot;No&amp;amp;quot;);\n    } else {\n        int u, w; RD(u, w);\n        upd(u, W&#x5B;u]^w);\n        W&#x5B;u] = w;\n    }\n}\n&lt;\/code&gt;&lt;\/pre&gt;\n\n}\n\n<\/pre>\n<h3><span class=\"ez-toc-section\" id=\"Codeforces_Round_520_Problem_E_Company\"><\/span>Codeforces Round #520, Problem E. Company<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li><a href=\"https:\/\/codeforces.com\/contest\/1062\/problem\/E\">https:\/\/codeforces.com\/contest\/1062\/problem\/E<\/a><br \/>\n\u4e00\u5806\u7ed3\u70b9\u7684 lca \u662f dfs \u5e8f\u91cc\u6700\u5de6\u548c\u6700\u53f3\u4e24\u4e2a\u7ed3\u70b9\u7684 lca\uff08\u8fd9\u4e2a\u7ed3\u8bba\u5efa\u865a\u6811\u7684\u65f6\u5019\u4f1a\u7528\uff09\u3002<br \/>\n\u56e0\u800c\u8fd8\u9700\u8981\u5bf9\u4ee5\u7ed3\u70b9\u4e3a\u4e0b\u6807\uff0c\u4ee5 <code>cmp_by_dfn<\/code> \u4e3a\u6bd4\u8f83\u51fd\u6570\uff0c\u518d\u5206\u522b\u5efa\u4e24\u7ec4 st \u8868\uff0c\u52a0\u4e0a lca \u81ea\u5df1\u7684 st \u8868\u4e00\u5171\u6709 3 \u7ec4\u3002<br \/>\n\u8be2\u95ee\u7684\u65f6\u5019\u8ba8\u8bba\u4e00\u4e0b\u5220\u5de6\u8fd8\u662f\u5220\u53f3\u5373\u53ef\u3002<\/li>\n<\/ul>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\n#include &amp;lt;lastweapon\/bitwise&amp;gt;\nusing namespace lastweapon;\nconst int N = int(1e5) + 9, LM = 19;\nint dfn&#x5B;N], ST&#x5B;LM]&#x5B;N], dep&#x5B;N], nn;\nint st&#x5B;LM]&#x5B;N], ts&#x5B;LM]&#x5B;N];\nVI adj&#x5B;N]; int n;\n\ninline bool cmp_by_dep(int a, int b) {\n    return dep&#x5B;a] &amp;lt; dep&#x5B;b];\n}\ninline bool cmp_by_dfn(int a, int b) {\n    return dfn&#x5B;a] &amp;lt; dfn&#x5B;b];\n}\ninline int lca(int a, int b) {\n    if (a == b) return a;\n    int l = dfn&#x5B;a], r = dfn&#x5B;b];\n    if (l &amp;gt; r) swap(l, r); int lv = lg2(r-l++);\n    return min(ST&#x5B;lv]&#x5B;l], ST&#x5B;lv]&#x5B;r-(1&amp;lt;&amp;lt;lv)+1], cmp_by_dep);\n}\ninline int mn(int l, int r) {\n    int lv = lg2(r-l+1);\n    return min(st&#x5B;lv]&#x5B;l], st&#x5B;lv]&#x5B;r-(1&amp;lt;&amp;lt;lv)+1], cmp_by_dfn);\n}\ninline int mx(int l, int r) {\n    int lv = lg2(r-l+1);\n    return max(ts&#x5B;lv]&#x5B;l], ts&#x5B;lv]&#x5B;r-(1&amp;lt;&amp;lt;lv)+1], cmp_by_dfn);\n}\n\nvoid dfs(int u = 1, int p = 0) {\n    ST&#x5B;0]&#x5B;dfn&#x5B;u] = ++nn] = p;\n    for (auto v: adj&#x5B;u]) {\n        dep&#x5B;v] = dep&#x5B;u] + 1;\n        dfs(v, u);\n    }\n}\n\nvoid init_rmq() {\n    REP_1(i, n) st&#x5B;0]&#x5B;i] = ts&#x5B;0]&#x5B;i] = i;\n\n&lt;pre&gt;&lt;code&gt;for ( int lv = 1 ; _1(lv) &amp;amp;lt;= nn ; lv ++ ) {\n    for ( int i = 1 ; i + _1(lv)  &amp;amp;lt;= nn + 1 ; i ++ ) {\n        ST&#x5B;lv]&#x5B;i] = min(ST&#x5B;lv-1]&#x5B;i], ST&#x5B;lv-1]&#x5B;i + _1(lv-1)], cmp_by_dep);\n        st&#x5B;lv]&#x5B;i] = min(st&#x5B;lv-1]&#x5B;i], st&#x5B;lv-1]&#x5B;i + _1(lv-1)], cmp_by_dfn);\n        ts&#x5B;lv]&#x5B;i] = max(ts&#x5B;lv-1]&#x5B;i], ts&#x5B;lv-1]&#x5B;i + _1(lv-1)], cmp_by_dfn);\n    }\n}\n&lt;\/code&gt;&lt;\/pre&gt;\n\n}\n\nPII f(int l, int r, int x) {\n    int a, b;\n    if (x == l) {\n        a = mn(x+1, r); b = mx(x+1, r);\n    } else if (x == r) {\n        a = mn(l, x-1); b = mx(l, x-1);\n    } else {\n        a = min(mn(l, x-1), mn(x+1, r), cmp_by_dfn);\n        b = max(mx(l, x-1), mx(x+1, r), cmp_by_dfn);\n    }\n    return {dep&#x5B;lca(a, b)], x};\n}\n\nint main() {\n\n#ifndef ONLINE_JUDGE\n    freopen(&amp;quot;in.txt&amp;quot;, &amp;quot;r&amp;quot;, stdin);\n    \/\/freopen(&amp;quot;\/Users\/minakokojima\/Documents\/GitHub\/ACM-Training\/Workspace\/out.txt&amp;quot;, &amp;quot;w&amp;quot;, stdout);\n#endif\n\n&lt;pre&gt;&lt;code&gt;int q; RD(n, q); FOR_1(i, 2, n) {\n    adj&#x5B;RD()].PB(i);\n}\n\ndfs(); init_rmq();\n\nDO(q) {\n    int l, r; RD(l, r);\n    int a = mn(l, r), b = mx(l, r);\n    PII z = max(f(l, r, a), f(l, r, b));\n    printf(&amp;amp;quot;%d %d\\n&amp;amp;quot;, z.se, z.fi);\n}\n&lt;\/code&gt;&lt;\/pre&gt;\n\n}\n\n<\/pre>\n<h2><span class=\"ez-toc-section\" id=\"%E7%9B%B4%E5%BE%84\"><\/span>\u76f4\u5f84<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<h3><span class=\"ez-toc-section\" id=\"SPOJ_PT07Z_Longest_path_in_a_tree\"><\/span>SPOJ PT07Z. Longest path in a tree<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li><a href=\"https:\/\/www.spoj.com\/problems\/PT07Z\/\">https:\/\/www.spoj.com\/problems\/PT07Z\/<\/a><\/li>\n<\/ul>\n<p>\u6811\u7684\u76f4\u5f84\u662f\u4e00\u4e2a\u975e\u5e38\u7ecf\u5178\u7684\u95ee\u9898\uff0c\u505a\u6cd5\u6781\u591a\u3002\u6bd4\u5982 dfs() \u4e24\u6b21\uff0c\u6811\u5f62 dp\uff0c\u90fd\u975e\u5e38\u7ecf\u5178\u3002<br \/>\n\u5176\u4e2d\u57fa\u4e8e\u7ebf\u6bb5\u6811\u533a\u95f4\u5408\u5e76\uff0c\u7ef4\u62a4\u76f4\u5f84\u4e5f\u662f\u4e00\u4e2a\u5927\u5bb6\u719f\u77e5\u7684\u7b97\u6cd5 \u2014\u2014 \u56e0\u4e3a\u4efb\u610f\u4e24\u4e2a\u8fde\u901a\u5757\u5408\u5e76\u540e\u7684\u76f4\u5f84\uff0c\u4e00\u5b9a\u7aef\u70b9\u8fd8\u5728\u539f\u5148\u7684\u4e24\u7ec4\u7aef\u70b9\u4e0a\u3002<br \/>\n\u8fd9\u4e2a\u65b9\u6cd5\u4e0d\u4ec5\u80fd\u6c42\u5168\u5c40\u76f4\u5f84\uff0c\u8fd8\u80fd\u6c42\u5b50\u6811\u76f4\u5f84\uff0c\u5220\u6389\u4e00\u4e9b\u5b50\u6811\u540e\u7684\u8fde\u901a\u5757\u7684\u76f4\u5f84\uff0c\u751a\u81f3\u865a\u6811\u76f4\u5f84\u4ec0\u4e48\u7684\u3002\u3002\u3002<br \/>\n\u7f3a\u70b9\u662f\u8f6c\u79fb\u65f6\u8981\u5404\u79cd\u8ba8\u8bba\u3002<\/p>\n<p>\u8fd9\u91cc\u6211\u4eec\u4ece\u4e0a\u9762\u63d0\u5230\u7684 dfs \u6c42 lca \u7684\u601d\u8def\u51fa\u53d1\uff0c\u53ef\u5c06\u4e00\u6bb5\u5b50\u6811\u7684\u76f4\u5f84\u8f6c\u6362\u4e3a max d[l]+d[r]-2dd[m] | l &lt; m &lt;= r\u3002<br \/>\n\u867d\u7136\u4ee3\u7801\u91cc\u6ca1\u6709 lca\uff0c\u4f46\u662f\u5176\u5b9e\u672c\u8d28\u5904\u5904\u90fd\u662f lca \u2014\u2014 \u4e0a\u8ff0\u516c\u5f0f\u91cc\u7684 m \u5c31\u9690\u542b\u4e86\u6c42 lca \u7684\u8fc7\u7a0b\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\n#include &amp;lt;lastweapon\/bitwise&amp;gt;\nusing namespace lastweapon;\n\nconst int N = int(1e5) + 9;\n\nint L&#x5B;N], R&#x5B;N], dep&#x5B;N], fa&#x5B;N], id&#x5B;N], nn;\nVII adj&#x5B;N]; LL W&#x5B;N]; int n;\n\nstruct rec{\n    LL d, dd, ld, rd, D;\n    void init(LL _d, LL _dd) {\n        d = _d; dd = 2*_dd;\n        D = ld = -INFF; rd = _d - dd;\n    }\n} T&#x5B;N*4];\n\n\/\/ max d&#x5B;l] + d&#x5B;r] - dd&#x5B;m]\n\/\/ l &amp;lt; m &amp;lt;= r\n\/\/ d \u6df1\u5ea6\n\/\/ dd \u7236\u4eb2\u7684\u6df1\u5ea6\n\n#define lx (x&amp;lt;&amp;lt;1)\n#define rx (lx|1)\n#define ml ((l+r)&amp;gt;&amp;gt;1)\n#define mr (ml+1)\n#define lc lx,l,ml\n#define rc rx,mr,r\nvoid upd(int x) {\n    T&#x5B;x].d = max(T&#x5B;lx].d, T&#x5B;rx].d);\n    T&#x5B;x].dd = min(T&#x5B;lx].dd, T&#x5B;rx].dd);\n    T&#x5B;x].ld = max(T&#x5B;lx].ld, T&#x5B;rx].ld, T&#x5B;lx].d - T&#x5B;rx].dd);\n    T&#x5B;x].rd = max(T&#x5B;lx].rd, T&#x5B;rx].rd, T&#x5B;rx].d - T&#x5B;lx].dd);\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);\n}\nvoid Build(int x, int l, int r) {\n    if (l == r) {\n        T&#x5B;x].init(dep&#x5B;id&#x5B;l]], dep&#x5B;fa&#x5B;id&#x5B;l]]]);\n    } else {\n        Build(lc);\n        Build(rc);\n        upd(x);\n    }\n}\nvoid dfs(int u = 1, int p = 0) {\n    id&#x5B;L&#x5B;u] = ++nn] = u;\n    for (auto it: adj&#x5B;u]) {\n        int v = it.fi; if (v == p) continue;\n        dep&#x5B;v] = dep&#x5B;u] + W&#x5B;it.se]; fa&#x5B;v] = u;\n        dfs(v, u);\n    }\n    R&#x5B;u] = nn;\n}\n\nint main() {\n\n#ifndef ONLINE_JUDGE\n    \/\/freopen(&amp;quot;in.txt&amp;quot;, &amp;quot;r&amp;quot;, stdin);\n    \/\/freopen(&amp;quot;\/Users\/minakokojima\/Documents\/GitHub\/ACM-Training\/Workspace\/out.txt&amp;quot;, &amp;quot;w&amp;quot;, stdout);\n#endif\n\n&lt;pre&gt;&lt;code&gt;dep&#x5B;0] = INF;\n\nint q; LL w; RD(n);\n\nREP_1(i, n-1) {\n    int x, y; RD(x, y); W&#x5B;i] = 1;\n    adj&#x5B;x].PB({y,i});\n    adj&#x5B;y].PB({x,i});\n}\n\ndfs(); Build(1, 1, n);\ncout &amp;amp;lt;&amp;amp;lt; T&#x5B;1].D &amp;amp;lt;&amp;amp;lt; endl;\n&lt;\/code&gt;&lt;\/pre&gt;\n\n}\n\n<\/pre>\n<h3><span class=\"ez-toc-section\" id=\"CEOI_2019_day_1_B_Dynamic_Diameter\"><\/span>CEOI 2019 day 1 B. Dynamic Diameter<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li><a href=\"https:\/\/codeforces.com\/contest\/1192\/submission\/189685098\">https:\/\/codeforces.com\/contest\/1192\/submission\/189685098<\/a><br \/>\n\u7ec8\u4e8e\u8981\u8fdb\u5165\u6b63\u7bc7\u4e86\u3002\u3002\u679c\u7136\u8fd8\u662f\u9700\u8981\u52a8\u6001\u76f4\u5f84\u65b9\u80fd\u4f53\u73b0\u8fd9\u4e2a\u505a\u6cd5\u7684\u5f3a\u5927\u4e4b\u5904\u3002\u3002\u3002<br \/>\n\u53ea\u8981\u5728\u4e0a\u9762\u7684\u4ee3\u7801\u7a0d\u7a0d\u4fee\u6539\uff0c\u652f\u6301\u4e24\u79cd\u4fee\u6539\u64cd\u4f5c\uff0c<br \/>\n\u4e00\u79cd\u533a\u95f4\u4fee\u6539\uff0c\u4fee\u6539\u5b50\u6811\u91cc\u6240\u6709\u7684 d \u503c \u548c dd \u503c\u3002\u3002<br \/>\n\u4e00\u79cd\u5355\u70b9\u4fee\u6539\uff0c\u56e0\u4e3a\u4e0a\u9762\u4fee\u6539 u \u6240\u5728\u7684\u5b50\u6811\u7684\u65f6\u5019\uff0cu \u7ed3\u70b9\u81ea\u5df1\u7684 dd \u5176\u5b9e\u662f\u4e0d\u88ab\u5f71\u54cd\u7684\uff0c\u8981\u4fee\u6b63\u56de\u6765\u3002<\/li>\n<\/ul>\n<p>\u800c\u8fd9\u4e9b\u90fd\u662f\u7ebf\u6bb5\u6811\u7684\u5e38\u89c4\u64cd\u4f5c\u4e86\u3002\u3002\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\n#include &amp;lt;lastweapon\/bitwise&amp;gt;\nusing namespace lastweapon;\n\nconst int N = int(1e5) + 9;\n\nint L&#x5B;N], R&#x5B;N], fa&#x5B;N], id&#x5B;N], EtoV&#x5B;N], nn;\nVII adj&#x5B;N]; LL dep&#x5B;N], W&#x5B;N]; int n;\n\nstruct rec{\n    LL d, dd, ld, rd, D, d0;\n    void init(LL _d, LL _dd) {\n        d = _d; dd = _dd*2;\n        D = ld = -INFF; rd = _d - dd;\n    }\n    void add(LL a) {\n        d += a; dd += a*2;\n        ld -= a; rd -= a;\n        d0 += a;\n    }\n} T&#x5B;N*4];\n\n\/\/ l &amp;lt; m &amp;lt;= r\n\/\/ max d&#x5B;l] + d&#x5B;r] - dd&#x5B;m]\n\/\/ d \u6df1\u5ea6\n\/\/ dd \u7236\u4eb2\u7684\u6df1\u5ea6\n\n#define lx (x&amp;lt;&amp;lt;1)\n#define rx (lx|1)\n#define ml ((l+r)&amp;gt;&amp;gt;1)\n#define mr (ml+1)\n#define lc lx,l,ml\n#define rc rx,mr,r\n\nvoid rls(int x) {\n    if (T&#x5B;x].d0) {\n        T&#x5B;lx].add(T&#x5B;x].d0);\n        T&#x5B;rx].add(T&#x5B;x].d0);\n        T&#x5B;x].d0 = 0;\n    }\n}\nvoid upd(int x) {\n    T&#x5B;x].d = max(T&#x5B;lx].d, T&#x5B;rx].d);\n    T&#x5B;x].dd = min(T&#x5B;lx].dd, T&#x5B;rx].dd);\n    T&#x5B;x].ld = max(T&#x5B;lx].ld, T&#x5B;rx].ld, T&#x5B;lx].d - T&#x5B;rx].dd);\n    T&#x5B;x].rd = max(T&#x5B;lx].rd, T&#x5B;rx].rd, T&#x5B;rx].d - T&#x5B;lx].dd);\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);\n}\nvoid Build(int x, int l, int r) {\n    if (l == r) {\n        T&#x5B;x].init(dep&#x5B;id&#x5B;l]], dep&#x5B;fa&#x5B;id&#x5B;l]]]);\n    } else {\n        Build(lc);\n        Build(rc);\n        upd(x);\n    }\n}\nvoid Modify(int x, int l, int r, int a, int b, LL d) {\n    if (b &amp;lt; l || r &amp;lt; a) return;\n    if (a &amp;lt;= l &amp;amp;&amp;amp; r &amp;lt;= b) {\n        T&#x5B;x].add(d);\n    } else {\n        rls(x);\n        Modify(lc, a, b, d);\n        Modify(rc, a, b, d);\n        upd(x);\n    }\n}\nvoid Modify(int x, int l, int r, int p, LL d) {\n    if (l == r) {\n        T&#x5B;x].init(T&#x5B;x].d, T&#x5B;x].dd\/2 + d);\n    } else {\n        rls(x);\n        if (p &amp;lt; mr) Modify(lc, p, d);\n        else Modify(rc, p, d);\n        upd(x);\n    }\n}\n\nvoid dfs(int u = 1, int p = 0) {\n    id&#x5B;L&#x5B;u] = ++nn] = u;\n    for (auto it: adj&#x5B;u]) {\n        int v = it.fi; if (v == p) continue;\n        dep&#x5B;v] = dep&#x5B;u] + W&#x5B;it.se]; fa&#x5B;v] = u; EtoV&#x5B;it.se] = v;\n        dfs(v, u);\n    }\n    R&#x5B;u] = nn;\n}\n\nint main() {\n\n#ifndef ONLINE_JUDGE\n    freopen(&amp;quot;in.txt&amp;quot;, &amp;quot;r&amp;quot;, stdin);\n    \/\/freopen(&amp;quot;\/Users\/minakokojima\/Documents\/GitHub\/ACM-Training\/Workspace\/out.txt&amp;quot;, &amp;quot;w&amp;quot;, stdout);\n#endif\n\n&lt;pre&gt;&lt;code&gt;dep&#x5B;0] = INFF;\n\nint q; LL w; RD(n, q, w);\n\nREP(i, n-1) {\n    int x, y; RD(x, y, W&#x5B;i]);\n    adj&#x5B;x].PB({y,i});\n    adj&#x5B;y].PB({x,i});\n}\n\ndfs(); Build(1, 1, n);\n\nDO(q) {\n    int t; LL v; RD(t, v);\n    t = (t + last_ans) % (n-1);\n    v = (v + last_ans) % w;\n\n    LL d = v - W&#x5B;t]; int x = EtoV&#x5B;t];\n    Modify(1, 1, n, L&#x5B;x], R&#x5B;x], d);\n    Modify(1, 1, n, L&#x5B;x], -d);\n    W&#x5B;t] = v;\n    printf(&amp;amp;quot;%lld\\n&amp;amp;quot;, last_ans = T&#x5B;1].D);\n}\n&lt;\/code&gt;&lt;\/pre&gt;\n\n}\n<\/pre>\n<h3><span class=\"ez-toc-section\" id=\"2019_ICPC_%E4%B8%8A%E6%B5%B7%E8%B5%9B%E5%8C%BA%E7%BD%91%E7%BB%9C%E8%B5%9B_Problem_A_Lightning_Routing_I\"><\/span>2019 ICPC \u4e0a\u6d77\u8d5b\u533a\u7f51\u7edc\u8d5b Problem A. Lightning Routing I<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li><a href=\"https:\/\/vjudge.net\/problem\/%E8%AE%A1%E8%92%9C%E5%AE%A2-41398\">https:\/\/vjudge.net\/problem\/%E8%AE%A1%E8%92%9C%E5%AE%A2-41398<\/a><\/li>\n<\/ul>\n<p>\u518d\u6765\u770b\u8fd9\u9898\uff0c\u5728\u4e0a\u9898\u7684\u57fa\u7840\u4e0a\uff0c\u8fd8\u9700\u8981\u7ef4\u62a4\u76f4\u5f84\u7684\u7aef\u70b9\u3002<br \/>\n\u8bbe\u76f4\u5f84\u4e3a (a, b)\uff0c\u90a3\u4e48\u7b54\u6848\u5c31\u662f max(dist(x, a), dist(x, b))\u3002<br \/>\n\u8fd9\u91cc\u7684 dist \u6b63\u5e38\u4e5f\u662f\u9700\u8981\u6c42 lca \u7684\uff0c\u4f46\u662f\u73b0\u5728\u6211\u4eec\u53d1\u73b0\u8981\u51cf\u53bb\u7684\u90a3\u73a9\u610f\u513f\u5df2\u7ecf\u5305\u542b\u5728\u6211\u4eec\u7ebf\u6bb5\u6811\u4e4b\u4e2d\u4e86\u3002\u3002\u3002<br \/>\n\u76f4\u63a5 query \u51fa\u6765\u5373\u53ef\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\n#include &amp;lt;lastweapon\/bitwise&amp;gt;\nusing namespace lastweapon;\n\nconst int N = int(1e5) + 9;\n\nint W&#x5B;N], L&#x5B;N], R&#x5B;N], fa&#x5B;N], id&#x5B;N], EtoV&#x5B;N], nn;\nVII adj&#x5B;N]; LL dep&#x5B;N]; int n;\n\nstruct rec{\n    pair&amp;lt;LL, int&amp;gt; d, ld, rd;\n    pair&amp;lt;LL, PII&amp;gt; D; LL dd, d0;\n    void init(LL _d, LL _dd, int x) {\n        d = {_d, x}; dd = _dd*2;\n        D = {-INFF, {0,0}};\n        ld = {-INFF, 0};\n        rd = {_d - dd, x};\n    }\n    void add(LL a) {\n        d.fi += a; dd += a*2;\n        ld.fi -= a; rd.fi -= a;\n        d0 += a;\n    }\n} T&#x5B;N*4];\n\n\/\/ l &amp;lt; m &amp;lt;= r\n\/\/ max d&#x5B;l] + d&#x5B;r] - dd&#x5B;m]\n\/\/ d \u6df1\u5ea6\n\/\/ dd \u7236\u4eb2\u7684\u6df1\u5ea6\n\n#define lx (x&amp;lt;&amp;lt;1)\n#define rx (lx|1)\n#define ml ((l+r)&amp;gt;&amp;gt;1)\n#define mr (ml+1)\n#define lc lx,l,ml\n#define rc rx,mr,r\nvoid rls(int x) {\n    if (T&#x5B;x].d0) {\n        T&#x5B;lx].add(T&#x5B;x].d0);\n        T&#x5B;rx].add(T&#x5B;x].d0);\n        T&#x5B;x].d0 = 0;\n    }\n}\nvoid upd(int x) {\n    T&#x5B;x].d = max(T&#x5B;lx].d, T&#x5B;rx].d);\n    T&#x5B;x].dd = min(T&#x5B;lx].dd, T&#x5B;rx].dd);\n    T&#x5B;x].ld = max(T&#x5B;lx].ld, T&#x5B;rx].ld, {T&#x5B;lx].d.fi - T&#x5B;rx].dd, T&#x5B;lx].d.se});\n    T&#x5B;x].rd = max(T&#x5B;lx].rd, T&#x5B;rx].rd, {T&#x5B;rx].d.fi - T&#x5B;lx].dd, T&#x5B;rx].d.se});\n    T&#x5B;x].D = max(T&#x5B;lx].D, T&#x5B;rx].D,{T&#x5B;lx].ld.fi + T&#x5B;rx].d.fi, {T&#x5B;lx].ld.se, T&#x5B;rx].d.se}},{T&#x5B;lx].d.fi + T&#x5B;rx].rd.fi, {T&#x5B;lx].d.se, T&#x5B;rx].rd.se}});\n}\nvoid Build(int x, int l, int r) {\n    if (l == r) {\n        T&#x5B;x].init(dep&#x5B;id&#x5B;l]], dep&#x5B;fa&#x5B;id&#x5B;l]]], id&#x5B;l]);\n    } else {\n        Build(lc);\n        Build(rc);\n        upd(x);\n    }\n}\nLL Query(int x, int l, int r, const int a, const int b) {\n    if (b &amp;lt; l || r &amp;lt; a) return INFF;\n    if (a &amp;lt;= l &amp;amp;&amp;amp; r &amp;lt;= b) {\n        return T&#x5B;x].dd;\n    } else {\n        rls(x);\n        return min(Query(lc, a, b), Query(rc, a, b));\n    }\n}\nLL Query(int x, int l, int r, const int p) {\n    if (l == r) {\n        return T&#x5B;x].d.fi;\n    } else {\n        rls(x);\n        return p &amp;lt; mr ? Query(lc, p) : Query(rc, p);\n    }\n}\nvoid Modify(int x, int l, int r, const int a, const int b, const LL d) {\n    if (b &amp;lt; l || r &amp;lt; a) return;\n    if (a &amp;lt;= l &amp;amp;&amp;amp; r &amp;lt;= b) {\n        T&#x5B;x].add(d);\n    } else {\n        rls(x);\n        Modify(lc, a, b, d);\n        Modify(rc, a, b, d);\n        upd(x);\n    }\n}\nvoid Modify(int x, int l, int r, const int p, const LL d) {\n    if (l == r) {\n        T&#x5B;x].init(T&#x5B;x].d.fi, T&#x5B;x].dd\/2 + d, id&#x5B;l]);\n    } else {\n        rls(x);\n        if (p &amp;lt; mr) Modify(lc, p, d);\n        else Modify(rc, p, d);\n        upd(x);\n    }\n}\n\nvoid dfs(int u = 1, int p = 0) {\n    id&#x5B;L&#x5B;u] = ++nn] = u;\n    for (auto it: adj&#x5B;u]) {\n        int v = it.fi; if (v == p) continue;\n        dep&#x5B;v] = dep&#x5B;u] + W&#x5B;it.se]; fa&#x5B;v] = u; EtoV&#x5B;it.se] = v;\n        dfs(v, u);\n    }\n    R&#x5B;u] = nn;\n}\nLL dist(int x, int y) {\n    if (x == y) return 0;\n    x = L&#x5B;x], y = L&#x5B;y]; if (x &amp;gt; y) swap(x, y);\n    return Query(1,1,n,x) + Query(1,1,n,y) - Query(1,1,n,x+1,y);\n}\n\nint main() {\n\n#ifndef ONLINE_JUDGE\n    freopen(&amp;quot;in.txt&amp;quot;, &amp;quot;r&amp;quot;, stdin);\n    \/\/freopen(&amp;quot;\/Users\/minakokojima\/Documents\/GitHub\/ACM-Training\/Workspace\/out.txt&amp;quot;, &amp;quot;w&amp;quot;, stdout);\n#endif\n\n&lt;pre&gt;&lt;code&gt;dep&#x5B;0] = INFF;\n\nRD(n); REP_1(i, n-1) {\n    int x, y; RD(x, y, W&#x5B;i]);\n    adj&#x5B;x].PB({y,i});\n    adj&#x5B;y].PB({x,i});\n}\n\ndfs(); Build(1, 1, n);\n\nRush {\n    if (RC() == &amp;amp;#039;Q&amp;amp;#039;) {\n        int x; RD(x);\n        auto D = T&#x5B;1].D;\n        int a = D.se.fi, b = D.se.se;\n        printf(&amp;amp;quot;%lld\\n&amp;amp;quot;, max(dist(x, a), dist(x, b)));\n    } else {\n        int i, w; RD(i, w);\n        LL d = w - W&#x5B;i]; int x = EtoV&#x5B;i];\n        Modify(1, 1, n, L&#x5B;x], R&#x5B;x], d);\n        Modify(1, 1, n, L&#x5B;x], -d);\n        W&#x5B;i] = w;\n    }\n}\n&lt;\/code&gt;&lt;\/pre&gt;\n\n}\n<\/pre>\n<h3><span class=\"ez-toc-section\" id=\"Educational_Codeforces_Round_141_Problem_G_Weighed_Tree_Radius\"><\/span>Educational Codeforces Round 141, Problem G. Weighed Tree Radius<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li><a href=\"https:\/\/codeforces.com\/contest\/1783\/problem\/G\">https:\/\/codeforces.com\/contest\/1783\/problem\/G<\/a><\/li>\n<\/ul>\n<p>\u7ec8\u4e8e\u53c8\u56de\u5230\u4e86\u6700\u521d\u7684\u8d77\u70b9&#8230; \u73b0\u5728\u518d\u7406\u89e3\u8840\u5c0f\u677f\u795e\u7684\u4ee3\u7801\u5c31\u5e94\u8be5\u8981\u7b80\u5355\u591a\u4e86\u5427\u3002<\/p>\n<p>\u56e0\u4e3a\u8fd9\u9898\u91cc\u7684\u4fee\u6539\u7684\u53ea\u6d89\u53ca\u70b9\u6743\uff0c\u800c\u70b9\u6743\u4e0d\u4f1a\u5f71\u54cd\u5b50\u6811\u72b6\u6001\uff0c\u6240\u4ee5\u53ea\u9700\u8981\u5355\u70b9\u4fee\u6539\uff0czkw \u6811\u5c31\u53ef\u4ee5\u4e86\u3002<br \/>\n\u53c8\u56e0\u4e3a\u8fd9\u91cc\u53ea\u6709\u5355\u4f4d\u6743\uff0c\u6240\u4ee5\u5176\u5b9e\u53ef\u4ee5 dd \u4e5f\u53ef\u4ee5\u4e0d\u7528\u53d6 lca \u7684\u6df1\u5ea6 \u2014\u2014 \u53cd\u6b63\u548c lca \u5c31\u5dee 1\u3002<br \/>\n\u8fd9\u6837\u4ee3\u7801\u53ef\u4ee5\u66f4\u52a0\u7b80\u6d01\u3002<\/p>\n<ul>\n<li><a href=\"https:\/\/codeforces.com\/contest\/1783\/submission\/259279448\">https:\/\/codeforces.com\/contest\/1783\/submission\/259279448<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>\u524d\u60c5\u63d0\u8981 \u524d\u51e0\u5929\u505a\u4e86\u4e00\u4e0b Educational Codeforces Round 141 \u7684 F \u9898\u3002\u3002\u3002\u770b\u8d77\u6765\u662f\u4e2a\u52a8\u6001\u76f4\u5f84\uff0c\u4e4b\u524d\u7f51\u8d5b\u6211\u51fa\u8fc7\u4e00\u6b21\uff0c\u7ffb\u51fa\u6807\u7a0b\u5e94\u8be5\u80fd\u79d2\u3002\u4f46\u662f\u5199\u8d77\u6765\u53d1\u73b0\u8981\u6539\u7684\u5730\u65b9\u5b9e\u5728\u5f88\u591a\uff0c\u5927\u6982\u662f\u6211\u7684\u6807\u7a0b\u5b9e\u5728\u4e0d\u600e\u4e48\u9ad8\u660e\u3002 \u4e8e\u662f\u770b\u4e86\u4e00\u4e0b\u4ee3\u7801\u6700\u77ed\u7684\u5bb6\u4f19\u4eec\u90fd\u5199\u4e86\u5565\uff0c\u4e8e\u662f\u6211\u88ab \u8fd9\u4efd\u4ee3\u7801 \u9707\u60ca\u4e86\u3002 \u7b2c\u4e00\u53cd\u5e94\u662f\uff0c\u867d\u7136\u8f6c\u79fb\u6211\u770b\u4e0d\u61c2\uff0c\u4f46\u662f\u5e94\u8be5\u5c31\u662f\u4e00\u9897 zkw \u6811\uff0c\u7b49\u4ef7\u4e8e \u8fd9\u7bc7\u6587\u7ae0\u91cc\u6240\u63d0\u5230\u7684\u7b97\u6cd5\u4e09 \u561b\u3002\u3002\u3002 &#8230;but wait, \u4f60\u7684 lca \u5728\u54ea\u91cc\u3002\u3002\u3002 \u4e4b\u524d Dynamic Diameter \u91cc\u6211\u4eec\u662f\u5728 euler \u5e8f\u4e0a\u5efa\u7ebf\u6bb5\u6811\u3002\u3002\u3002\u5b9e\u9645\u4e0a\u662f\u9690\u542b\u4e86\u4e00\u4e2a\u6c42 lca \u7684\u8fc7\u7a0b\u7684\u3002\u3002\u3002 \u4f46\u662f\u8fd9\u91cc\u660e\u663e\u662f dfs \u5e8f\u5427\u3002\u3002\u3002\u3002\u3002\u3002 \u307e\u3055\u304b\uff1f&#8230; LCA dfs \u5e8f\u4e5f\u53ef\u4ee5\u6c42 lca\uff1f \u641c\u4e86\u4e00\u4e0b\uff0c\u539f\u6765\u8fd8\u771f\u6709\uff01 \u6838\u5fc3\u601d\u60f3\uff1a\u867d\u7136 lca \u81ea\u5df1\u4e0d\u4f1a\u51fa\u73b0\u5728\u533a\u95f4\u91cc\u3002\u3002\u4f46\u662f\u4f60\u7684\u5b69\u5b50\u4f1a\u554a\u3002\u3002\u3002\u627e\u5230\u8fd9\u4e2a\u70b9\u518d\u6c42\u7236\u4eb2\uff0c\u6216\u8005\uff0c\u76f4\u63a5\u5728\u5efa st \u8868\u7684\u65f6\u5019\u5c31\u76f4\u63a5\u653e\u7236\u7ed3\u70b9\u5c31\u884c\u4e86\uff01 \u597d\u5427\u3002\u3002\u53cd\u6b63\u6211\u662f\u60f3\u4e0d\u5230\u3002\u3002\u56e7\u3002\u3002 \u8fd9\u4e2a\u677f\u5b50\u663e\u7136\u5404\u65b9\u9762\u90fd\u662f\u5b8c\u80dc euler \u5e8f lca \u7684\u3002\u3002\u3002\u7279\u522b\u662f\u6709\u7684\u9898\u91cc\u540c\u65f6\u51fa\u73b0 dfs \u5e8f\u548c lca \u7684\u65f6\u5019 \u2014\u2014 [&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-2172","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-z2","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2172","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=2172"}],"version-history":[{"count":31,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2172\/revisions"}],"predecessor-version":[{"id":3263,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2172\/revisions\/3263"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=2172"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=2172"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=2172"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}