{"id":123,"date":"2018-08-01T10:22:55","date_gmt":"2018-08-01T10:22:55","guid":{"rendered":"http:\/\/bytew.net\/?p=123"},"modified":"2021-09-08T20:20:07","modified_gmt":"2021-09-08T12:20:07","slug":"bzoj3697-%e9%87%87%e8%8d%af%e4%ba%ba%e7%9a%84%e8%b7%af%e5%be%84","status":"publish","type":"post","link":"https:\/\/bytew.net\/?p=123","title":{"rendered":"[BZOJ3697] \u91c7\u836f\u4eba\u7684\u8def\u5f84"},"content":{"rendered":"

\u91c7\u836f\u4eba\u7684\u836f\u7530\u662f\u4e00\u4e2a\u6811\u72b6\u7ed3\u6784\uff0c\u6bcf\u6761\u8def\u5f84\u4e0a\u90fd\u79cd\u690d\u7740\u540c\u79cd\u836f\u6750\u3002\u91c7\u836f\u4eba\u4ee5\u81ea\u5df1\u5bf9\u836f\u6750\u72ec\u5230\u7684\u89c1\u89e3\uff0c\u5bf9\u6bcf\u79cd\u836f\u6750\u8fdb\u884c\u4e86\u5206\u7c7b\u3002\u5927\u81f4\u5206\u4e3a\u4e24\u7c7b\uff0c\u4e00\u79cd\u662f\u9634\u6027\u7684\uff0c\u4e00\u79cd\u662f\u9633\u6027\u7684\u3002\u91c7\u836f\u4eba\u6bcf\u5929\u90fd\u8981\u8fdb\u884c\u91c7\u836f\u6d3b\u52a8\u3002\u4ed6\u9009\u62e9\u7684\u8def\u5f84\u662f\u5f88\u6709\u8bb2\u7a76\u7684\uff0c\u4ed6\u8ba4\u4e3a\u9634\u9633\u5e73\u8861\u662f\u5f88\u91cd\u8981\u7684\uff0c\u6240\u4ee5\u4ed6\u8d70\u7684\u4e00\u5b9a\u662f\u4e24\u79cd\u836f\u6750\u6570\u76ee\u76f8\u7b49\u7684\u8def\u5f84\u3002\u91c7\u836f\u5de5\u4f5c\u662f\u5f88\u8f9b\u82e6\u7684\uff0c\u6240\u4ee5\u4ed6\u5e0c\u671b\u4ed6\u9009\u51fa\u7684\u8def\u5f84\u4e2d\u6709\u4e00\u4e2a\u53ef\u4ee5\u4f5c\u4e3a\u4f11\u606f\u7ad9\u7684\u8282\u70b9\uff08\u4e0d\u5305\u62ec\u8d77\u70b9\u548c\u7ec8\u70b9\uff09\uff0c\u6ee1\u8db3\u8d77\u70b9\u5230\u4f11\u606f\u7ad9\u548c\u4f11\u606f\u7ad9\u5230\u7ec8\u70b9\u7684\u8def\u5f84\u4e5f\u662f\u9634\u9633\u5e73\u8861\u7684\u3002\u4ed6\u60f3\u77e5\u9053\u4ed6\u4e00\u5171\u53ef\u4ee5\u9009\u62e9\u591a\u5c11\u79cd\u4e0d\u540c\u7684\u8def\u5f84\u3002<\/p><\/blockquote>\n

\u5982XHT\u5927\u4f6c\u6240\u8bf4\uff0c\u8fd9\u662f\u70b9\u5206\u6cbb\u88f8\u9898\u4e00\u4e2a\u3002<\/p>\n

<\/p>\n

\u70b9\u5206\u6cbb\uff0c\u5219\u95ee\u9898\u5c31\u53d8\u6210\u6c42\u8fc7\u6839\u6ee1\u8db3\u6761\u4ef6\u7684\u8def\u5f84\u6570\u3002<\/p>\n

\u8def\u5f84\u4e0a\u7684\u4f11\u606f\u7ad9\u4e00\u5b9a\u662f\u5728\u8d77\u70b9\u5230\u6839\u7684\u8def\u5f84\u4e0a\uff0c\u6216\u8005\u6839\u5230\u7ec8\u70b9\u7684\u8def\u5f84\u4e0a\u3002<\/p>\n

\u5982\u4f55\u5224\u65ad\u4e00\u6761\u4ece\u6839\u51fa\u53d1\u7684\u8def\u5f84\u662f\u5426\u5305\u542b\u4f11\u606f\u7ad9\uff1f\u53ea\u8981\u5728dfs\u4e2d\u8bb0\u5f55\u4e0b\u8fd9\u6761\u8def\u5f84\u7684\u548cx\uff0c\u540c\u65f6\u7528\u4e2a\u6807\u5fd7\u6570\u7ec4\u5224\u65ad\u8fd9\u6761\u8def\u5f84\u662f\u5426\u5b58\u5728\u524d\u7f00\u548c\u4e3ax\u7684\u8282\u70b9\u3002<\/p>\n

\u679a\u4e3e\u6839\u8282\u70b9\u7684\u6bcf\u4e2a\u5b50\u6811\u3002\u7528f[i][0\/1]\uff0cg[i][0\/1]\u5206\u522b\u8868\u793a\u524d\u9762\u51e0\u4e2a\u5b50\u6811\u4ee5\u53ca\u5f53\u524d\u5b50\u6811\u548c\u4e3ai\u7684\u8def\u5f84\u6570\u76ee\uff0c0\u548c1\u7528\u4e8e\u533a\u5206\u8def\u5f84\u4e0a\u662f\u5426\u5b58\u5728\u524d\u7f00\u548c\u4e3ai\u7684\u8282\u70b9\u3002\u90a3\u4e48\u5f53\u524d\u5b50\u6811\u7684\u8d21\u732e\u5c31\u662f<\/p>\n

  <\/span>   <\/span>\"\[\sum_{i=-d}^d f [i][0] * g [-i][1] + f[i][1] * (g[-i][0] + g[-i][1])\]\"<\/p>\n

\u5176\u4e2dd\u4e3a\u5f53\u524d\u5b50\u6811\u7684\u6df1\u5ea6\u3002\u7136\u540e\u518d\u52a0\u4e0a<\/p>\n

  <\/span>   <\/span>\"\[f[0][0] * g[0][0] + f[0][1]\]\"<\/p>\n

\uff08\u5f53\u524d\u6839\u4f5c\u4e3a\u4f11\u606f\u70b9\/\u5f53\u524d\u6839\u4f5c\u4e3a\u7aef\u70b9\u7684\u60c5\u51b5\uff09<\/p>\n

\u8fd9\u6837\u590d\u6742\u5ea6\u5c31\u4e3a n log n\u3002<\/p>\n

\u4e3a\u5565\u8981\u5199\u535a\u5ba2\uff1f\u8c03\u9898\u592a\u75db\u82e6\u4e86\uff0c\u8fd9\u9898\u8c03\u4e863\u5c0f\u65f6<\/strong>\uff0c\u5728XHT\u5e2e\u52a9\u4e0b\u77e5\u9053\u662f\u6570\u7ec4\u5f00\u5c0f\u4e86\uff0c\u8981\u8bb0\u5f55\u4e0b\u6765\uff0c\u4ee5\u540e\u5c11\u51fa\u9519\u3002<\/p>\n

\/\/ Author : WangZhikun\n\/\/ Date   : 2018.07.31\n#include <cstdio>\n#include <vector>\n#include <iostream>\n#define PII pair<ll,ll>\n#define MP make_pair\n#define PB push_back\n#define FF first\n#define SS second\n#define N 110000\nusing namespace std;\ntypedef long long ll;\n\nll n,u,v,w,rt,ctsz,ans;\nll kgb[200020] = {0},sz[200020] = {0},ccv[200020] = {0},mx[200020],ddd[220010][2] = {0},kkk[220010][2],depth[200020],mdepth[200020];\nvector<PII> G[200020];\n\nvoid dfs1(ll num,ll fa){\n\tsz[num] = 1;mx[num]=0;\n\tfor(ll i=0;i<G[num].size();i++){\n\t\tll ct = G[num][i].FF;\n\t\tif(kgb[ct]||ct == fa)continue;\n\t\tdfs1(ct,num);\n\t\tsz[num]+=sz[ct];\n\t\tmx[num] = max(mx[num],sz[ct]);\n\t}\n\tmx[num] = max(mx[num],ctsz-sz[num]);\n\tif(mx[num]<mx[rt])rt = num;\n}\nvoid dfs2(ll num,ll fa,ll x){\n\tif(ccv[x]>0)ddd[x][1]+=1;\n\telse ddd[x][0]+=1;\n\tccv[x]+=1;\n\tsz[num] = 1;\n\tfor(PII ech:G[num]){\n\t\tll ct = ech.FF;if(kgb[ct]||ct == fa)continue;\n\t\tdfs2(ct,num,x+ech.SS);\n\t\tsz[num]+=sz[ct];\n\t}\n\tccv[x]-=1;\n}\nvoid dfs3(ll num,ll fa){\n\tmdepth[num] = depth[num];\n\tsz[num] = 1;\n\tfor(PII ech:G[num]){\n\t\tll ct = ech.FF;if(kgb[ct]||ct == fa)continue;\n\t\tdepth[ct] = depth[num]+1;\n\t\tdfs3(ct,num);\n\t\tsz[num]+=sz[ct];\n\t\tmdepth[num] = max(mdepth[num],mdepth[ct]);\n\t}\n}\nvoid solve(ll num){\n\trt = 100005;mx[rt] = 10000005;\n\tdfs1(num,-1);\n\tdepth[rt] = 0;\n\tdfs3(rt,-1);\n\tkgb[rt] = 1;\n\tfor(ll i = N-mdepth[rt];i<=N+mdepth[rt];i++)kkk[i][0] = kkk[i][1] = 0;\n\tfor(auto ech:G[rt]){\n\t\tll ct = ech.FF;\n\t\tif(kgb[ct])continue;\n\t\tdfs2(ct,rt,N+ech.SS);\n\t\tans+=ddd[N][0]*kkk[N][0];\n\t\tans+=ddd[N][1];\n\t\tfor(ll i = -mdepth[ct];i<=+mdepth[ct];i++){\n\t\t\tans+=ddd[i+N][0]*kkk[-i+N][1]+ddd[i+N][1]*kkk[-i+N][0]+ddd[i+N][1]*kkk[N-i][1];\n\t\t}\n\t\tfor(ll i = N-mdepth[ct];i<=N+mdepth[ct];i++){\n\t\t\tkkk[i][0]+=ddd[i][0];\n\t\t\tkkk[i][1]+=ddd[i][1];\n\t\t\tddd[i][0] = ddd[i][1] = 0;\n\t\t}\n\t}\n\tfor(auto ech:G[rt]){\n\t\tif(kgb[ech.FF])continue;\n\t\tif(sz[ech.FF]>=5){\n\t\t\tctsz = sz[ech.FF];\n\t\t\tsolve(ech.FF);\n\t\t}\n\t}\n}\nint main(){\n\tcin>>n;\n\tfor(ll i=1;i<n;i++){\n\t\tcin>>u>>v>>w;\n\t\tif(!w)w=-1;\n\t\tG[u].PB(MP(v,w));\n\t\tG[v].PB(MP(u,w));\n\t}\n\tctsz = n;solve(1);\n\tcout<<ans<<endl;;\n\treturn 0;\n}\n<\/pre>\n
[latex]<\/p>\n ","protected":false},"excerpt":{"rendered":"
\u91c7\u836f\u4eba\u7684\u836f\u7530\u662f\u4e00\u4e2a\u6811\u72b6\u7ed3\u6784\uff0c\u6bcf\u6761\u8def\u5f84\u4e0a\u90fd\u79cd\u690d\u7740\u540c\u79cd\u836f\u6750\u3002\u91c7\u836f\u4eba\u4ee5\u81ea\u5df1\u5bf9\u836f\u6750\u72ec\u5230\u7684\u89c1\u89e3\uff0c\u5bf9\u6bcf\u79cd\u836f\u6750\u8fdb\u884c\u4e86\u5206\u7c7b\u3002\u5927 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2,5],"tags":[],"_links":{"self":[{"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/posts\/123"}],"collection":[{"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/bytew.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=123"}],"version-history":[{"count":1,"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/posts\/123\/revisions"}],"predecessor-version":[{"id":770,"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/posts\/123\/revisions\/770"}],"wp:attachment":[{"href":"https:\/\/bytew.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=123"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/bytew.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=123"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/bytew.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=123"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}