{"id":620,"date":"2019-02-16T13:13:26","date_gmt":"2019-02-16T05:13:26","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=620"},"modified":"2019-02-16T13:13:26","modified_gmt":"2019-02-16T05:13:26","slug":"lp2597-zjoi2012-%e7%81%be%e9%9a%be","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2019\/02\/16\/lp2597-zjoi2012-%e7%81%be%e9%9a%be\/","title":{"rendered":"lp2597 ZJOI2012 \u707e\u96be"},"content":{"rendered":"\n<p>\u8fd9\u4e00\u9898\u7684\u601d\u8def\u8fd8\u662f\u6bd4\u8f83\u6e05\u6670\u7684\u3002\u867d\u7136\u53ef\u4ee5\u5f53\u4f5c\u652f\u914d\u6811\u6a21\u677f\uff0c\u4f46\u662f\u4e8b\u5b9e\u4e0a\u53ef\u4ee5\u4e0a\u4e00\u4e2aLCA\u6765\u4ee3\u66ff\u652f\u914d\u6811\u3002<br>\u5177\u4f53\u6765\u8bf4\uff0c\u5c31\u662f\u628a\u6709\u591a\u4e2a\u98df\u7269\u7684\u6d88\u8d39\u8005\u8fde\u5230\u5b83\u6240\u6709\u98df\u7269\u7684LCA\u3002\u7136\u540e\u8ba1\u7b97\u4e00\u904d\u5b50\u6811\u5927\u5c0f\u5c31\u597d\u4e86\u3002<br> \u6ce8\u610f\u8fde\u70b9\u4e4b\u524d\u8981\u5148\u62d3\u6251\u6392\u5e8f\u3002 <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;iostream>\n#include&lt;cstdio>\n#include&lt;queue>\n\n#define Swap(A,B) (A^=B^=A^=B)\n\nstruct ee{\n\tint v;\n\tint nxt;\n}e[2500005];\n\/\/h\uff0c\u6811\u4e0a\u7684\u8282\u70b9\u3002g\uff0c\u62d3\u6251\u6392\u5e8f\u7684\u8282\u70b9\u3002to\uff0c\u6bcf\u4e2a\u8282\u70b9\u7684\u6240\u6709\u7236\u4eb2\u3002 \nint h[70000],g[70000],et=0,dep[70000],fa[70000][18],in[70000],to[70000],sz[70000],loc[70000];\nint n,tp=0;\ninline void add(int *H,int U,int V){\n\tif(U==V){\n\t\treturn;\n\t}\n\te[++et]=(ee){V,H[U]};\n\tH[U]=et;\n}\ninline void srt(){\n\tstd::queue&lt;int> q;\n\tfor(int i=1;i&lt;=n;++i){\n\t\tif(!in[i]){\n\t\t\tq.push(i);\n\t\t}\n\t}\n\tint p=0;\n\twhile(!q.empty()){\n\t\tp=q.front();\n\t\tq.pop();\n\t\tloc[++tp]=p;\n\t\tfor(int i=g[p];i;i=e[i].nxt){\n\t\t\t--in[e[i].v];\n\t\t\tif(!in[e[i].v]){\n\t\t\t\tq.push(e[i].v);\n\t\t\t}\n\t\t}\n\t}\n}\ninline int lca(int X,int Y){\n\tif(dep[X]&lt;dep[Y]){\n\t\tSwap(X,Y);\n\t}\n\tfor(int i=17;i>=0;--i){\n\t\tif(dep[X]-(1&lt;&lt;i)>=dep[Y]){\n\t\t\tX=fa[X][i]; \n\t\t}\n\t}\n\tif(X==Y){\n\t\treturn X;\n\t}\n\tfor(int i=17;i>=0;--i){\n\t\tif(fa[X][i]!=fa[Y][i]){\n\t\t\tX=fa[X][i],Y=fa[Y][i];\n\t\t}\n\t}\n\treturn fa[X][0];\n}\ninline void prpr(){\n\tint nw=0;\n\tfor(int i=1,j;i&lt;=n;++i){\n\t\tj=loc[i];\n\t\tnw=e[to[j]].v;\n\t\tfor(int k=to[j];k;k=e[k].nxt){\n\t\t\tnw=lca(nw,e[k].v);\n\t\t}\n\/\/\t\t\u8bf7\u6ce8\u610f\u8fd9\u91cc\u7684nw\u53ef\u80fd\u4e0d\u5b58\u5728\u4efb\u4f55\u7236\u4eb2\u8282\u70b9\u3002 \n\t\tadd(h,nw,j);\n\t\tfa[j][0]=nw;\n\t\tdep[j]=dep[nw]+1;\n\t\tfor(int k=1;k&lt;=17;++k){\n\t\t\tfa[j][k]=fa[fa[j][k-1]][k-1];\n\t\t}\n\t}\n}\ninline void dfs(int X){\n\tfor(int i=h[X];i;i=e[i].nxt){\n\t\tdfs(e[i].v);\n\t\tsz[X]+=sz[e[i].v];\n\t}\n\t++sz[X];\n}\nvoid init(){\n\tscanf(\"%d\",&amp;n);\n\tint x; \n\tfor(int i=1;i&lt;=n;++i){\n\t\tscanf(\"%d\",&amp;x);\n\t\twhile(x){\n\t\t\t++in[i];\n\t\t\tadd(g,x,i);\n\t\t\tadd(to,i,x);\n\t\t\tscanf(\"%d\",&amp;x);\n\t\t}\n\t}\n\tsrt();\n\tprpr();\n\tdfs(0);\n\tfor(int i=1;i&lt;=n;++i){\n\t\tprintf(\"%d\\n\",sz[i]-1);\n\t}\n}\n\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u8fd9\u4e00\u9898\u7684\u601d\u8def\u8fd8\u662f\u6bd4\u8f83\u6e05\u6670\u7684\u3002\u867d\u7136\u53ef\u4ee5\u5f53\u4f5c\u652f\u914d\u6811\u6a21\u677f\uff0c\u4f46\u662f\u4e8b\u5b9e\u4e0a\u53ef\u4ee5\u4e0a\u4e00\u4e2aLCA\u6765\u4ee3\u66ff\u652f\u914d\u6811\u3002\u5177\u4f53\u6765\u8bf4\uff0c\u5c31\u662f\u628a\u6709 &hellip; <\/p>\n<p class=\"link-more\"><a href=\"http:\/\/SmokeyDays.top\/wordpress\/2019\/02\/16\/lp2597-zjoi2012-%e7%81%be%e9%9a%be\/\" class=\"more-link\">\u7ee7\u7eed\u9605\u8bfb<span class=\"screen-reader-text\">\u201clp2597 ZJOI2012 \u707e\u96be\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,33,57,51,56,8,6,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/620"}],"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=620"}],"version-history":[{"count":1,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/620\/revisions"}],"predecessor-version":[{"id":621,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/620\/revisions\/621"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=620"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=620"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=620"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}