{"id":2705,"date":"2023-05-01T18:00:49","date_gmt":"2023-05-01T10:00:49","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=2705"},"modified":"2023-05-03T18:52:31","modified_gmt":"2023-05-03T10:52:31","slug":"block-cut-tree","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/block-cut-tree\/","title":{"rendered":"\u5706\u65b9\u6811"},"content":{"rendered":"<ul>\n<li><a href=\"https:\/\/oi-wiki.org\/graph\/block-forest\/#%E4%BE%8B%E9%A2%98\">https:\/\/oi-wiki.org\/graph\/block-forest\/#%E4%BE%8B%E9%A2%98<\/a><\/li>\n<li><a href=\"https:\/\/codeforces.com\/gym\/102512\/problem\/A\">https:\/\/codeforces.com\/gym\/102512\/problem\/A<\/a><\/li>\n<li><a href=\"https:\/\/www.shuizilong.com\/house\/archives\/spoj-9577-dynamic-tree-connectivity\/\">https:\/\/www.shuizilong.com\/house\/archives\/spoj-9577-dynamic-tree-connectivity\/<\/a><\/li>\n<li><a href=\"https:\/\/www.shuizilong.com\/house\/archives\/spoj-375-query-on-a-tree\/\">https:\/\/www.shuizilong.com\/house\/archives\/spoj-375-query-on-a-tree\/<\/a><\/li>\n<\/ul>\n<h1>\u4ed9\u4eba\u638c<\/h1>\n<ul>\n<li><a href=\"https:\/\/codeforces.com\/problemset\/problem\/231\/E\">https:\/\/codeforces.com\/problemset\/problem\/231\/E<\/a><\/li>\n<\/ul>\n<h1>LibreOJ #2587. \u300cAPIO2018\u300d\u94c1\u4eba\u4e24\u9879<\/h1>\n<p>\u5de7\u5999\u7684\u6807\u53f7\uff0c\u8bbe\u65b9\u70b9\u7684\u6743\u503c\u4e3a\u5468\u56f4\u5706\u70b9\u7684\u4e2a\u6570\uff0c\u5706\u70b9\u7684\u6743\u503c\u4e3a -1\uff0c\u90a3\u4e48\u4efb\u610f\u4e00\u4e2a\u5408\u6cd5\u7684 (s,f)\uff0c\u4e2d\u95f4\u5408\u6cd5\u7684 c \u6070\u597d\u7b49\u4e8e\u5b83\u4eec\u5728\u5706\u65b9\u6811\u4e0a\u8def\u5f84\u7684\u6743\u503c\u548c\u3002\u4e8e\u662f\u76f4\u63a5\u6811 dp \u5373\u53ef\u3002<\/p>\n<h1>Codeforces Round 278 (Div. 1) E. Tourists<\/h1>\n<p>\u5706\u65b9\u6811\u540e\u8f6c\u5316\u4e3a QTREE\u3002<br \/>\n\u5982\u679c\u6211\u4eec\u65b9\u70b9\u7684\u6743\u503c\u8bb0\u4e3a\u6240\u6709\u5468\u56f4\u5706\u70b9\u7684\u6700\u5c0f\u503c\uff0c\u90a3\u4e48\u4fee\u6539\u5706\u70b9\u64cd\u4f5c\u53ef\u80fd\u4f1a\u5f71\u54cd O(n) \u4e2a\u8282\u70b9\uff0c<br \/>\n\u4f46\u662f\u5176\u5b9e\u6211\u4eec\u53ef\u4ee5\u53ea\u8003\u8651\u6709\u6839\u6811\uff0c\u65b9\u70b9\u53ea\u8bb0\u5f55\u5b69\u5b50\u4e2d\u5706\u70b9\u7684\u6700\u5c0f\u503c\uff0c\u90a3\u4e48\u64cd\u4f5c\u5c31\u53ea\u4f1a\u5f71\u54cd O(1) \u4e2a\u8282\u70b9\u4e86\uff0c<br \/>\n\u8fd9\u6837\u7edf\u8ba1\u7b54\u6848\u7684\u65f6\u5019\uff0c\u5982\u679c lca \u662f\u65b9\u70b9\uff0c\u53ea\u8981\u518d\u5411\u4e0a\u53d6\u4e00\u4e2a\u6700\u5c0f\u503c\u5373\u53ef\u3002<br \/>\n\u8fd9\u4e2a\u6280\u5de7\u5728 <a href=\"https:\/\/www.shuizilong.com\/house\/archives\/typedb-forces-2023\/\">\u4e4b\u524d<\/a> \u4e5f\u51fa\u73b0\u8fc7\u3002<\/p>\n<h1>Luogu P8456. \u300cSWTR-8\u300d\u5730\u5730\u94c1\u94c1<\/h1>\n<ul>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/P8456\">https:\/\/www.luogu.com.cn\/problem\/P8456<\/a><\/li>\n<\/ul>\n<p>\u96be\u70b9\u5728\u4e8e\u4ec0\u4e48\u60c5\u51b5\u4e0b\u4e24\u70b9\u4e4b\u95f4\u540c\u65f6\u5b58\u5728\u767d\u8def\u5f84\u548c\u9ed1\u8def\u5f84\uff0c\u4f46\u4e0d\u5b58\u5728\u9ed1\u767d\u8def\u5f84\u3002<br \/>\n\u8fd9\u4e2a\u9898\u8fd8\u9700\u8981\u627e\u5230\u6bcf\u4e2a\u53cc\u8fde\u901a\u5206\u91cf\u5185\u7684\u6240\u6709\u8fb9\uff0c\u6240\u4ee5\u8fd8\u9700\u8981\u5f00\u4e2a\u8fb9\u6808\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(1e6) + 9, M = int(2e6) + 9;\r\n\r\nint dfn&#x5B;N], low&#x5B;N]; stack&lt;int&gt; sta, sta_e; int nn;\r\nint hd&#x5B;N], suc&#x5B;M], to&#x5B;M];\r\nint n; LL z;\r\n\r\nnamespace DSU{ \/\/ Disjoint Set Union\r\n    int P&#x5B;N], R&#x5B;N], sz&#x5B;N];\r\n    inline void Make(int x){\r\n        P&#x5B;x] = x, R&#x5B;x] = 0;\r\n    }\r\n    inline int Find(int x){\r\n        return P&#x5B;x] == x ? x : P&#x5B;x] = Find(P&#x5B;x]);\r\n    }\r\n    inline void Unionn(int x, int y){\r\n        if (R&#x5B;x] == R&#x5B;y]) ++R&#x5B;x];\r\n        else if (R&#x5B;x] &lt; R&#x5B;y]) swap(x, y);\r\n        sz&#x5B;x] += sz&#x5B;y];\r\n        P&#x5B;y] = x;\r\n    }\r\n    inline void Union(int x, int y){\r\n        x = Find(x), y = Find(y);\r\n        if (x != y) Unionn(x, y);\r\n    }\r\n} \/\/using namespace DSU;\r\n\r\ninline LL C2(LL n) {\r\n    return n*(n-1)\/2;\r\n}\r\n\r\nstruct Block_Cut_Tree {\r\n    VI adj&#x5B;N]; int fa&#x5B;N], col&#x5B;N];\r\n    int n;\r\n\r\n    void add_block(int u, int v, int r) {\r\n        ++n; int b = ::n+n;\r\n        adj&#x5B;u].PB(b); fa&#x5B;b] = u;\r\n        do {\r\n            u = sta.top(); sta.pop();\r\n            adj&#x5B;b].PB(u);\r\n        } while (u^v);\r\n\r\n        int i, c; map&lt;int, int&gt; mask;\r\n        do {\r\n            i = sta_e.top(), sta_e.pop();\r\n            u = to&#x5B;i^1], v = to&#x5B;i]; if (u &lt; 0) u = -u, v = -v, c = 2; else c = 1;\r\n            col&#x5B;b] |= c; mask&#x5B;u] |= c; mask&#x5B;v] |= c;\r\n        } while (r^i);\r\n\r\n        if (col&#x5B;b] == 3) {\r\n            int cnt = 0; for (auto t: mask) if (t.se == 3) {\r\n                if (++cnt &gt; 2) break;\r\n            }\r\n            if (cnt == 2) --z;\r\n        }\r\n    }\r\n\r\n    LL calc(int c) {\r\n        using namespace DSU;\r\n        int nn = ::n+n;\r\n        REP_1(i, nn) Make(i);\r\n        REP_1(i, ::n) sz&#x5B;i] = 1;\r\n        REP_1(i, n) sz&#x5B;::n+i] = 0;\r\n\r\n        FOR_1(b, ::n+1, nn) if (col&#x5B;b] == c) {\r\n            Union(b, fa&#x5B;b]);\r\n            for (auto u: adj&#x5B;b]) Union(b, u);\r\n        }\r\n\r\n        LL z = 0; REP_1(i, nn) if (Find(i) == i) z += C2(sz&#x5B;i]);\r\n        return z;\r\n    }\r\n} bct;\r\n\r\nvoid tarjan(int u = 1, int r = 0) {\r\n\r\n    dfn&#x5B;u] = low&#x5B;u] = ++nn;\r\n    sta.push(u);\r\n\r\n    REP_G(i, u) if (i^r) {\r\n        int v = abs(to&#x5B;i]);\r\n        if (dfn&#x5B;v]) {\r\n            if (dfn&#x5B;u] &lt; dfn&#x5B;v]) continue;\r\n            sta_e.push(i);\r\n            checkMin(low&#x5B;u], dfn&#x5B;v]);\r\n        } else {\r\n            sta_e.push(i); tarjan(v, i^1);\r\n            checkMin(low&#x5B;u], low&#x5B;v]);\r\n            if (dfn&#x5B;u] &lt;= low&#x5B;v]) { \/\/ find a cut!\r\n                bct.add_block(u, v, i);\r\n            }\r\n        }\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    RD(); int m; RD(n, m);\r\n\r\n    for (int i=2;i&lt;=2*m;) {\r\n        int x, y; bool c; RD(x, y); c = RC() == 'd';\r\n        suc&#x5B;i] = hd&#x5B;x], hd&#x5B;x] = i, to&#x5B;i] = c ? -y : y; ++i;\r\n        suc&#x5B;i] = hd&#x5B;y], hd&#x5B;y] = i, to&#x5B;i] = c ? -x : x; ++i;\r\n    }\r\n\r\n    z = C2(n); tarjan();\r\n    z -= bct.calc(1) + bct.calc(2);\r\n    cout &lt;&lt; z &lt;&lt; endl;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/oi-wiki.org\/graph\/block-forest\/#%E4%BE%8B%E9%A2%98 https:\/\/codeforces.com\/gym\/102512\/problem\/A https:\/\/www.shuizilong.com\/house\/archives\/spoj-9577-dynamic-tree-connectivity\/ https:\/\/www.shuizilong.com\/house\/archives\/spoj-375-query-on-a-tree\/ \u4ed9\u4eba\u638c https:\/\/codeforces.com\/problemset\/problem\/231\/E LibreOJ #2587. \u300cAPIO2018\u300d\u94c1\u4eba\u4e24\u9879 \u5de7\u5999\u7684\u6807\u53f7\uff0c\u8bbe\u65b9\u70b9\u7684\u6743\u503c\u4e3a\u5468\u56f4\u5706\u70b9\u7684\u4e2a\u6570\uff0c\u5706\u70b9\u7684\u6743\u503c\u4e3a -1\uff0c\u90a3\u4e48\u4efb\u610f\u4e00\u4e2a\u5408\u6cd5\u7684 (s,f)\uff0c\u4e2d\u95f4\u5408\u6cd5\u7684 c \u6070\u597d\u7b49\u4e8e\u5b83\u4eec\u5728\u5706\u65b9\u6811\u4e0a\u8def\u5f84\u7684\u6743\u503c\u548c\u3002\u4e8e\u662f\u76f4\u63a5\u6811 dp \u5373\u53ef\u3002 Codeforces Round 278 (Div. 1) E. Tourists \u5706\u65b9\u6811\u540e\u8f6c\u5316\u4e3a QTREE\u3002 \u5982\u679c\u6211\u4eec\u65b9\u70b9\u7684\u6743\u503c\u8bb0\u4e3a\u6240\u6709\u5468\u56f4\u5706\u70b9\u7684\u6700\u5c0f\u503c\uff0c\u90a3\u4e48\u4fee\u6539\u5706\u70b9\u64cd\u4f5c\u53ef\u80fd\u4f1a\u5f71\u54cd O(n) \u4e2a\u8282\u70b9\uff0c \u4f46\u662f\u5176\u5b9e\u6211\u4eec\u53ef\u4ee5\u53ea\u8003\u8651\u6709\u6839\u6811\uff0c\u65b9\u70b9\u53ea\u8bb0\u5f55\u5b69\u5b50\u4e2d\u5706\u70b9\u7684\u6700\u5c0f\u503c\uff0c\u90a3\u4e48\u64cd\u4f5c\u5c31\u53ea\u4f1a\u5f71\u54cd O(1) \u4e2a\u8282\u70b9\u4e86\uff0c \u8fd9\u6837\u7edf\u8ba1\u7b54\u6848\u7684\u65f6\u5019\uff0c\u5982\u679c lca \u662f\u65b9\u70b9\uff0c\u53ea\u8981\u518d\u5411\u4e0a\u53d6\u4e00\u4e2a\u6700\u5c0f\u503c\u5373\u53ef\u3002 \u8fd9\u4e2a\u6280\u5de7\u5728 \u4e4b\u524d \u4e5f\u51fa\u73b0\u8fc7\u3002 Luogu P8456. \u300cSWTR-8\u300d\u5730\u5730\u94c1\u94c1 https:\/\/www.luogu.com.cn\/problem\/P8456 \u96be\u70b9\u5728\u4e8e\u4ec0\u4e48\u60c5\u51b5\u4e0b\u4e24\u70b9\u4e4b\u95f4\u540c\u65f6\u5b58\u5728\u767d\u8def\u5f84\u548c\u9ed1\u8def\u5f84\uff0c\u4f46\u4e0d\u5b58\u5728\u9ed1\u767d\u8def\u5f84\u3002 \u8fd9\u4e2a\u9898\u8fd8\u9700\u8981\u627e\u5230\u6bcf\u4e2a\u53cc\u8fde\u901a\u5206\u91cf\u5185\u7684\u6240\u6709\u8fb9\uff0c\u6240\u4ee5\u8fd8\u9700\u8981\u5f00\u4e2a\u8fb9\u6808\u3002 #include &lt;lastweapon\/io&gt; using namespace lastweapon; const int N = int(1e6) + 9, [&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-2705","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-HD","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2705","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=2705"}],"version-history":[{"count":9,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2705\/revisions"}],"predecessor-version":[{"id":2738,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2705\/revisions\/2738"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=2705"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=2705"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=2705"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}