{"id":441,"date":"2017-04-12T08:18:36","date_gmt":"2017-04-12T00:18:36","guid":{"rendered":"http:\/\/kylelv.com\/?p=441"},"modified":"2018-01-03T18:20:26","modified_gmt":"2018-01-03T10:20:26","slug":"bzoj-3872-poi2014ant-colony-%e6%a0%91%e5%bd%a2dp%e4%ba%8c%e5%88%86","status":"publish","type":"post","link":"https:\/\/blog.kylelv.com\/?p=441","title":{"rendered":"bzoj 3872: [Poi2014]Ant colony  &#8212; \u6811\u5f62dp+\u4e8c\u5206"},"content":{"rendered":"<p>&nbsp;<\/p>\n<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-69fdef1c3233e\" 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-69fdef1c3233e\"  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=441\/#3872_Poi2014Ant_colony\" title=\"3872: [Poi2014]Ant colony\">3872: [Poi2014]Ant colony<\/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=441\/#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=441\/#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=441\/#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=441\/#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=441\/#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=441\/#HINT\" title=\"HINT\">HINT<\/a><\/li><\/ul><\/nav><\/div>\n<h2 style=\"text-align: center;\"><span class=\"ez-toc-section\" id=\"3872_Poi2014Ant_colony\"><\/span>3872: [Poi2014]Ant colony<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p style=\"text-align: center;\"><span class=\"green\">Time Limit:\u00a030 Sec\u00a0\u00a0Memory Limit:\u00a0128 MB<\/span><\/p>\n<h2><span class=\"ez-toc-section\" id=\"Description\"><\/span>Description<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<div><\/div>\n<div>There is an entrance to the ant hill in every chamber with only one corridor leading into (or out of) it. At each entry, there are g groups of m1,m2,&#8230;,mg ants respectively. These groups will enter the ant hill one after another, each successive group entering once there are no ants inside. Inside the hill, the ants explore it in the following way:<\/div>\n<div>Upon entering a chamber with d outgoing corridors yet unexplored by the group, the group divides into d groups of equal size. Each newly created group follows one of the d corridors. If d=0, then the group exits the ant hill.<\/div>\n<div>If the ants cannot divide into equal groups, then the stronger ants eat the weaker until a perfect division is possible. Note that such a division is always possible since eventually the number of ants drops down to zero. Nothing can stop the ants from allowing divisibility &#8211; in particular, an ant can eat itself, and the last one remaining will do so if the group is smaller than d.<\/div>\n<div>The following figure depicts m ants upon entering a chamber with three outgoing unexplored corridors, dividing themselves into three (equal) groups of floor(m\/3) ants each.<\/div>\n<div>A hungry anteater dug into one of the corridors and can now eat all the ants passing through it. However, just like the ants, the anteater is very picky when it comes to numbers. It will devour a passing group if and only if it consists of exactly k ants. We want to know how many ants the anteater will eat.<\/div>\n<div>\n<div>\u7ed9\u5b9a\u4e00\u68f5\u6709n\u4e2a\u8282\u70b9\u7684\u6811\u3002\u5728\u6bcf\u4e2a\u53f6\u5b50\u8282\u70b9\uff0c\u6709g\u7fa4\u8682\u8681\u8981\u4ece\u5916\u9762\u8fdb\u6765\uff0c\u5176\u4e2d\u7b2ci\u7fa4\u6709m[i]\u53ea\u8682\u8681\u3002\u8fd9\u4e9b\u8682\u8681\u4f1a\u76f8\u7ee7\u8fdb\u5165\u6811\u4e2d\uff0c\u800c\u4e14\u8981\u4fdd\u8bc1\u6bcf\u4e00\u65f6\u523b\u6bcf\u4e2a\u8282\u70b9\u6700\u591a\u53ea\u6709\u4e00\u7fa4\u8682\u8681\u3002\u8fd9\u4e9b\u8682\u8681\u4f1a\u6309\u4ee5\u4e0b\u65b9\u5f0f\u524d\u8fdb\uff1a<\/div>\n<div>\u00b7\u5728\u5373\u5c06\u79bb\u5f00\u67d0\u4e2a\u5ea6\u6570\u4e3ad+1\u7684\u70b9\u65f6\uff0c\u8be5\u7fa4\u8682\u8681\u6709d\u4e2a\u65b9\u5411\u8fd8\u6ca1\u6709\u8d70\u8fc7\uff0c\u8fd9\u7fa4\u8682\u8681\u5c31\u4f1a\u5206\u88c2\u6210d\u7fa4\uff0c\u6bcf\u7fa4\u6570\u91cf\u90fd\u76f8\u7b49\u3002\u5982\u679cd=0\uff0c\u90a3\u4e48\u8682\u8681\u4f1a\u79bb\u5f00\u8fd9\u68f5\u6811\u3002<\/div>\n<div>\u00b7\u5982\u679c\u8682\u8681\u4e0d\u80fd\u7b49\u5206\uff0c\u90a3\u4e48\u8682\u8681\u4e4b\u95f4\u4f1a\u4e92\u76f8\u541e\u566c\uff0c\u76f4\u5230\u53ef\u4ee5\u7b49\u5206\u4e3a\u6b62\uff0c\u5373\u4e00\u7fa4\u8682\u8681\u6709m\u53ea\uff0c\u8981\u5206\u6210d\u7ec4\uff0c\u6bcf\u7ec4\u5c06\u4f1a\u6709floor(m\/d)\u53ea\uff0c\u5982\u4e0b\u56fe\u3002<\/div>\n<\/div>\n<div><\/div>\n<div>\n<div><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-medium wp-image-442\" src=\"http:\/\/kylelv.com\/wp-content\/uploads\/2018\/01\/s-300x224.png\" alt=\"\" width=\"300\" height=\"224\" srcset=\"https:\/\/blog.kylelv.com\/wp-content\/uploads\/2018\/01\/s-300x224.png 300w, https:\/\/blog.kylelv.com\/wp-content\/uploads\/2018\/01\/s.png 305w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/div>\n<div>\u4e00\u53ea\u9965\u997f\u7684\u98df\u8681\u517d\u57cb\u4f0f\u5728\u4e00\u6761\u8fb9\u4e0a\uff0c\u5982\u679c\u6709\u4e00\u7fa4\u8682\u8681\u901a\u8fc7\u8fd9\u6761\u8fb9\uff0c\u5e76\u4e14\u6570\u91cf\u6070\u4e3ak\u53ea\uff0c\u5b83\u5c31\u4f1a\u541e\u6389\u8fd9\u7fa4\u8682\u8681\u3002\u8bf7\u8ba1\u7b97\u4e00\u5171\u6709\u591a\u5c11\u53ea\u8682\u8681\u4f1a\u88ab\u541e\u6389\u3002<\/div>\n<div><\/div>\n<\/div>\n<p>&nbsp;<\/p>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"Input\"><\/span>Input<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<div>The first line of the standard input contains three integers n, g, k (2&lt;=n,g&lt;=1000000, 1&lt;=k&lt;=10^9), separated by single spaces. These specify the number of chambers, the number of ant groups and the number of ants the anteater devours at once. The chambers are numbered from 1 to n.<\/div>\n<div>The second line contains g integers m[1],m[2],&#8230;,m[g](1&lt;=m[i]&lt;=10^9), separated by single spaces, where m[i] gives the number of ants in the i-th group at every entrance to the ant hill. The n-1 lines that follow describe the corridors within the ant hill; the i-th such line contains two integers a[i],b[i] (1&lt;=a[i],b[i]&lt;=n), separated by a single space, that indicate that the chambers no.a[i] and b[i] are linked by a corridor. The anteater has dug into the corridor that appears first on input.<\/div>\n<div>\u7b2c\u4e00\u884c\u5305\u542b\u4e09\u4e2a\u6574\u6570n,g,k,\u8868\u793a\u70b9\u6570\u3001\u8682\u8681\u7fa4\u6570\u4ee5\u53cak\u3002<\/div>\n<div>\u7b2c\u4e8c\u884c\u5305\u542bg\u4e2a\u6574\u6570m[1],m[2],&#8230;,m[g]\uff0c\u8868\u793a\u6bcf\u7fa4\u8682\u8681\u4e2d\u8682\u8681\u7684\u6570\u91cf\u3002<\/div>\n<div>\u63a5\u4e0b\u6765n-1\u884c\u6bcf\u884c\u4e24\u4e2a\u6574\u6570\uff0c\u8868\u793a\u4e00\u6761\u8fb9\uff0c\u98df\u8681\u517d\u57cb\u4f0f\u5728\u8f93\u5165\u7684\u7b2c\u4e00\u6761\u8fb9\u4e0a\u3002<\/div>\n<div><\/div>\n<p>&nbsp;<\/p>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"Output\"><\/span>Output<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<div>Your program should print to the standard output a single line containing a single integer: the number of ants eaten by the anteater.<\/div>\n<div>\u4e00\u4e2a\u6574\u6570\uff0c\u5373\u98df\u8681\u517d\u80fd\u5403\u6389\u7684\u8682\u8681\u7684\u6570\u91cf\u3002<\/div>\n<div><\/div>\n<p>&nbsp;<\/p>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"Sample_Input\"><\/span>Sample Input<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\"><span class=\"sampledata\">7 5 3<br \/>\n3 4 1 9 11<br \/>\n1 2<br \/>\n1 4<br \/>\n4 3<br \/>\n4 5<br \/>\n4 6<br \/>\n6 7<\/span><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Sample_Output\"><\/span>Sample Output<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\"><span class=\"sampledata\">21<\/span><\/div>\n<h2><span class=\"ez-toc-section\" id=\"HINT\"><\/span>HINT<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u663e\u7136\u5f97\u4ece\u90a3\u6761\u5173\u952e\u8fb9\u5012\u7740\u63a8<\/p>\n<p>\u4ee5\u8fd9\u6761\u8fb9\u4f5c\u4e3a\u8fd9\u68f5\u6811\u7684\u201c\u6839\u201d\uff0c\u5f00\u59cb\u904d\u5386\u5176\u4ed6\u7684\u8fb9\uff0c\u904d\u5386\u5230\u6bcf\u6761\u8fb9\u7684\u65f6\u5019\u8ba1\u7b97\u4e00\u4e0b\u201c\u5230\u8fd9\u6761\u8fb9\u65f6\u8fd9\u7fa4\u8682\u8681\u4f1a\u88ab\u5403\u6389\u201d\u7684\u5f53\u65f6\u8682\u8681\u6570\u91cf\u4e0a\u9650\u548c\u4e0b\u9650<\/p>\n<p>\u7136\u540e\u5bf9\u4e8e\u6bcf\u4e2a\u53f6\u5b50\u8282\u70b9\u7684\u90a3\u4e9b\u8fb9\uff0c\u4e8c\u5206\u4e00\u4e0b\u6709\u591a\u5c11\u7ec4\u8682\u8681\u4f1a\u88ab\u5403\u6389\u5c31\u597d\u4e86<\/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;cstring&gt;\r\n#include&lt;iostream&gt;\r\n#include&lt;algorithm&gt;\r\nusing namespace std;\r\n#define ll long long\r\n#define N 1000010\r\ninline int read()\r\n{\r\n    int x=0,f=1;char ch=getchar();\r\n    while(ch&lt;'0'||ch&gt;'9'){if(ch=='-')f=-1;ch=getchar();}\r\n    while(ch&gt;='0'&amp;&amp;ch&lt;='9'){x=x*10+ch-'0';ch=getchar();}\r\n    return x*f;\r\n}\r\nll lj[N],fro[N&lt;&lt;1],to[N&lt;&lt;1],du[N],cnt,s1,s2;\r\ninline void add(int a,int b){to[++cnt]=b;fro[cnt]=lj[a];lj[a]=cnt;du[a]++;}\r\nll mn[N],mx[N],n,g,k,m[N],u,v,ans;\r\nvoid dfs(int x,int f)\r\n{\r\n    int v;\r\n    for(int i=lj[x];i;i=fro[i])\r\n    {\r\n        v=to[i];\r\n        if(v==f) continue;\r\n        mn[v]=mn[x]*(du[x]-1);\r\n        mx[v]=mx[x]*(du[x]-1)+du[x]-2;\r\n        mx[v]=min(mx[v],m[g]);\r\n        if(mn[v]&lt;=m[g]) dfs(v,x);\r\n    }\r\n}\r\nll cal(ll x)\r\n{\r\n    ll L=1,R=g+1,mid;\r\n    while(L&lt;R)\r\n    {\r\n        mid=(L+R)&gt;&gt;1;\r\n        if(m[mid]&lt;=x) L=mid+1;\r\n        else R=mid;\r\n    }\r\n    return L-1;\r\n}\r\nint main()\r\n{\r\n    n=read();g=read();k=read();\r\n    for(int i=1;i&lt;=g;i++) m[i]=read();\r\n    sort(m+1,m+g+1);\r\n    s1=read();s2=read();\r\n    add(s1,s2);add(s2,s1);\r\n    for(int i=2;i&lt;n;i++)\r\n    {\r\n        u=read();v=read();\r\n        add(u,v);add(v,u);\r\n    }\r\n    mn[s1]=mn[s2]=mx[s1]=mx[s2]=k;\r\n    dfs(s1,s2);dfs(s2,s1);\r\n    for(int i=1;i&lt;=n;i++) if(du[i]==1) ans+=cal(mx[i])-cal(mn[i]-1);\r\n    printf(\"%lld\\n\",ans*k);\r\n    return 0;\r\n}<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>&nbsp; 3872: [Poi2014]Ant colony Time Limit:\u00a030 Sec\u00a0\u00a0Me [&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":[5,11,47],"class_list":["post-441","post","type-post","status-publish","format-standard","hentry","category-bzoj","tag-dp","tag-11"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/441","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=441"}],"version-history":[{"count":2,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/441\/revisions"}],"predecessor-version":[{"id":444,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/441\/revisions\/444"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=441"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=441"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=441"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}