{"id":1036,"date":"2014-10-16T13:25:41","date_gmt":"2014-10-16T05:25:41","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1036"},"modified":"2014-10-16T20:13:16","modified_gmt":"2014-10-16T12:13:16","slug":"bzoj-3648-%e5%af%9d%e5%ae%a4%e7%ae%a1%e7%90%86","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/bzoj-3648-%e5%af%9d%e5%ae%a4%e7%ae%a1%e7%90%86\/","title":{"rendered":"BZOJ 3648. \u5bdd\u5ba4\u7ba1\u7406"},"content":{"rendered":"

http:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=3648<\/a>
\nhttp:\/\/hi.baidu.com\/greencloud\/item\/5d009dddcecde7b133db90ad<\/a><\/p>\n

Brief description: <\/h3>\n

\u7ed9\u5b9a\u4e00\u4e2a\u6811\u52a0\u4e00\u6761\u8fb9\u3002\u3002\u6c42\u8fd9\u4e2a\u56fe\u4e2d\u6240\u6709\u7ecf\u8fc7\u7ed3\u70b9\u6811 >= k \u7684\u8def\u5f84\u6709\u591a\u5c11\u7ec4\u3002\u3002
\n\uff08(u -> v) \u4e0e (v -> u) \u7b97\u4e00\u7ec4\u3002\u3002\uff09<\/p>\n

<\/p>\n

Analysis: <\/h3>\n

\u6811\u7684\u60c5\u51b5\u6811\u5206\u6cbb\u5373\u53ef\u3002\u3002\u3002\u7531\u4e8e\u90fd\u662f\u5355\u4f4d\u6743\u3002\u3002\u3002\u6211\u4eec\u6811\u72b6\u6570\u7ec4\u5373\u53ef\u3002\u3002\u57fa\u672c\u529f\u3002\u3002\u3002<\/p>\n

\u8003\u8651\u73af\u7684\u60c5\u51b5\u3002\u3002\u3002\u6bd4\u5982\u6837\u4f8b\u3002\u3002\u3002\u3002
\n\u6211\u4eec\u6cbf\u987a\u65f6\u9488\u8f6c\u4e09\u6b21\u3002\u3002\u3002\uff08\u6ce8\u610f (u, v) \u548c (v, u) \u53ea\u7edf\u8ba1\u4e00\u6b21\u3002\u3002\u800c\u4ed6\u4eec\u6b63\u597d\u5206\u522b\u5bf9\u5e94\u4e00\u6b21\u987a\u65f6\u9488\u548c\u4e00\u6b21\u9006\u65f6\u9488\u3002\u3001\u3001\uff09
\n\u8fd9\u91cc d \u662f offset\u3002\u3002\u3002<\/p>\n

\r\n\r\n\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(1e5) + 9, M = N*2;\r\n\r\nnamespace BIT{\r\n    const int N = ::N+::N+1;\r\n    int C[N], n;\r\n    void Add(int x, int d = 1){\r\n        x += ::N;\r\n        for (;x<N;x+=low_bit(x)) C[x] += d;\r\n    }\r\n    int Sum(int x){\r\n        x += ::N;\r\n        int res = 0; for (;x;x^=low_bit(x)) res += C[x];\r\n        return res;\r\n    }\r\n    int Rsum(int x){\r\n        int t = Sum(::N); t -= x + ::N > 0 ? Sum(x) : 0;\r\n        return t;\r\n    }\r\n} \/\/using namespace BIT;\r\n\r\n\r\nint hd[N], prd[M], suc[M], to[M];\r\nint m;\r\n\r\nvoid add_edge(int a, int b){\r\n    to[m] = b, suc[prd[hd[a]] = m] = hd[a], hd[a] = m++;\r\n}\r\n\r\nvoid add_edgee(int a, int b) {\r\n    add_edge(a, b);\r\n    add_edge(b, a);\r\n}\r\n\r\n#define aa to[i^1]\r\n#define bb to[i]\r\n#define v bb\r\n\r\ninline void del(int i){\r\n    if (hd[aa] == i) prd[hd[aa] = suc[i]] = 0;\r\n    else prd[suc[i]] = prd[i], suc[prd[i]] = suc[i];\r\n}\r\n\r\ninline void rsm(int i){\r\n    if (suc[i] == hd[aa]) hd[aa] = i;\r\n    prd[suc[i]] = suc[prd[i]] = i;\r\n}\r\n\r\ninline void dell(int i){\r\n    del(i), del(i^1);\r\n}\r\n\r\ninline void rsmm(int i){\r\n    rsm(i), rsm(i^1);\r\n}\r\n\r\nint n, k; int sz[N], dep[N]; LL ans; VI L;\r\n\r\nvoid Scann(int u, int p) {\r\n    L.PB(dep[u]); REP_G(i, u) if (v != p){\r\n        dep[v] = dep[u] + 1;\r\n        Scann(v, u);\r\n    }\r\n}\r\n\r\nvoid Scan(int u){\r\n    CLR(L); dep[u] = 1; L.PB(dep[u]);\r\n    REP_G(i, u){\r\n        dep[v] = dep[u] + 1;\r\n        Scann(v, u);\r\n    }\r\n}\r\n\r\nnamespace TDC{\r\n\r\n    int nn, cc, c;\r\n\r\n    void dfsc(int u, int p = 0){\r\n        int ss = 0; sz[u] = 1; REP_G(i, u) if (v != p){\r\n            dfsc(v, u), sz[u] += sz[v];\r\n            checkMax(ss, sz[v]);\r\n        }\r\n        checkMax(ss, nn - sz[u]);\r\n        if (ss <= cc) cc = ss, c = u;\r\n    }\r\n\r\n    void dfs0(int u, int p = -1){\r\n        sz[u] = 1; REP_G(i, u) if (v != p){\r\n            dep[v] = dep[u] + 1;\r\n            dfs0(v, u);\r\n            sz[u] += sz[v];\r\n        }\r\n    }\r\n\r\n    void dfs1(int u, int p){\r\n        L.PB(dep[u]);\r\n        REP_G(i, u) if (v != p){\r\n            dfs1(v, u);\r\n        }\r\n    }\r\n\r\n    void dfs2(int u, int p = -1){\r\n        BIT::Add(dep[u], -1);\r\n        REP_G(i, u) if (v != p){\r\n            dfs2(v, u);\r\n        }\r\n    }\r\n\r\n    void gao(int u = 1){\r\n\r\n        cc = INF, dfsc(u), u = c;\r\n\r\n        dep[u] = 1; dfs0(u); BIT::Add(1);\r\n\r\n        REP_G(i, u){\r\n            CLR(L); dfs1(v, u);\r\n            ECH(it, L) ans += BIT::Rsum(k-*it);\r\n            ECH(it, L) BIT::Add(*it);\r\n        }\r\n\r\n        dfs2(u);\r\n\r\n        REP_G(i, u){\r\n            nn = sz[v], dell(i), gao(v), rsmm(i);\r\n        }\r\n    }\r\n}\r\n\r\n\r\nVI Circle; PII sta[N]; int pos[N], top = 0;\r\n\r\nvoid dfs(int u = 1, int p = -1){ \/\/ Find_Circle\r\n    sta[pos[u]=++top].fi = u;\r\n    REP_G(i, u) if (i != (p^1)){\r\n        sta[top].se = i;\r\n        if (!pos[v]) dfs(v, i);\r\n        else {\r\n            FOR_1(ii, pos[v], top) {\r\n                Circle.PB(sta[ii].fi);\r\n                dell(sta[ii].se);\r\n            }\r\n        }\r\n    }\r\n    --top;\r\n}\r\n\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n    \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    m = 2; int m; RD(n, m, k); DO(m){\r\n        int a, b; RD(a, b);\r\n        add_edgee(a, b);\r\n    }\r\n\r\n    if (m == n-1) TDC::gao();\r\n    else {\r\n\r\n        dfs(); ECH(c, Circle) TDC::gao(*c);\r\n\r\n        int d = 0;\r\n\r\n        ECH(c, Circle){\r\n            Scan(*c);\r\n            ECH(it, L) BIT::Add(*it-d);\r\n            ++d;\r\n        }\r\n\r\n        ECH(c, Circle){\r\n            Scan(*c);\r\n            ECH(it, L) BIT::Add(*it-d+SZ(Circle), -1);\r\n            ECH(it, L) ans += BIT::Rsum(k-d-*it);\r\n            ECH(it, L) BIT::Add(*it-d);\r\n            ++d;\r\n        }\r\n\r\n        ECH(c, Circle){\r\n            Scan(*c);\r\n            ECH(it, L) BIT::Add(*it-d+SZ(Circle), -1);\r\n            ++d;\r\n        }\r\n    }\r\n\r\n    printf("%lld\\n", ans);\r\n}\r\n\r\n<\/pre>\n
https:\/\/gist.github.com\/lychees\/6b55943725966850b1a3<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
http:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=3648 http:\/\/hi.baidu.com\/greencloud\/item\/5d009dddcecde7b133db90ad Brief description: \u7ed9\u5b9a\u4e00\u4e2a\u6811\u52a0\u4e00\u6761\u8fb9\u3002\u3002\u6c42\u8fd9\u4e2a\u56fe\u4e2d\u6240\u6709\u7ecf\u8fc7\u7ed3\u70b9\u6811 >= k \u7684\u8def\u5f84\u6709\u591a\u5c11\u7ec4\u3002\u3002 \uff08(u -> v) \u4e0e (v -> u) \u7b97\u4e00\u7ec4\u3002\u3002\uff09<\/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-1036","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-gI","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1036","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=1036"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1036\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1036"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1036"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1036"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}