{"id":68,"date":"2026-01-03T00:06:58","date_gmt":"2026-01-02T16:06:58","guid":{"rendered":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/?p=68"},"modified":"2026-01-04T11:16:42","modified_gmt":"2026-01-04T03:16:42","slug":"p3916-%e5%9b%be%e7%9a%84%e9%81%8d%e5%8e%86%e9%82%bb%e6%8e%a5%e8%a1%a8%e6%b3%95","status":"publish","type":"post","link":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/2026\/01\/03\/p3916-%e5%9b%be%e7%9a%84%e9%81%8d%e5%8e%86%e9%82%bb%e6%8e%a5%e8%a1%a8%e6%b3%95\/","title":{"rendered":"P3916 \u56fe\u7684\u904d\u5386(\u90bb\u63a5\u8868\u6cd5)"},"content":{"rendered":"\n<a href=\"https:\/\/www.luogu.com.cn\/problem\/P3916\" target=\"_blank\" style=\"margin:0 auto;\">P3916 \u56fe\u7684\u904d\u5386<\/a>\n\n\n\n<pre class=\"wp-block-code\"><code>void add(int x, int y) { \/\/ \u6dfb\u52a0\u6761\u76ee\n\tnxt&#91;++cnt] = header&#91;x];\n\tdata&#91;cnt] = y;\n\theader&#91;x] = cnt;\n}\nvoid dfs(int x) { \/\/ \u6df1\u641c(\u5012\u7740)\n\tans&#91;x] = maxn;\n\tfor(int i = header&#91;x]; i; i = nxt&#91;i]) \/\/ \u7b80\u6d01\n\t    if(!ans&#91;data&#91;i]]) dfs(data&#91;i]);\n}<\/code><\/pre>\n\n\n\n<p>\u56e0\u4e3a\u8fd9\u9898\u7684\u8303\u56f4\u5f88\u5927\uff0c\u6240\u4ee5\u6211\u4eec\u9700\u8981<strong>\u53cd\u5411\u5efa\u8868<\/strong>\uff0c\u5373\u5c06\u6df1\u641c\u8fc7\u7a0b\u4e2d\u6bcf\u4e00\u4e2a\u6570\u90fd\u8bbe\u4e3a\u4e00\u5f00\u59cb\u8fdb\u884c\u6df1\u641c\u7684\u6700\u5927\u7684\u6570\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>cin >> x >> y;\nadd(y, x);<\/code><\/pre>\n\n\n\n<p>\u7136\u540e\u5012\u7740\u8fdb\u884cdfs<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>for (int d1=n;d1>=1;d1--) {\n    if (ans&#91;d1]) continue; \/\/ TODO: \u522b\u5fd8\u8bb0\u5df2\u7ecf\u8ba1\u7b97\u8fc7\u7684\u8981\u8df3\u8fc7!!!!\n    maxn = d1;\n    dfs(d1);\n}\nfor (int d1=1;d1&lt;=n;d1++) {\n   cout &lt;&lt; ans&#91;d1] &lt;&lt; \" \";\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>P3916 \u56fe\u7684\u904d\u5386 \u56e0\u4e3a\u8fd9\u9898&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"class_list":["post-68","post","type-post","status-publish","format-standard","hentry","category-c"],"_links":{"self":[{"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/posts\/68","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=68"}],"version-history":[{"count":2,"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/posts\/68\/revisions"}],"predecessor-version":[{"id":70,"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/posts\/68\/revisions\/70"}],"wp:attachment":[{"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=68"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=68"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=68"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}