{"id":533,"date":"2018-04-03T13:44:02","date_gmt":"2018-04-03T05:44:02","guid":{"rendered":"http:\/\/kylelv.com\/?p=533"},"modified":"2018-05-23T13:47:56","modified_gmt":"2018-05-23T05:47:56","slug":"bzoj-2286-sdoi2011%e6%b6%88%e8%80%97%e6%88%98-%e8%99%9a%e6%a0%91","status":"publish","type":"post","link":"https:\/\/blog.kylelv.com\/?p=533","title":{"rendered":"bzoj 2286: [Sdoi2011]\u6d88\u8017\u6218  &#8212; \u865a\u6811"},"content":{"rendered":"<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_73 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-69fdef3fe9747\" 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-69fdef3fe9747\"  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:\/\/blog.kylelv.com\/?p=533\/#2286_Sdoi2011%E6%B6%88%E8%80%97%E6%88%98\" title=\"2286: [Sdoi2011]\u6d88\u8017\u6218\">2286: [Sdoi2011]\u6d88\u8017\u6218<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/blog.kylelv.com\/?p=533\/#Description\" title=\"Description\">Description<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/blog.kylelv.com\/?p=533\/#Input\" title=\"Input\">Input<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/blog.kylelv.com\/?p=533\/#Output\" title=\"Output\">Output<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/blog.kylelv.com\/?p=533\/#Sample_Input\" title=\"Sample Input\">Sample Input<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/blog.kylelv.com\/?p=533\/#Sample_Output\" title=\"Sample Output\">Sample Output<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/blog.kylelv.com\/?p=533\/#HINT\" title=\"HINT\">HINT<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/blog.kylelv.com\/?p=533\/#Source\" title=\"Source\">Source<\/a><\/li><\/ul><\/nav><\/div>\n<h2 style=\"text-align: center;\"><span class=\"ez-toc-section\" id=\"2286_Sdoi2011%E6%B6%88%E8%80%97%E6%88%98\"><\/span>2286: [Sdoi2011]\u6d88\u8017\u6218<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p style=\"text-align: center;\">Time Limit:\u00a020 Sec\u00a0\u00a0Memory Limit:\u00a0512 MB<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Description\"><\/span>Description<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u5728\u4e00\u573a\u6218\u4e89\u4e2d\uff0c\u6218\u573a\u7531n\u4e2a\u5c9b\u5c7f\u548cn-1\u4e2a\u6865\u6881\u7ec4\u6210\uff0c\u4fdd\u8bc1\u6bcf\u4e24\u4e2a\u5c9b\u5c7f\u95f4\u6709\u4e14\u4ec5\u6709\u4e00\u6761\u8def\u5f84\u53ef\u8fbe\u3002\u73b0\u5728\uff0c\u6211\u519b\u5df2\u7ecf\u4fa6\u67e5\u5230\u654c\u519b\u7684\u603b\u90e8\u5728\u7f16\u53f7\u4e3a1\u7684\u5c9b\u5c7f\uff0c\u800c\u4e14\u4ed6\u4eec\u5df2\u7ecf\u6ca1\u6709\u8db3\u591f\u591a\u7684\u80fd\u6e90\u7ef4\u7cfb\u6218\u6597\uff0c\u6211\u519b\u80dc\u5229\u5728\u671b\u3002\u5df2\u77e5\u5728\u5176\u4ed6k\u4e2a\u5c9b\u5c7f\u4e0a\u6709\u4e30\u5bcc\u80fd\u6e90\uff0c\u4e3a\u4e86\u9632\u6b62\u654c\u519b\u83b7\u53d6\u80fd\u6e90\uff0c\u6211\u519b\u7684\u4efb\u52a1\u662f\u70b8\u6bc1\u4e00\u4e9b\u6865\u6881\uff0c\u4f7f\u5f97\u654c\u519b\u4e0d\u80fd\u5230\u8fbe\u4efb\u4f55\u80fd\u6e90\u4e30\u5bcc\u7684\u5c9b\u5c7f\u3002\u7531\u4e8e\u4e0d\u540c\u6865\u6881\u7684\u6750\u8d28\u548c\u7ed3\u6784\u4e0d\u540c\uff0c\u6240\u4ee5\u70b8\u6bc1\u4e0d\u540c\u7684\u6865\u6881\u6709\u4e0d\u540c\u7684\u4ee3\u4ef7\uff0c\u6211\u519b\u5e0c\u671b\u5728\u6ee1\u8db3\u76ee\u6807\u7684\u540c\u65f6\u4f7f\u5f97\u603b\u4ee3\u4ef7\u6700\u5c0f\u3002<\/p>\n<p>\u4fa6\u67e5\u90e8\u95e8\u8fd8\u53d1\u73b0\uff0c\u654c\u519b\u6709\u4e00\u53f0\u795e\u79d8\u673a\u5668\u3002\u5373\u4f7f\u6211\u519b\u5207\u65ad\u6240\u6709\u80fd\u6e90\u4e4b\u540e\uff0c\u4ed6\u4eec\u4e5f\u53ef\u4ee5\u7528\u90a3\u53f0\u673a\u5668\u3002\u673a\u5668\u4ea7\u751f\u7684\u6548\u679c\u4e0d\u4ec5\u4ec5\u4f1a\u4fee\u590d\u6240\u6709\u6211\u519b\u70b8\u6bc1\u7684\u6865\u6881\uff0c\u800c\u4e14\u4f1a\u91cd\u65b0\u968f\u673a\u8d44\u6e90\u5206\u5e03\uff08\u4f46\u53ef\u4ee5\u4fdd\u8bc1\u7684\u662f\uff0c\u8d44\u6e90\u4e0d\u4f1a\u5206\u5e03\u52301\u53f7\u5c9b\u5c7f\u4e0a\uff09\u3002\u4e0d\u8fc7\u4fa6\u67e5\u90e8\u95e8\u8fd8\u53d1\u73b0\u4e86\u8fd9\u53f0\u673a\u5668\u53ea\u80fd\u591f\u4f7f\u7528m\u6b21\uff0c\u6240\u4ee5\u6211\u4eec\u53ea\u9700\u8981\u628a\u6bcf\u6b21\u4efb\u52a1\u5b8c\u6210\u5373\u53ef\u3002<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Input\"><\/span>Input<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u7b2c\u4e00\u884c\u4e00\u4e2a\u6574\u6570n\uff0c\u4ee3\u8868\u5c9b\u5c7f\u6570\u91cf\u3002<\/p>\n<p>\u63a5\u4e0b\u6765n-1\u884c\uff0c\u6bcf\u884c\u4e09\u4e2a\u6574\u6570u,v,w\uff0c\u4ee3\u8868u\u53f7\u5c9b\u5c7f\u548cv\u53f7\u5c9b\u5c7f\u7531\u4e00\u6761\u4ee3\u4ef7\u4e3ac\u7684\u6865\u6881\u76f4\u63a5\u76f8\u8fde\uff0c\u4fdd\u8bc11&lt;=u,v&lt;=n\u4e141&lt;=c&lt;=100000\u3002<\/p>\n<p>\u7b2cn+1\u884c\uff0c\u4e00\u4e2a\u6574\u6570m\uff0c\u4ee3\u8868\u654c\u65b9\u673a\u5668\u80fd\u4f7f\u7528\u7684\u6b21\u6570\u3002<\/p>\n<p>\u63a5\u4e0b\u6765m\u884c\uff0c\u6bcf\u884c\u4e00\u4e2a\u6574\u6570k<sub>i<\/sub>\uff0c\u4ee3\u8868\u7b2ci\u6b21\u540e\uff0c\u6709k<sub>i<\/sub>\u4e2a\u5c9b\u5c7f\u8d44\u6e90\u4e30\u5bcc\uff0c\u63a5\u4e0b\u6765k\u4e2a\u6574\u6570h<sub>1<\/sub>,h<sub>2<\/sub>,\u2026h<sub>k<\/sub>\uff0c\u8868\u793a\u8d44\u6e90\u4e30\u5bcc\u5c9b\u5c7f\u7684\u7f16\u53f7\u3002<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Output\"><\/span>Output<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u8f93\u51fa\u6709m\u884c\uff0c\u5206\u522b\u4ee3\u8868\u6bcf\u6b21\u4efb\u52a1\u7684\u6700\u5c0f\u4ee3\u4ef7\u3002<\/p>\n<p>&nbsp;<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Sample_Input\"><\/span>Sample Input<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>10<br \/>\n1 5 13<br \/>\n1 9 6<br \/>\n2 1 19<br \/>\n2 4 8<br \/>\n2 3 91<br \/>\n5 6 8<br \/>\n7 5 4<br \/>\n7 8 31<br \/>\n10 7 9<br \/>\n3<br \/>\n2 10 6<br \/>\n4 5 7 8 3<br \/>\n3 9 4 6<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Sample_Output\"><\/span>Sample Output<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>12<br \/>\n32<br \/>\n22<\/p>\n<h2><span class=\"ez-toc-section\" id=\"HINT\"><\/span>HINT<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u5bf9\u4e8e100%\u7684\u6570\u636e\uff0c2&lt;=n&lt;=250000,m&gt;=1,sigma(ki)&lt;=500000,1&lt;=ki&lt;=n-1<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Source\"><\/span>Source<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u865a\u6811\u7b2c\u4e00\u9898\uff0c\uff0c<\/p>\n<p>\u4e00\u4e2a\u5f88\u597d\u7684\u865a\u6811\u5b66\u4e60\u8bb2\u89e3\u00a0<a href=\"https:\/\/blog.sengxian.com\/algorithms\/virtual-tree\" target=\"_blank\" rel=\"noopener\">https:\/\/blog.sengxian.com\/algorithms\/virtual-tree<\/a><\/p>\n<p>\u5efa\u865a\u6811\u7136\u540e\u5c31\u76f4\u63a5dp\u5373\u53ef<\/p>\n<p>&nbsp;<\/p>\n<pre class=\"lang:c++ decode:true \">#include&lt;map&gt;\r\n#include&lt;cmath&gt;\r\n#include&lt;queue&gt;\r\n#include&lt;cstdio&gt;\r\n#include&lt;string&gt;\r\n#include&lt;cstring&gt;\r\n#include&lt;iostream&gt;\r\n#include&lt;algorithm&gt;\r\nusing namespace std;\r\n#define inf 1000000007\r\n#define ll long long\r\n#define N 500010\r\ninline int rd()\r\n{\r\n\tint x=0,f=1;char ch=getchar();\r\n\twhile(ch&lt;'0'||ch&gt;'9'){if(ch=='-')f=-1;ch=getchar();}\r\n\twhile(ch&gt;='0'&amp;&amp;ch&lt;='9'){x=x*10+ch-'0';ch=getchar();}\r\n\treturn x*f;\r\n}\r\nint lj[N],fro[N],to[N],cnt;\r\nll v[N];\r\nvoid add(int a,int b,int c){fro[++cnt]=lj[a];to[cnt]=b;lj[a]=cnt;v[cnt]=c;}\r\nint n,m;\r\nint dfn[N],tim;\r\nbool cmp(int a,int b){return dfn[a]&lt;dfn[b];}\r\nint Fa[N][21],dep[N];\r\nll mn[N];\r\nvoid dfs(int x,int f)\r\n{\r\n\tdfn[x]=++tim;\r\n\tFa[x][0]=f;dep[x]=dep[f]+1;\r\n\tfor(int i=1;i&lt;21;i++) Fa[x][i]=Fa[Fa[x][i-1]][i-1];\r\n\tll tp=0;\r\n\tfor(int i=lj[x];i;i=fro[i])\r\n\t{\r\n\t\tif(to[i]==f) continue;\r\n\t\tmn[to[i]]=min(mn[x],v[i]);\r\n\t\tdfs(to[i],x);\r\n\t}\r\n}\r\nint sq[N],k;\r\nint LCA(int a,int b)\r\n{\r\n\tif(dep[a]&lt;dep[b]) swap(a,b);\r\n\tfor(int i=20;i&gt;=0;i--) if(dep[Fa[a][i]]&gt;=dep[b]) a=Fa[a][i];\r\n\tif(a==b) return a;\r\n\tfor(int i=20;i&gt;=0;i--) if(Fa[a][i]^Fa[b][i]) a=Fa[a][i],b=Fa[b][i];\r\n\treturn Fa[a][0];\r\n}\r\nint q[N],tq;\r\nbool us[N];\r\nvoid build()\r\n{\r\n\tfor(int i=1;i&lt;=k;i++) lj[sq[i]]=0;cnt=0;\r\n\tsort(sq+1,sq+k+1,cmp);\r\n\tq[tq=1]=1;lj[1]=0;\r\n\tint lca;\r\n\tfor(int i=1,x;i&lt;=k;i++)\r\n\t{\r\n\t\tx=sq[i];\r\n\t\tlca=LCA(q[tq],x);\r\n\t\tif(q[tq]==lca){q[++tq]=x;continue;}\r\n\t\twhile(dep[q[tq-1]]&gt;=dep[lca])\r\n\t\t\tadd(q[tq-1],q[tq],0),tq--;\r\n\t\tif(lca^q[tq])\r\n\t\t{\r\n\t\t\tlj[lca]=0;\r\n\t\t\tadd(lca,q[tq--],0);\r\n\t\t\tq[++tq]=lca;\r\n\t\t}\r\n\t\tq[++tq]=x;\r\n\t}\r\n\tfor(int i=1;i&lt;tq;i++) add(q[i],q[i+1],0);\r\n}\r\nll f[N];\r\nvoid dfs(int x)\r\n{\r\n\tf[x]=mn[x];\r\n\tif(!lj[x]) return;\r\n\tll tmp=0;\r\n\tfor(int i=lj[x];i;i=fro[i])\r\n\t{\r\n\t\tdfs(to[i]);\r\n\t\ttmp+=f[to[i]];\r\n\t}\r\n\tif(!us[x]) f[x]=min(f[x],tmp);\r\n}\r\nint main()\r\n{\r\n\tn=rd();\r\n\tfor(int i=1,x,y,z;i&lt;n;i++)\r\n\t{\r\n\t\tx=rd();y=rd();z=rd();\r\n\t\tadd(x,y,z);add(y,x,z);\r\n\t}\r\n\tmn[1]=(ll)inf*inf;\r\n\tdfs(1,0);\r\n\tm=rd();\r\n\twhile(m--)\r\n\t{\r\n\t\tk=rd();\r\n\t\tfor(int i=1;i&lt;=k;i++) sq[i]=rd(),us[sq[i]]=1;\r\n\t\tbuild();\r\n\t\tdfs(1);\r\n\t\tprintf(\"%lld\\n\",f[1]);\r\n\t\tfor(int i=1;i&lt;=k;i++) us[sq[i]]=0;\r\n\t}\r\n\treturn 0;\r\n}<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>2286: [Sdoi2011]\u6d88\u8017\u6218 Time Limit:\u00a020 Sec\u00a0\u00a0Memory Limit:\u00a05 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[58],"class_list":["post-533","post","type-post","status-publish","format-standard","hentry","category-bzoj","tag-58"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/533","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=533"}],"version-history":[{"count":1,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/533\/revisions"}],"predecessor-version":[{"id":534,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/533\/revisions\/534"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=533"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=533"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=533"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}