{"id":1666,"date":"2020-07-23T13:24:57","date_gmt":"2020-07-23T05:24:57","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1666"},"modified":"2020-07-23T13:24:57","modified_gmt":"2020-07-23T05:24:57","slug":"bzoj-2125-%e6%9c%80%e7%9f%ad%e8%b7%af","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/bzoj-2125-%e6%9c%80%e7%9f%ad%e8%b7%af\/","title":{"rendered":"BZOJ 2125: \u6700\u77ed\u8def"},"content":{"rendered":"

BZOJ<\/a> | Luogu<\/a>
\nhttps:\/\/cmxrynp.github.io\/2018\/10\/29\/BZOJ-2125-%E6%9C%80%E7%9F%AD%E8%B7%AF\/<\/a>
\nhttps:\/\/blog.csdn.net\/LPA20020220\/article\/details\/88887231<\/a><\/p>\n

\u9898\u610f<\/h2>\n

\u7ed9\u4f60\u4e00\u4e2a\u6709 n \u4e2a\u70b9\u548c m \u6761\u8fb9\u7684\u4ed9\u4eba\u638c\u56fe\uff0c\u548c q \u7ec4\u8be2\u95ee\uff0c
\n\u6bcf\u6b21\u8be2\u95ee\u4e24\u4e2a\u70b9\u4e4b\u95f4\u7684\u6700\u77ed\u8def\u3002<\/p>\n

\u9898\u89e3<\/h2>\n

\u5706\u65b9\u6811<\/h3>\n
\nconst int N = int(2e4) + 9, LV = 15;\n\nVII adj[N], adjj[N];\nint dfn[N], low[N], tt, sta[N], top;\nint fa[LV][N], dep[N], D[N], DD[N], L[N];\nint n, nn;\n\ninline int move_up(int x, int t){\nfor (int lv=0;t;++lv,t&gt;&gt;=1)\nif (t&amp;1) x = fa[lv][x];\nreturn x;\n}\ninline int lca(int x, int y) {\nif (dep[x]&gt;dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) return x;\nDWN(lv, LV, 0) if (fa[lv][x]!=fa[lv][y]) x = fa[lv][x], y = fa[lv][y];\nreturn fa[0][x];\n}\nvoid getLCA(int x, int y, int &amp;a, int &amp;b, int &amp;z) {\nif (dep[x]&gt;dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) {z = x; return;}\nDWN(lv, LV, 0) if (fa[lv][x]!=fa[lv][y]) x = fa[lv][x], y = fa[lv][y];\na = x; b = y; z = fa[0][x];\n}\n\nvoid add_edge(int u, int v, LL w) {\nadjj[u].PB(MP(v, w));\n}\n\n#define v it-&gt;fi\n#define w it-&gt;se\nvoid tarjan(int u = 1, int p = -1) {\nlow[u] = dfn[u] = ++tt;\nsta[++top] = u;\nECH(it, adj[u]) if (v != p) {\nif (!dfn[v]) {\nD[v] = D[u] + w; tarjan(v, u);\ncheckMin(low[u], low[v]);\nif (dfn[v] == low[v]) add_edge(u, v, w); \/\/ tree edge\n} else if (dfn[v] &lt; dfn[u]) { \/\/ find circle\n            checkMin(low[u], dfn[v]);\n            add_edge(v, ++nn, 0); L[nn] = D[u]-D[v]+w;\n            for (int i=top;sta[i]!=v;--i) {\n                int d = D[sta[i]]-D[v];\n                add_edge(nn, sta[i], min(d, L[nn]-d));\n            }\n        }\n    }\n    --top;\n}\n#define p fa[0][u]\nvoid dfs(int u = 1) {\n    ECH(it, adjj[u]) {\n        dep[v] = dep[u] + 1; DD[v] = DD[u] + w;\n        fa[0][v] = u; for (int lv=0;fa[lv+1][v]=fa[lv][fa[lv][v]];++lv);\n        dfs(v);\n    }\n}\n#undef p\n#undef w\n#undef v\n\nint main() {\n\n#ifndef ONLINE_JUDGE\n    freopen("in.txt", "r", stdin);\n    \/\/freopen("out.txt", "w", stdout);\n#endif\n\n    int Q, m; RD(n, m, Q);\n\n    DO(m) {\n        int x, y, w; RD(x, y, w);\n        adj[x].PB(MP(y, w));\n        adj[y].PB(MP(x, w));\n    }\n\n    nn = n; tarjan(); dfs();\n\n    DO(Q) {\n        int x, y, a, b, z; RD(x, y); getLCA(x, y, a, b, z);\n\n        \/\/cout &lt;&lt; x &lt;&lt; " " &lt;&lt; y &lt;&lt; " " &lt;&lt;  z&lt;&lt; endl;\n\n        if (z &lt;= n) { \/\/ round one ...\n            OT(DD[x]+DD[y]-DD[z]*2);\n        } else { \/\/ square one ...\n            int d = abs(D[a]-D[b]);\n            OT(DD[x]+DD[y]-DD[a]-DD[b]+min(d, L[z]-d));\n        }\n    }\n}\n<\/pre>\n
\u52a8\u6001\u4ed9\u4eba\u638c<\/h3>\n
https:\/\/www.luogu.com.cn\/record\/31868182<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
BZOJ | Luogu https:\/\/cmxrynp.github.io\/2018\/10\/29\/BZOJ-2125-%E6%9C%80%E7%9F%AD%E8%B7%AF\/ https:\/\/blog.csdn.net\/LPA20020220\/article\/details\/88887231 \u9898\u610f \u7ed9\u4f60\u4e00\u4e2a\u6709 n \u4e2a\u70b9\u548c m \u6761\u8fb9\u7684\u4ed9\u4eba\u638c\u56fe\uff0c\u548c q \u7ec4\u8be2\u95ee\uff0c \u6bcf\u6b21\u8be2\u95ee\u4e24\u4e2a\u70b9\u4e4b\u95f4\u7684\u6700\u77ed\u8def\u3002 \u9898\u89e3 \u5706\u65b9\u6811 const int N = int(2e4) + 9, LV = 15; VII adj[N], adjj[N]; int dfn[N], low[N], tt, sta[N], top; int fa[LV][N], dep[N], D[N], DD[N], L[N]; int n, nn; inline int move_up(int x, int t){ for (int lv=0;t;++lv,t&gt;&gt;=1) if (t&amp;1) […]<\/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-1666","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-qS","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1666","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=1666"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1666\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1666"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1666"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1666"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}