{"id":862,"date":"2019-04-11T15:39:03","date_gmt":"2019-04-11T07:39:03","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=862"},"modified":"2019-04-12T15:51:38","modified_gmt":"2019-04-12T07:51:38","slug":"lp4582-fjoi2014-%e6%a0%91%e7%9a%84%e9%87%8d%e5%bf%83","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2019\/04\/11\/lp4582-fjoi2014-%e6%a0%91%e7%9a%84%e9%87%8d%e5%bf%83\/","title":{"rendered":"lp4582 FJOI2014 \u6811\u7684\u91cd\u5fc3"},"content":{"rendered":"\n<p>\u4e24\u4e2a\u91cd\u5fc3\u7684\u60c5\u51b5\u60f3\u60f3\u90fd\u9ebb\u3002\u6211\u4eec\u9996\u5148\u8003\u8651\u4e00\u4e2a\u91cd\u5fc3\u7684\u60c5\u51b5\u3002\n\u6211\u4eec\u628a\n\u5047\u8bbe\u6211\u4eec\u73b0\u5728\u5df2\u7ecf\u6c42\u51fa\u4e86\u6bcf\u4e2a\u5b50\u6811\u7684\u5927\u5c0f\uff0c\u90a3\u4e48\u6211\u4eec\u53d1\u73b0\uff0c\u4e00\u68f5\u5b50\u6811\u6709\u4e14\u4ec5\u6709\u5b83\u7684\u5927\u5c0f\u662f\u5bf9\u7b54\u6848\u6709\u5f71\u54cd\u7684\u3002\u6240\u4ee5\u6211\u4eec\u53ef\u4ee5\u9884\u5904\u7406\u51fa\u6bcf\u68f5\u5b50\u6811\u7684\u4e0d\u540c\u5927\u5c0f\u7684\u8054\u901a\u7ed3\u6784\u6570\uff0c\u7136\u540e\u679a\u4e3e\u5b50\u6811\u5927\u5c0f\u778e\u7edf\u8ba1\u4e00\u4e0b\u3002\n\u90a3\u4e48\u60f3\u60f3\u8981\u600e\u4e48\u9884\u5904\u7406\u3002\u6211\u4eec\u4ee4\\(f_{i,j}\\)\u8868\u793a\u4ee5\\(i\\)\u4e3a\u6839\u8282\u70b9\u7684\u5b50\u6811\u4e2d\u9009\u53d6\\(j\\)\u4e2a\u8282\u70b9\u7684\u8054\u901a\u5b50\u6811\u7684\u4e2a\u6570\uff0c\\(g_{i,j}\\)\u8868\u793a\u5f53\u524d\u5b50\u6811\u524d\\(i\\)\u4e2a\u513f\u5b50\u9009\u53d6\\(j\\)\u4e2a\u7684\u8054\u901a\u5b50\u6811\u7684\u4e2a\u6570\u3002\n\u90a3\u4e48\uff0c\u6839\u636e\u5b9a\u4e49\u6211\u4eec\u6709\uff1a\n$$g_{nw,j}=\\sum_{k=1}^{j}g_{nw-1,k}f_{v,j-k}$$\n$$f_{X,i}=g_{sum\\_of\\_sons,i-1}$$\n\u7136\u540e\u6811\u5f62DP\u5373\u53ef\u3002\n\u4ed4\u7ec6\u60f3\u60f3\uff0c\u5982\u679c\u6709\u4e24\u4e2a\u91cd\u5fc3\uff0c\u90a3\u4e48\u628a\u4e24\u4e2a\u91cd\u5fc3\u7684\u8fde\u8fb9\u65ad\u5f00\uff0c\u4e24\u8fb9\u7684\u7b54\u6848\u7684\u7edf\u8ba1\u662f\u4e92\u4e0d\u5e72\u6270\u7684\u3002\n\u6545\u800c\u6211\u4eec\u53ef\u4ee5\u5c06\u539f\u6811\u5206\u6210\u4e24\u68f5\u6811\u7edf\u8ba1\u7b54\u6848\uff0c\u518d\u628a\u7b54\u6848\u76f8\u4e58\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;iostream>\n#include&lt;cstdio>\n#include&lt;cstring>\n#include&lt;algorithm>\n#include&lt;queue>\n#include&lt;vector>\nusing namespace std;\n#define Fv(A,X) for(int A=h[X];A;A=e[A].nxt)\n\nconst int MOD=10007;\nconst int INF=0x3f3f3f3f;\ninline int Max(int A,int B){\n\treturn A>B?A:B;\n}\ninline int Min(int A,int B){\n\treturn A&lt;B?A:B;\n}\nstruct ee{\n\tint v;\n\tint nxt;\n}e[404];\nint h[205],et=0;\ninline void Eadd(int U,int V){\n\te[++et]=(ee){V,h[U]};\n\th[U]=et;\n}\ninline void add(int U,int V){\n\tEadd(U,V);\n\tEadd(V,U);\n}\nint sz[205],mx[205],rt=0,rt2=0,totsz,Tid=0,n;\ninline void dfs0(int X,int FA){\n\tsz[X]=1;mx[X]=0;\n\tFv(i,X){\n\t\tif(e[i].v==FA){\n\t\t\tcontinue;\n\t\t}\n\t\tdfs0(e[i].v,X);\n\t\tsz[X]+=sz[e[i].v];\n\t\tmx[X]=Max(mx[X],sz[e[i].v]);\n\t}\n\tmx[X]=Max(mx[X],totsz-sz[X]);\n\tif(mx[X]&lt;mx[rt]){\n\t\trt=X;\n\t\trt2=0;\n\t}else if(mx[X]==mx[rt]){\n\t\trt2=X;\n\t}\n}\nint f[205][205],g[205][205];\ninline void dfs1(int X,int FA){\n\tFv(i,X){\n\t\tif(e[i].v==FA){\n\t\t\tcontinue;\n\t\t}\n\t\tdfs1(e[i].v,X);\n\t}\n\tfor(int i=0;i&lt;=n;++i){\n\t\tfor(int j=0;j&lt;=n;++j){\n\t\t\tg[i][j]=0;\n\t\t}\n\t}\n\tf[X][1]=f[X][0]=g[0][0]=sz[X]=1;\n\tint nw=1;\n\tFv(i,X){\n\t\tif(e[i].v==FA){\n\t\t\tcontinue;\n\t\t}\n\t\tsz[X]+=sz[e[i].v];\n\t\tfor(int j=0;j&lt;=sz[X];++j){\n\t\t\tfor(int k=0;k&lt;=j;++k){\n\t\t\t\tg[nw][j]=(g[nw][j]+g[nw-1][j-k]*f[e[i].v][k]%MOD)%MOD;\n\t\t\t}\n\t\t}\n\t\t++nw;\n\t}\n\t--nw;\n\tfor(int i=1;i&lt;=sz[X];++i){\n\t\tf[X][i]=g[nw][i-1];\n\t}\n}\nint ans=0;\ninline void calc1(){\n\tans=1;\n\tfor(int i=0;i&lt;=n;++i){\n\t\tsz[i]=0;\n\t\tfor(int j=0;j&lt;=n;++j){\n\t\t\tf[i][j]=0;\n\t\t}\n\t}\n\tdfs1(rt,0);\n\tfor(int i=2;i&lt;=n;++i){\n\t\tfor(int j=0;j&lt;=n;++j){\n\t\t\tfor(int k=0;k&lt;=n;++k){\n\t\t\t\tg[j][k]=0;\n\t\t\t}\n\t\t}\n\t\tg[0][0]=1;int nw=1;sz[rt]=1;\n\t\tFv(E,rt){\n\t\t\tsz[rt]+=sz[e[E].v];\n\t\t\tfor(int j=0;j&lt;=Min(i-1,sz[rt]);++j){\n\t\t\t\tfor(int k=0;k&lt;=j;++k){\n\t\t\t\t\tif(2*k>=i){\n\t\t\t\t\t\tbreak;\n\t\t\t\t\t}\n\t\t\t\t\tg[nw][j]=(g[nw][j]+g[nw-1][j-k]*f[e[E].v][k]%MOD)%MOD;\n\t\t\t\t}\n\t\t\t}\n\t\t\t++nw;\n\t\t}\n\t\t--nw;\n\t\tans=(ans+g[nw][i-1])%MOD;\n\t}\n}\ninline void calc2(){\n\tfor(int i=0;i&lt;=n;++i){\n\t\tsz[i]=0;\n\t\tfor(int j=0;j&lt;=n;++j){\n\t\t\tf[i][j]=0;\n\t\t}\n\t}\n\tdfs1(rt,rt2);dfs1(rt2,rt);\n\tans=0;\n\tfor(int i=1;i&lt;=n\/2;++i){\n\t\tans=(ans+f[rt][i]*f[rt2][i]%MOD)%MOD;\n\t}\n}\nvoid init(){\n\tscanf(\"%d\",&amp;n);\n\tint u,v;\n\tet=rt=rt2=0;\n\tfor(int i=1;i&lt;=n;++i){\n\t\th[i]=sz[i]=0;\n\t}\n\tfor(int i=1;i&lt;n;++i){\n\t\tscanf(\"%d%d\",&amp;u,&amp;v);\n\t\tadd(u,v);\n\t}\n\ttotsz=n;\n\tmx[0]=INF;\n\tdfs0(1,0);\n\tif(!rt2){\n\t\tcalc1();\n\t}else{\n\t\tcalc2();\n\t}\n\tprintf(\"Case %d: %d\\n\",Tid,ans);\n}\nint main(){\n\tint T;\n\tscanf(\"%d\",&amp;T);\n\twhile(T--){\n\t\t++Tid;\n\t\tinit();\n\t}\n\treturn 0;\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u4e24\u4e2a\u91cd\u5fc3\u7684\u60c5\u51b5\u60f3\u60f3\u90fd\u9ebb\u3002\u6211\u4eec\u9996\u5148\u8003\u8651\u4e00\u4e2a\u91cd\u5fc3\u7684\u60c5\u51b5\u3002 \u6211\u4eec\u628a \u5047\u8bbe\u6211\u4eec\u73b0\u5728\u5df2\u7ecf\u6c42\u51fa\u4e86\u6bcf\u4e2a\u5b50\u6811\u7684\u5927\u5c0f\uff0c\u90a3\u4e48\u6211\u4eec\u53d1 &hellip; <\/p>\n<p class=\"link-more\"><a href=\"http:\/\/SmokeyDays.top\/wordpress\/2019\/04\/11\/lp4582-fjoi2014-%e6%a0%91%e7%9a%84%e9%87%8d%e5%bf%83\/\" class=\"more-link\">\u7ee7\u7eed\u9605\u8bfb<span class=\"screen-reader-text\">\u201clp4582 FJOI2014 \u6811\u7684\u91cd\u5fc3\u201d<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[34,37,30,51,56,8,9,6,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/862"}],"collection":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/comments?post=862"}],"version-history":[{"count":2,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/862\/revisions"}],"predecessor-version":[{"id":867,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/862\/revisions\/867"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=862"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=862"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=862"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}