{"id":1024,"date":"2019-03-07T19:24:17","date_gmt":"2019-03-07T11:24:17","guid":{"rendered":"https:\/\/mnihyc.com\/blog\/?p=1024"},"modified":"2020-04-22T11:41:36","modified_gmt":"2020-04-22T03:41:36","slug":"yzoj-p3392-%e8%b6%8a%e9%87%8e%e8%b5%9b%e8%bd%a6%e9%97%ae%e9%a2%98","status":"publish","type":"post","link":"https:\/\/mnihyc.com\/blog\/archives\/1024","title":{"rendered":"YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898"},"content":{"rendered":"<h1 style=\"text-align: center;\">YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898<\/h1>\n<p style=\"text-align: center;\">\u65f6\u95f4\u9650\u5236\uff1a1000MS \u00a0\u00a0\u00a0\u00a0 \u5185\u5b58\u9650\u5236\uff1a262144KB<\/p>\n<p style=\"text-align: center;\">\u96be\u5ea6\uff1a <span style=\"color: #ff9900;\">\\(6.0\\)<\/span><\/p>\n<ul>\n<li>\n<h3><strong>\u95ee\u9898\u63cf\u8ff0<\/strong><\/h3>\n<\/li>\n<\/ul>\n<p>\u67d0\u5c71\u4e0a\u4e00\u5171\u6709 \\(n\\) \u4e2a\u5e7f\u573a\uff0c\u7f16\u53f7\u4f9d\u6b21\u4e3a \\(1\\) \u5230 \\(<span style=\"color: #000000;\">n\\)\uff0c\u8fd9\u4e9b\u5e7f\u573a\u4e4b\u95f4\u901a\u8fc7<\/span> \\(n-1\\) \u6761\u53cc\u5411\u8f66\u9053\u76f4\u63a5\u6216\u95f4\u63a5\u5730\u8fde\u63a5\u5728\u4e00\u8d77\u3002\u5bf9\u4e8e\u6bcf\u6761\u8f66\u9053 \\(i\\)\uff0c\u53ef\u4ee5\u7528\u56db\u4e2a\u6b63\u6574\u6570 \\(u_i, v_i, l_i, r_i\\) \u63cf\u8ff0\uff0c\u8868\u793a\u8f66\u9053\u8fde\u63a5\u5e7f\u573a \\(u_i\\) \u548c \\(v_i\\)\uff0c\u5176\u901f\u5ea6\u627f\u53d7\u533a\u95f4\u4e3a \\([l_i, r_i]\\)\uff0c\u5373\u6c7d\u8f66\u5fc5\u987b\u4ee5\u4e0d\u5c0f\u4e8e \\(l_i\\) \u4e14\u4e0d\u5927\u4e8e \\(r_i\\) \u7684\u901f\u5ea6\u7ecf\u8fc7\u8f66\u9053 \\(i\\) \u3002<\/p>\n<p>\u73b0\u8ba1\u5212\u8fdb\u884c \\(m\\) \u6b21\u8bad\u7ec3\uff0c\u6bcf\u6b21\u9009\u62e9\u67d0\u5c71\u4e0a\u7684\u4e00\u6761<strong>\u7b80\u5355\u8def\u5f84<\/strong>\uff0c\u7136\u540e\u5728\u8fd9\u6761\u8def\u5f84\u4e0a\u884c\u9a76\uff0c\u4e14\u6bcf\u6b21\u8bad\u7ec3\u65f6\u7684\u8f66\u901f\u90fd\u662f\u56fa\u5b9a\u7684\u3002\u73b0\u5728\u6709\u5728 m \u6b21\u8bad\u7ec3\u4e2d\u5206\u522b\u8ba1\u5212\u4f7f\u7528\u7684\u8f66\u901f\uff0c\u8981\u6c42\u4e00\u6761\u5408\u6cd5\u7684\u8def\u5f84\uff08\u8f66\u901f\u5728\u6240\u6709\u8f66\u9053\u7684\u901f\u5ea6\u627f\u53d7\u533a\u95f4\u7684\u4ea4\u96c6\u5185\uff09\uff0c\u4f7f\u5f97\u8def\u5f84\u4e0a\u7ecf\u8fc7\u7684<strong>\u8f66\u9053\u6570\u6700\u5927<\/strong>\u3002<\/p>\n<ul>\n<li>\n<h3><strong>\u6570\u636e\u8f93\u5165<\/strong><\/h3>\n<\/li>\n<\/ul>\n<p>\u8f93\u5165\u6587\u4ef6\u7684\u7b2c\u4e00\u884c\u5305\u542b\u4e24\u4e2a\u6b63\u6574\u6570 \\(n, m\\)\uff0c\u8868\u793a\u5e7f\u573a\u6570\u548c\u8bad\u7ec3\u6b21\u6570\u3002\u63a5\u4e0b\u6765 \\(n-1\\) \u884c\uff0c\u6bcf\u884c\u56db\u4e2a\u6b63\u6574\u6570 \\(u_i, v_i, l_i, r_i ( \\leq n)\\)\uff0c\u63cf\u8ff0\u6240\u6709\u8f66\u9053\u3002\u6700\u540e \\(m\\) \u884c\uff0c\u6bcf\u884c\u4e00\u4e2a\u6b63\u6574\u6570 \\(v (\\leq n)\\) \uff0c\u8868\u793a\u6bcf\u6b21\u8bad\u7ec3\u662f\u7684\u8f66\u901f\u3002<\/p>\n<ul>\n<li>\n<h3><strong>\u7ed3\u679c\u8f93\u51fa<\/strong><\/h3>\n<\/li>\n<\/ul>\n<p>\u8f93\u51fa \\(m\\) \u884c\uff0c\u8f93\u51fa\u6bcf\u6b21\u8bad\u7ec3\u65f6\u7684\u884c\u9a76\u8def\u5f84\u7ecf\u8fc7\u7684\u6700\u5927\u8f66\u9053\u6570\u3002<\/p>\n<ul>\n<li>\n<h3><strong>\u6837\u4f8b\u8f93\u5165<\/strong><\/h3>\n<\/li>\n<\/ul>\n<pre class=\"\">5 3\r\n3 2 2 4\r\n1 5 2 5\r\n4 5 2 2\r\n1 2 3 5\r\n1\r\n2\r\n3<\/pre>\n<ul>\n<li>\n<h3><strong>\u6837\u4f8b\u8f93\u51fa<\/strong><\/h3>\n<\/li>\n<\/ul>\n<pre class=\"\">0\r\n2\r\n3<\/pre>\n<p><!--more--><\/p>\n<ul>\n<li>\n<h3><strong>\u6570\u636e\u8303\u56f4<\/strong><\/h3>\n<\/li>\n<\/ul>\n<table class=\"lightningtable\" style=\"height: 286px;\" border=\"1\" cellspacing=\"1\" cellpadding=\"1\">\n<tbody>\n<tr style=\"height: 26px;\">\n<td style=\"width: 116.2px; height: 26px;\">\u6570\u636e\u70b9<\/td>\n<td style=\"width: 148.25px; height: 26px;\">\\(n\\)<\/td>\n<td style=\"width: 148.25px; height: 26px;\">\\(m\\)<\/td>\n<td style=\"width: 123.9px; height: 26px;\">\u7ea6\u5b9a<\/td>\n<\/tr>\n<tr style=\"height: 26px;\">\n<td style=\"width: 116.2px; height: 26px;\">1<\/td>\n<td style=\"width: 148.25px; height: 26px;\">\\(=5\\)<\/td>\n<td style=\"width: 148.25px; height: 26px;\">\\(5\\)<\/td>\n<td style=\"vertical-align: top; width: 123.9px; height: 52px;\" colspan=\"1\" rowspan=\"2\">&#8211;<\/td>\n<\/tr>\n<tr style=\"height: 26px;\">\n<td style=\"width: 116.2px; height: 26px;\">2<\/td>\n<td style=\"width: 148.25px; height: 26px;\">\\(=20\\)<\/td>\n<td style=\"width: 154.65px; height: 26px;\">\\(20\\)<\/td>\n<\/tr>\n<tr style=\"height: 26px;\">\n<td style=\"width: 116.2px; height: 26px;\">3<\/td>\n<td style=\"width: 148.25px; height: 26px;\">\\(=50000\\)<\/td>\n<td style=\"width: 148.25px; height: 26px;\">\\(=50000\\)<\/td>\n<td style=\"vertical-align: top; width: 123.9px; height: 52px;\" colspan=\"1\" rowspan=\"2\">\\(l_i = 1, u_i = i, v_i = i +1\\)<\/td>\n<\/tr>\n<tr style=\"height: 26px;\">\n<td style=\"width: 116.2px; height: 26px;\">4<\/td>\n<td style=\"width: 148.25px; height: 26px;\">\\(=70000\\)<\/td>\n<td style=\"width: 154.65px; height: 26px;\">\\(=70000\\)<\/td>\n<\/tr>\n<tr style=\"height: 26px;\">\n<td style=\"width: 116.2px; height: 26px;\">5<\/td>\n<td style=\"width: 148.25px; height: 26px;\">\\(=50000\\)<\/td>\n<td style=\"width: 148.25px; height: 26px;\">\\(=50000\\)<\/td>\n<td style=\"vertical-align: top; width: 123.9px; height: 52px;\" colspan=\"1\" rowspan=\"2\">\\(u_i = i, v_i = i +1\\)<\/td>\n<\/tr>\n<tr style=\"height: 26px;\">\n<td style=\"width: 116.2px; height: 26px;\">6<\/td>\n<td style=\"width: 148.25px; height: 26px;\">\\(=70000\\)<\/td>\n<td style=\"width: 154.65px; height: 26px;\">\\(=70000\\)<\/td>\n<\/tr>\n<tr style=\"height: 26px;\">\n<td style=\"width: 116.2px; height: 26px;\">7<\/td>\n<td style=\"width: 148.25px; height: 26px;\">\\(=50000\\)<\/td>\n<td style=\"width: 148.25px; height: 26px;\">\\(=50000\\)<\/td>\n<td style=\"vertical-align: top; width: 123.9px; height: 52px;\" colspan=\"1\" rowspan=\"2\">\\(l_i = 1\\)<\/td>\n<\/tr>\n<tr style=\"height: 26px;\">\n<td style=\"width: 116.2px; height: 26px;\">8<\/td>\n<td style=\"width: 148.25px; height: 26px;\">\\(=70000\\)<\/td>\n<td style=\"width: 154.65px; height: 26px;\">\\(=70000\\)<\/td>\n<\/tr>\n<tr style=\"height: 26px;\">\n<td style=\"width: 116.2px; height: 26px;\">9<\/td>\n<td style=\"width: 148.25px; height: 26px;\">\\(=50000\\)<\/td>\n<td style=\"width: 148.25px; height: 26px;\">\\(=50000\\)<\/td>\n<td style=\"vertical-align: top; width: 123.9px; height: 52px;\" colspan=\"1\" rowspan=\"2\">&#8211;<\/td>\n<\/tr>\n<tr style=\"height: 26px;\">\n<td style=\"width: 116.2px; height: 26px;\">10<\/td>\n<td style=\"width: 148.25px; height: 26px;\">\\(=70000\\)<\/td>\n<td style=\"width: 154.65px; height: 26px;\">\\(=70000\\)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p><!--more--><\/p>\n<hr \/>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>\u9996\u5148\u5bf9\u4e8e \\(n,m \\leq 20\\) \u7684\u6570\u636e\uff0c\u968f\u4fbf\u4e71\u641c\u90fd\u80fd\u8fc7\u3002<\/p>\n<p>\u7136\u540e\u662f\u5bf9\u4e8e \\(l_i = 1\\) \u7684\u6570\u636e\uff0c\u4e5f\u5c31\u662f\u8bf4\u6700\u5c0f\u5141\u8bb8\u7684\u901f\u5ea6\u90fd\u662f \\(1\\) \uff0c\u53ea\u8981\u8003\u8651 \\(r_i\\) \u9020\u6210\u7684\u5f71\u54cd\u3002<\/p>\n<p>\u6240\u4ee5\u53ef\u4ee5\u60f3\u5230\u6309\u7167\u8fb9\u7684 \\(r_i\\) \u964d\u5e8f\u6392\u5e8f\uff0c\u540c\u65f6\u628a\u8be2\u95ee<strong>\u79bb\u7ebf<\/strong>\u4e5f\u6309\u7167 \\(v_i\\) \u964d\u5e8f\u6392\u5e8f\uff0c\u6bcf\u6b21\u53ea\u9700\u8981\u628a\u6240\u6709 \\(r\\) \u6bd4\u5f53\u524d\u8be2\u95ee \\(v\\) \u5927\u7684\u8fb9\u52a0\u5165\u67d0\u4e2a\u6570\u636e\u7ed3\u6784\u7ef4\u62a4\uff0c\u7136\u540e\u66f4\u65b0\u7b54\u6848\u5373\u53ef\u3002<\/p>\n<p>\u7531\u4e8e\u8fd9\u91cc\u7ef4\u62a4\u7684\u662f\u8fde\u901a\u6027\uff0c\u6240\u4ee5\u5f88\u81ea\u7136\u7684\u60f3\u5230<strong>\u5e76\u67e5\u96c6<\/strong>\u3002\u4f46\u662f\u8981\u6c42\u7684\u7b54\u6848\u662f\u6700\u957f\u94fe\u7684\u957f\u5ea6\uff0c\u6240\u4ee5\u9700\u8981\u5bf9\u5e76\u67e5\u96c6\u4e2d\u7684\u6bcf\u4e00\u4e2a\u8fde\u901a\u5b50\u6811\u7ef4\u62a4\u5176\u4e2d<strong>\u6700\u957f\u94fe\u7684\u4e24\u4e2a\u7aef\u70b9<\/strong>\uff0c\u8bbe\u4e3a \\(\\{x, y\\}\\) \u3002<\/p>\n<p>\u5408\u5e76\u4e24\u4e2a\u5e76\u67e5\u96c6\u7684\u65f6\u5019\uff0c\u5047\u8bbe\u53e6\u4e00\u4e2a\u5e76\u67e5\u96c6\u6700\u957f\u94fe\u7684\u4e24\u4e2a\u7aef\u70b9\u4e3a \\(\\{s, t\\}\\) \uff0c\u90a3\u4e48\u5408\u5e76\u540e\u5b50\u6811\u7684\u6700\u957f\u94fe\u53ea\u6709\u516d\u79cd\u60c5\u51b5\uff1a\\(\\{x,y\\}, \\{s,t\\}, \\{x,s\\}, \\{x,t\\}, \\{y,s\\}, \\{y,t\\}\\) \uff0c\u6c42\u4e24\u70b9\u8ddd\u79bb\u7684\u65f6\u5019\u7528<span style=\"font-size: 20px;\"><strong>\u6811\u94fe\u5256\u5206<\/strong><span style=\"font-size: 8px;\">\u6216\u500d\u589e<\/span><\/span> lca \u8f6c\u6362\u4e00\u4e0b\u3002<\/p>\n<p><del>\u8bc1\u660e\u8bf7\u89c1YJC\u540c\u5b66\u7684\u8865\u5145\u9898\u89e3\u3002<\/del><\/p>\n<p>\u8fd9\u6837\u65f6\u95f4\u590d\u6742\u5ea6\u5c31\u662f lca \\(+\\) \u5e76\u67e5\u96c6 \\(+\\) std::sort \\(= O(nlogn)\\) \u3002<\/p>\n<p>&nbsp;<\/p>\n<p>\u5bf9\u4e8e\u6240\u6709\u7684\u6570\u636e\uff0c\\(l_i\\) \u4e0d\u4e00\u5b9a\u90fd\u4e3a \\(1\\) \uff0c\u4e5f\u5c31\u662f\u8bf4\u5fc5\u987b\u8003\u8651 \\(l_i\\) \u9020\u6210\u7684\u5f71\u54cd\u3002\u82e5\u6b64\u65f6\u8fd8\u662f\u6309\u7167\u4e4b\u524d\u7684\u505a\u6cd5\uff0c\u90a3\u5c31\u9700\u8981\u5e26\u6743\u5e76\u67e5\u96c6\u652f\u6301\u4efb\u610f\u64a4\u9500\u4e00\u6761\u8fb9\u7684\u8fde\u63a5\uff0c\u8fd9\u662f\u975e\u5e38\u4e0d\u73b0\u5b9e\u7684\u3002<\/p>\n<p>\u6362\u4e00\u79cd\u601d\u8003\u65b9\u6cd5\uff0c\u628a\u533a\u95f4 \\([l_i, r_i]\\) \u770b\u4f5c<strong>\u65f6\u95f4\u533a\u95f4<\/strong>\uff0c\u90a3\u4e48\u4e00\u6761\u8fb9\u5c06\u5728 \\(l_i\\) \u65f6\u523b\u51fa\u73b0\uff0c\u5e76\u5728 \\(r_i\\) \u65f6\u523b\u540e\u6d88\u5931\uff0c\u8be2\u95ee \\(v\\) \u5c31\u662f\u8be2\u95ee \\(v\\) \u65f6\u523b\u7684\u7b54\u6848\u3002<\/p>\n<p>\u540c\u65f6\u6ce8\u610f\u5230 \\(l_i, r_i, v_i \\leq n \\leq 70000\\) \uff0c\u6240\u4ee5\u60f3\u5230<strong>\u7ebf\u6bb5\u6811\u5206\u6cbb<\/strong>\u3002<\/p>\n<p>\u7ebf\u6bb5\u6811\u5206\u6cbb\u5176\u5b9e\u5c31\u662f<strong>\u6309\u7167\u65f6\u95f4\u5206\u6cbb<\/strong>\uff0c\u56e0\u4e3a\u5206\u6cbb\u7684\u533a\u95f4 \\([l, mid], (mid, r]\\) \u6781\u5176\u7c7b\u4f3c\u4e8e\u7ebf\u6bb5\u6811\u5206\u6cbb\u7684\u533a\u95f4\u5f62\u5f0f\uff08\u51e0\u4e4e\u662f\u4e00\u6837\u7684\uff09\uff0c\u6240\u4ee5\u53ef\u4ee5\u7528\u5206\u6cbb\u7684\u65b9\u6cd5\u904d\u5386\u7ebf\u6bb5\u6811\uff0c\u540c\u65f6\u5408\u5e76\uff08<strong>\u5229\u7528<\/strong>\uff09\u7ebf\u6bb5\u6811\u4e0a<strong>\u7ef4\u62a4\u7684\u4fe1\u606f<\/strong>\u8fdb\u884c\u7b54\u6848\u7684\u66f4\u65b0\u3002<\/p>\n<p>\u5bf9\u4e8e\u6b64\u9898\u6765\u8bf4\uff0c\u5bf9 \\(v\\) \u8fdb\u884c\u5206\u6cbb\uff0c\u5206\u6cbb\u533a\u95f4 \\([l, r]\\) \u7ef4\u62a4\u901f\u5ea6<strong>\u5728 \\([l, r]\\) \u8303\u56f4<\/strong>\u65f6\u7684\u5408\u6cd5\u7684\u8fb9\u3002\u663e\u7136\u4e0d\u80fd\u5bf9\u6bcf\u4e2a\u8fd9\u6837\u7684\u533a\u95f4\uff08\u603b\u5171\u4e0d\u8d85\u8fc7 \\(4n\\) \u4e2a\uff09\u90fd\u5b58\u4e0b\u6240\u6709\u7684\u5408\u6cd5\u7684\u8fb9\uff0c\u8fd9\u65f6\u5019\u7ebf\u6bb5\u6811\u7684\u601d\u60f3\u5c31\u6d3e\u4e0a\u7528\u573a\u4e86\u3002<\/p>\n<p>\u7ebf\u6bb5\u6811\u67e5\u8be2\u7684\u590d\u6742\u5ea6\u53ea\u6709 \\(logn\\) \uff0c\u56e0\u4e3a\u82e5\u533a\u95f4 \\([l, r]\\) \u5df2\u7ecf\u88ab\u8be2\u95ee\u533a\u95f4\u5b8c\u5168\u5305\u542b\uff0c\u90a3\u4e48\u5c31<strong>\u4e0d\u7528<\/strong>\u7ee7\u7eed\u5f80\u4e0b\u5bfb\u627e\uff0c\u76f4\u63a5\u5229\u7528\u8fd9\u4e2a\u533a\u95f4\u70b9\u7684\u4fe1\u606f\u66f4\u65b0\u7b54\u6848\u5373\u53ef\u3002\u540c\u7406\uff0c\u7ebf\u6bb5\u6811\u5206\u6cbb\u4e5f\u662f\u5982\u6b64\u3002\u82e5\u4e00\u6761\u8fb9\u5728\u901f\u5ea6\u4e3a\u533a\u95f4 \\([l, r]\\) \u7684\u8303\u56f4\u5185\u5df2\u7ecf\u5408\u6cd5\uff0c\u90a3\u4e48\u5c31\u4e0d\u7528\u5bf9\u4e8e \\([l, r]\\) \u5185\u7684\u5176\u4f59\u6240\u6709\u5b50\u533a\u95f4\u90fd\u6dfb\u52a0\u8fd9\u6761\u8fb9\u4e86\uff0c\u56e0\u4e3a\u53ea\u6709\u5206\u6cbb\u5230 \\([l, r]\\) \u65f6\u9700\u8981\u6dfb\u52a0\u8fd9\u6761\u8fb9\u7684\u4fe1\u606f\uff0c\u4e4b\u540e\u5206\u6cbb\u8fdb\u7684\u5b50\u533a\u95f4\u5c31\u518d\u4e5f\u4e0d\u9700\u8981\u4e86\u3002\u8fd9\u6837\u4e00\u6761\u8fb9\u5c31\u6700\u591a\u53ea\u4f1a\u88ab \\(O(logn)\\) \u4e2a\u533a\u95f4\u6240\u6dfb\u52a0\uff0c\u65f6\u95f4\u548c\u7a7a\u95f4\u590d\u6742\u5ea6\u90fd\u662f\u53ef\u4ee5\u63a5\u53d7\u7684\u3002<\/p>\n<p>\u73b0\u5728\u8fd8\u5269\u6700\u540e\u4e00\u4e2a\u95ee\u9898\uff0c\u5206\u6cbb\u65f6\u9700\u8981\u5728\u8fd4\u56de\u4e4b\u524d\u64a4\u9500\u5728\u8fd9\u4e00\u5c42\u4e2d\u5e76\u67e5\u96c6\u6dfb\u52a0\u7684\u8fb9\u3002\u53d1\u73b0\u53ea\u8981\u7b80\u5355\u7684\u6309<strong>\u6808\u5e8f\u64a4\u9500<\/strong>\u5373\u53ef\uff0c\u6240\u4ee5\u5e76\u67e5\u96c6\u4e0d\u80fd\u6709\u8def\u5f84\u538b\u7f29\uff0c\u5199\u4e00\u4e2a\u6309\u79e9\u5408\u5e76\uff08\u542f\u53d1\u5f0f\u5408\u5e76\uff09\uff0c\u8fd8\u539f\u65f6\u8bb0\u5f97\u628a \\(f\\) \u6570\u7ec4\uff0c\\(size\\) \u6216 \\(rank\\) \uff0c\u7ef4\u62a4\u7684\u6700\u957f\u94fe\u7684\u4e24\u4e2a\u7aef\u70b9\uff0c\u6240\u6709\u8fde\u901a\u5b50\u6811\u4e2d\u6700\u957f\u94fe\u6700\u5927\u957f\u5ea6\uff08\u7b54\u6848\uff09 \u5168\u90e8\u8fd8\u539f\uff01<\/p>\n<p>\u8fd9\u6837\u65f6\u95f4\u590d\u6742\u5ea6\u5c31\u662f lca \\(+\\) \u5e76\u67e5\u96c6 \\(+\\) \u7ebf\u6bb5\u6811\u5206\u6cbb \\(= O(nlogn)\\) \u3002<\/p>\n<p>&nbsp;<\/p>\n<pre class=\"lang:default decode:true \">#include &lt;cstdio&gt;\r\n#include &lt;cstdlib&gt;\r\n#include &lt;cstring&gt;\r\n#include &lt;climits&gt;\r\n#include &lt;algorithm&gt;\r\n\r\n#define _max(_a_,_b_) ((_a_)&gt;(_b_)?(_a_):(_b_))\r\n\r\n#ifdef ONLINE_JUDGE\r\n\tchar __B[1&lt;&lt;15],*__S=__B,*__T=__B;\r\n\t#define getchar() (__S==__T&amp;&amp;(__T=(__S=__B)+fread(__B,1,1&lt;&lt;15,stdin),__S==__T)?EOF:*__S++)\r\n#endif\r\n\r\ninline int getnum()\r\n{\r\n\tregister char c=0;\r\n\twhile(!(c&gt;='0' &amp;&amp; c&lt;='9'))\r\n\t\tc=getchar();\r\n\tregister int a=0;\r\n\twhile(c&gt;='0' &amp;&amp; c&lt;='9')\r\n\t{\r\n\t\ta*=10;a+=c-'0';\r\n\t\tc=getchar();\r\n\t}\r\n\treturn a;\r\n}\r\n\r\n\r\nint N;\r\nint ghead[105050],gnext[205050],gnode[205050],gcnt;\r\ninline void ginsertLine(register int s,register int t)\r\n{\r\n\tgnode[++gcnt]=t,gnext[gcnt]=ghead[s],ghead[s]=gcnt;\r\n\tgnode[++gcnt]=s,gnext[gcnt]=ghead[t],ghead[t]=gcnt;\r\n}\r\n\r\n\/*int _log[105050],lf[105050][20],depth[105050];\r\nvoid DFS(register int o,register int fa)\r\n{\r\n\tfor(register int j=ghead[o];j;j=gnext[j])\r\n\t\tif(gnode[j] != fa)\r\n\t\t{\r\n\t\t\tdepth[gnode[j]]=depth[o]+1;\r\n\t\t\tlf[gnode[j]][0]=o;\r\n\t\t\tDFS(gnode[j],o);\r\n\t\t}\r\n}\r\n\r\ninline void initLCA()\r\n{\r\n\tfor(register int i=1;i&lt;=N;i++)\r\n\t\t_log[i]=_log[i&gt;&gt;1]+1;\r\n\tfor(register int k=1;(1&lt;&lt;k)&lt;=N;k++)\r\n\t\tfor(register int i=1;i&lt;=N;i++)\r\n\t\t\tlf[i][k]=lf[lf[i][k-1]][k-1];\r\n}\r\n\r\ninline int getLCA(register int x,register int y)\r\n{\r\n\tif(depth[x]&gt;depth[y])\r\n\t\tx^=y^=x^=y;\r\n\tregister int df=depth[y]-depth[x];\r\n\tfor(register int k=0;(1&lt;&lt;k)&lt;=df;k++)\r\n\t\tif((1&lt;&lt;k)&amp;df)\r\n\t\t\ty=lf[y][k];\r\n\tif(x!=y)\r\n\t{\r\n\t\tfor(register int k=_log[N];k&gt;=0;k--)\r\n\t\t\tif(lf[x][k] != lf[y][k])\r\n\t\t\t\tx=lf[x][k],y=lf[y][k];\r\n\t\tx=lf[x][0];\r\n\t}\r\n\treturn x;\r\n}*\/\r\n\r\nint depth[105050],father[105050],lsize[105050],lson[105050],ltop[105050];\r\nvoid DFS(register int o)\r\n{\r\n\tlsize[o]=1;\r\n\tfor(register int j=ghead[o];j;j=gnext[j])\r\n\t\tif(gnode[j] != father[o])\r\n\t\t{\r\n\t\t\tdepth[gnode[j]]=depth[o]+1;\r\n\t\t\tfather[gnode[j]]=o;\r\n\t\t\tDFS(gnode[j]);\r\n\t\t\tlsize[o]+=lsize[gnode[j]];\r\n\t\t\tif(lsize[gnode[j]] &gt; lsize[lson[o]])\r\n\t\t\t\tlson[o]=gnode[j];\r\n\t\t}\r\n}\r\n\r\nvoid DFS1(register int o)\r\n{\r\n\tif(o==lson[father[o]])\r\n\t\tltop[o]=ltop[father[o]];\r\n\telse\r\n\t\tltop[o]=o;\r\n\tfor(register int j=ghead[o];j;j=gnext[j])\r\n\t\tif(gnode[j] != father[o])\r\n\t\t\tDFS1(gnode[j]);\r\n}\r\n\r\ninline int getLCA(register int x,register int y)\r\n{\r\n\twhile(ltop[x] != ltop[y])\r\n\t\tif(depth[ltop[x]] &gt; depth[ltop[y]])\r\n\t\t\tx=father[ltop[x]];\r\n\t\telse\r\n\t\t\ty=father[ltop[y]];\r\n\treturn (depth[x]&lt;depth[y] ? x : y);\r\n}\r\n\r\n\r\nstruct _edge\r\n{\r\n\tint s,t;\r\n}edges[105050];\r\n\r\nint qhead[305050],qnext[2050505],qidx[2050505],qcnt;\r\n\r\nint Qvl,Qvr,Qpos;\r\ninline void ModifyTreeAddQuery(register int O,register int L,register int R)\r\n{\r\n\tif(L&gt;=Qvl &amp;&amp; R&lt;=Qvr)\r\n\t{\r\n\t\tqidx[++qcnt]=Qpos,qnext[qcnt]=qhead[O],qhead[O]=qcnt;\r\n\t\treturn;\r\n\t}\r\n\t\r\n\tregister int mid=(L+R)&gt;&gt;1;\r\n\tif(Qvl&lt;=mid)\r\n\t\tModifyTreeAddQuery(O&lt;&lt;1,L,mid);\r\n\tif(Qvr&gt;mid)\r\n\t\tModifyTreeAddQuery(O&lt;&lt;1|1,mid+1,R);\r\n}\r\n\r\n\r\nstruct _link\r\n{\r\n\tint x,y,len;\r\n\t_link operator += (const _link&amp;o)\r\n\t{\r\n\t\tregister int ax=x,ay=y,alen=len;\r\n\t\t#define SetAns(_olen,_ox,_oy) \\\r\n\t\t\tif((_olen)&gt;alen)alen=_olen,ax=_ox,ay=_oy;\r\n\t\t#define getDIS(_x,_y) \\\r\n\t\t\t(depth[_x]+depth[_y]-(depth[getLCA(_x,_y)]&lt;&lt;1))\r\n\t\tSetAns(o.len,o.x,o.y);\r\n\t\tSetAns(getDIS(x,o.x),x,o.x);\r\n\t\tSetAns(getDIS(x,o.y),x,o.y);\r\n\t\tSetAns(getDIS(y,o.x),y,o.x);\r\n\t\tSetAns(getDIS(y,o.y),y,o.y);\r\n\t\tx=ax,y=ay,len=alen;\r\n\t\treturn *this;\r\n\t}\r\n}ulink[105050],hslink[105050];\r\n\r\nint uf[105050],usize[105050];\r\ninline int UnionFind(register int x)\r\n{\r\n\twhile(x!=uf[x])\r\n\t\tx=uf[x];\r\n\treturn x;\r\n}\r\n\r\nint hsuf[105050][2],hstop;\r\ninline int UnionMerge(register int x,register int y)\r\n{\r\n\tx=UnionFind(x),y=UnionFind(y);\r\n\tif(x==y)\r\n\t\treturn ulink[x].len;\r\n\tif(usize[x]&lt;usize[y])\r\n\t\tx^=y^=x^=y;\r\n\tuf[y]=x,usize[x]+=usize[y];\r\n\thsuf[++hstop][0]=x,hsuf[hstop][1]=y;\r\n\thslink[hstop]=ulink[x];\r\n\treturn (ulink[x]+=ulink[y]).len;\r\n}\r\n\r\ninline void UnionUndo()\r\n{\r\n\tregister int x=hsuf[hstop][0],y=hsuf[hstop][1];\r\n\tuf[y]=y,usize[x]-=usize[y];\r\n\tulink[x]=hslink[hstop--];\r\n}\r\n\r\n\r\nint ans[105050];\r\nvoid Divide(register int O,register int l,register int r,register int nans)\r\n{\r\n\tregister int ohstop=hstop;\r\n\tfor(register int j=qhead[O];j;j=qnext[j])\r\n\t{\r\n\t\tregister int tans=UnionMerge(edges[qidx[j]].s,edges[qidx[j]].t);\r\n\t\tnans=_max(nans,tans);\r\n\t}\r\n\t\r\n\tif(l==r)\r\n\t\tans[l]=nans;\r\n\telse\r\n\t{\r\n\t\tregister int mid=(l+r)&gt;&gt;1;\r\n\t\tDivide(O&lt;&lt;1,l,mid,nans),Divide(O&lt;&lt;1|1,mid+1,r,nans);\r\n\t}\r\n\t\r\n\twhile(hstop&gt;ohstop)\r\n\t\tUnionUndo();\r\n}\r\n\r\nint main()\r\n{\r\n\tregister int N=getnum(),M=getnum();\r\n\t::N=N;\r\n\tfor(register int i=1;i&lt;=N-1;i++)\r\n\t{\r\n\t\tregister int u=getnum(),v=getnum();\r\n\t\tginsertLine(u,v);\r\n\t\tedges[i]=(_edge){u,v};\r\n\t\tQvl=getnum(),Qvr=getnum(),Qpos=i;\r\n\t\tModifyTreeAddQuery(1,1,N);\r\n\t}\r\n\t\/\/DFS(1,0),initLCA();\r\n\tDFS(1),DFS1(1);\r\n\t\r\n\tfor(register int i=1;i&lt;=N;i++)\r\n\t\tuf[i]=i,usize[i]=1,ulink[i]=(_link){i,i,0};\r\n\tDivide(1,1,N,0);\r\n\tfor(register int i=1;i&lt;=M;i++)\r\n\t\tprintf(\"%d\\n\",ans[getnum()]);\r\n\t\r\n\treturn 0;\r\n}<\/pre>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898 \u65f6\u95f4\u9650\u5236\uff1a1000MS \u00a0\u00a0\u00a0\u00a0 \u5185\u5b58\u9650\u5236\uff1a262144KB \u96be\u5ea6\uff1a \u95ee\u9898 &hellip; <a href=\"https:\/\/mnihyc.com\/blog\/archives\/1024\" class=\"more-link\">\u7ee7\u7eed\u9605\u8bfb<span class=\"screen-reader-text\">YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[41,61,70,69],"tags":[],"class_list":["post-1024","post","type-post","status-publish","format-standard","hentry","category-proa","category-unionset","category-graphlca","category-segdivide"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.1.1 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898 - mnihyc&#039;s Blog<\/title>\n<meta name=\"description\" content=\"YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898 \u65f6\u95f4\u9650\u5236\uff1a1000MS \u00a0\u00a0\u00a0\u00a0 \u5185\u5b58\u9650\u5236\uff1a262144KB \u96be\u5ea6\uff1a \u95ee\u9898\u63cf\u8ff0 \u67d0\u5c71\u4e0a\u4e00\u5171\u6709 (n) \u4e2a\u5e7f\u573a\uff0c\u7f16\u53f7\u4f9d\u6b21\u4e3a (1) \u5230 (n)\uff0c\u8fd9\u4e9b\u5e7f\u573a\u4e4b\u95f4\u901a\u8fc7 (n-1) \u6761\u53cc\u5411\u8f66\u9053\u76f4\u63a5\u6216\u95f4\u63a5\u5730\u8fde\u63a5\u5728\u4e00\u8d77\u3002\u5bf9\u4e8e\u6bcf\u6761\u8f66\u9053 (i)\uff0c\u53ef\u4ee5\u7528\u56db\u4e2a\u6b63\u6574\u6570\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/mnihyc.com\/blog\/archives\/1024\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898 - mnihyc&#039;s Blog\" \/>\n<meta property=\"og:description\" content=\"YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898 \u65f6\u95f4\u9650\u5236\uff1a1000MS \u00a0\u00a0\u00a0\u00a0 \u5185\u5b58\u9650\u5236\uff1a262144KB \u96be\u5ea6\uff1a \u95ee\u9898\u63cf\u8ff0 \u67d0\u5c71\u4e0a\u4e00\u5171\u6709 (n) \u4e2a\u5e7f\u573a\uff0c\u7f16\u53f7\u4f9d\u6b21\u4e3a (1) \u5230 (n)\uff0c\u8fd9\u4e9b\u5e7f\u573a\u4e4b\u95f4\u901a\u8fc7 (n-1) \u6761\u53cc\u5411\u8f66\u9053\u76f4\u63a5\u6216\u95f4\u63a5\u5730\u8fde\u63a5\u5728\u4e00\u8d77\u3002\u5bf9\u4e8e\u6bcf\u6761\u8f66\u9053 (i)\uff0c\u53ef\u4ee5\u7528\u56db\u4e2a\u6b63\u6574\u6570\" \/>\n<meta property=\"og:url\" content=\"https:\/\/mnihyc.com\/blog\/archives\/1024\" \/>\n<meta property=\"og:site_name\" content=\"mnihyc&#039;s Blog\" \/>\n<meta property=\"article:published_time\" content=\"2019-03-07T11:24:17+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2020-04-22T03:41:36+00:00\" \/>\n<meta name=\"author\" content=\"mnihyc\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@mnihyc\" \/>\n<meta name=\"twitter:site\" content=\"@mnihyc\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"mnihyc\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4\" \/>\n\t<meta name=\"twitter:data2\" content=\"5 \u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/mnihyc.com\/blog\/archives\/1024#article\",\"isPartOf\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/archives\/1024\"},\"author\":{\"name\":\"mnihyc\",\"@id\":\"https:\/\/cf.mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751\"},\"headline\":\"YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898\",\"datePublished\":\"2019-03-07T11:24:17+00:00\",\"dateModified\":\"2020-04-22T03:41:36+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/archives\/1024\"},\"wordCount\":169,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/cf.mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751\"},\"articleSection\":[\"6.0 ~ 7.0\",\"\u5e76\u67e5\u96c6\",\"\u6700\u8fd1\u516c\u5171\u7956\u5148\uff08LCA\uff09\",\"\u7ebf\u6bb5\u6811\u5206\u6cbb\"],\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/mnihyc.com\/blog\/archives\/1024#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/mnihyc.com\/blog\/archives\/1024\",\"url\":\"https:\/\/mnihyc.com\/blog\/archives\/1024\",\"name\":\"YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898 - mnihyc&#039;s Blog\",\"isPartOf\":{\"@id\":\"https:\/\/cf.mnihyc.com\/blog\/#website\"},\"datePublished\":\"2019-03-07T11:24:17+00:00\",\"dateModified\":\"2020-04-22T03:41:36+00:00\",\"description\":\"YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898 \u65f6\u95f4\u9650\u5236\uff1a1000MS \u00a0\u00a0\u00a0\u00a0 \u5185\u5b58\u9650\u5236\uff1a262144KB \u96be\u5ea6\uff1a \u95ee\u9898\u63cf\u8ff0 \u67d0\u5c71\u4e0a\u4e00\u5171\u6709 \\\\(n\\\\) \u4e2a\u5e7f\u573a\uff0c\u7f16\u53f7\u4f9d\u6b21\u4e3a \\\\(1\\\\) \u5230 \\\\(n\\\\)\uff0c\u8fd9\u4e9b\u5e7f\u573a\u4e4b\u95f4\u901a\u8fc7 \\\\(n-1\\\\) \u6761\u53cc\u5411\u8f66\u9053\u76f4\u63a5\u6216\u95f4\u63a5\u5730\u8fde\u63a5\u5728\u4e00\u8d77\u3002\u5bf9\u4e8e\u6bcf\u6761\u8f66\u9053 \\\\(i\\\\)\uff0c\u53ef\u4ee5\u7528\u56db\u4e2a\u6b63\u6574\u6570\",\"breadcrumb\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/archives\/1024#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/mnihyc.com\/blog\/archives\/1024\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/mnihyc.com\/blog\/archives\/1024#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9875\",\"item\":\"https:\/\/cf.mnihyc.com\/blog\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/cf.mnihyc.com\/blog\/#website\",\"url\":\"https:\/\/cf.mnihyc.com\/blog\/\",\"name\":\"mnihyc&#039;s Blog\",\"description\":\"Welcome!\",\"publisher\":{\"@id\":\"https:\/\/cf.mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/cf.mnihyc.com\/blog\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"zh-Hans\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\/\/cf.mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751\",\"name\":\"mnihyc\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\/\/cf.mnihyc.com\/blog\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/8d111f863afc3f98816bc96220f97077d470a96f41088de9f19530fc480f8e72?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/8d111f863afc3f98816bc96220f97077d470a96f41088de9f19530fc480f8e72?s=96&d=mm&r=g\",\"caption\":\"mnihyc\"},\"logo\":{\"@id\":\"https:\/\/cf.mnihyc.com\/blog\/#\/schema\/person\/image\/\"}}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898 - mnihyc&#039;s Blog","description":"YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898 \u65f6\u95f4\u9650\u5236\uff1a1000MS \u00a0\u00a0\u00a0\u00a0 \u5185\u5b58\u9650\u5236\uff1a262144KB \u96be\u5ea6\uff1a \u95ee\u9898\u63cf\u8ff0 \u67d0\u5c71\u4e0a\u4e00\u5171\u6709 (n) \u4e2a\u5e7f\u573a\uff0c\u7f16\u53f7\u4f9d\u6b21\u4e3a (1) \u5230 (n)\uff0c\u8fd9\u4e9b\u5e7f\u573a\u4e4b\u95f4\u901a\u8fc7 (n-1) \u6761\u53cc\u5411\u8f66\u9053\u76f4\u63a5\u6216\u95f4\u63a5\u5730\u8fde\u63a5\u5728\u4e00\u8d77\u3002\u5bf9\u4e8e\u6bcf\u6761\u8f66\u9053 (i)\uff0c\u53ef\u4ee5\u7528\u56db\u4e2a\u6b63\u6574\u6570","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/mnihyc.com\/blog\/archives\/1024","og_locale":"zh_CN","og_type":"article","og_title":"YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898 - mnihyc&#039;s Blog","og_description":"YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898 \u65f6\u95f4\u9650\u5236\uff1a1000MS \u00a0\u00a0\u00a0\u00a0 \u5185\u5b58\u9650\u5236\uff1a262144KB \u96be\u5ea6\uff1a \u95ee\u9898\u63cf\u8ff0 \u67d0\u5c71\u4e0a\u4e00\u5171\u6709 (n) \u4e2a\u5e7f\u573a\uff0c\u7f16\u53f7\u4f9d\u6b21\u4e3a (1) \u5230 (n)\uff0c\u8fd9\u4e9b\u5e7f\u573a\u4e4b\u95f4\u901a\u8fc7 (n-1) \u6761\u53cc\u5411\u8f66\u9053\u76f4\u63a5\u6216\u95f4\u63a5\u5730\u8fde\u63a5\u5728\u4e00\u8d77\u3002\u5bf9\u4e8e\u6bcf\u6761\u8f66\u9053 (i)\uff0c\u53ef\u4ee5\u7528\u56db\u4e2a\u6b63\u6574\u6570","og_url":"https:\/\/mnihyc.com\/blog\/archives\/1024","og_site_name":"mnihyc&#039;s Blog","article_published_time":"2019-03-07T11:24:17+00:00","article_modified_time":"2020-04-22T03:41:36+00:00","author":"mnihyc","twitter_card":"summary_large_image","twitter_creator":"@mnihyc","twitter_site":"@mnihyc","twitter_misc":{"\u4f5c\u8005":"mnihyc","\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4":"5 \u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/mnihyc.com\/blog\/archives\/1024#article","isPartOf":{"@id":"https:\/\/mnihyc.com\/blog\/archives\/1024"},"author":{"name":"mnihyc","@id":"https:\/\/cf.mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751"},"headline":"YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898","datePublished":"2019-03-07T11:24:17+00:00","dateModified":"2020-04-22T03:41:36+00:00","mainEntityOfPage":{"@id":"https:\/\/mnihyc.com\/blog\/archives\/1024"},"wordCount":169,"commentCount":0,"publisher":{"@id":"https:\/\/cf.mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751"},"articleSection":["6.0 ~ 7.0","\u5e76\u67e5\u96c6","\u6700\u8fd1\u516c\u5171\u7956\u5148\uff08LCA\uff09","\u7ebf\u6bb5\u6811\u5206\u6cbb"],"inLanguage":"zh-Hans","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/mnihyc.com\/blog\/archives\/1024#respond"]}]},{"@type":"WebPage","@id":"https:\/\/mnihyc.com\/blog\/archives\/1024","url":"https:\/\/mnihyc.com\/blog\/archives\/1024","name":"YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898 - mnihyc&#039;s Blog","isPartOf":{"@id":"https:\/\/cf.mnihyc.com\/blog\/#website"},"datePublished":"2019-03-07T11:24:17+00:00","dateModified":"2020-04-22T03:41:36+00:00","description":"YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898 \u65f6\u95f4\u9650\u5236\uff1a1000MS \u00a0\u00a0\u00a0\u00a0 \u5185\u5b58\u9650\u5236\uff1a262144KB \u96be\u5ea6\uff1a \u95ee\u9898\u63cf\u8ff0 \u67d0\u5c71\u4e0a\u4e00\u5171\u6709 \\(n\\) \u4e2a\u5e7f\u573a\uff0c\u7f16\u53f7\u4f9d\u6b21\u4e3a \\(1\\) \u5230 \\(n\\)\uff0c\u8fd9\u4e9b\u5e7f\u573a\u4e4b\u95f4\u901a\u8fc7 \\(n-1\\) \u6761\u53cc\u5411\u8f66\u9053\u76f4\u63a5\u6216\u95f4\u63a5\u5730\u8fde\u63a5\u5728\u4e00\u8d77\u3002\u5bf9\u4e8e\u6bcf\u6761\u8f66\u9053 \\(i\\)\uff0c\u53ef\u4ee5\u7528\u56db\u4e2a\u6b63\u6574\u6570","breadcrumb":{"@id":"https:\/\/mnihyc.com\/blog\/archives\/1024#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["https:\/\/mnihyc.com\/blog\/archives\/1024"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/mnihyc.com\/blog\/archives\/1024#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"https:\/\/cf.mnihyc.com\/blog"},{"@type":"ListItem","position":2,"name":"YZOJ P3392 \u8d8a\u91ce\u8d5b\u8f66\u95ee\u9898"}]},{"@type":"WebSite","@id":"https:\/\/cf.mnihyc.com\/blog\/#website","url":"https:\/\/cf.mnihyc.com\/blog\/","name":"mnihyc&#039;s Blog","description":"Welcome!","publisher":{"@id":"https:\/\/cf.mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/cf.mnihyc.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"zh-Hans"},{"@type":["Person","Organization"],"@id":"https:\/\/cf.mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751","name":"mnihyc","image":{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/cf.mnihyc.com\/blog\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/8d111f863afc3f98816bc96220f97077d470a96f41088de9f19530fc480f8e72?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/8d111f863afc3f98816bc96220f97077d470a96f41088de9f19530fc480f8e72?s=96&d=mm&r=g","caption":"mnihyc"},"logo":{"@id":"https:\/\/cf.mnihyc.com\/blog\/#\/schema\/person\/image\/"}}]}},"_links":{"self":[{"href":"https:\/\/mnihyc.com\/blog\/wp-json\/wp\/v2\/posts\/1024","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mnihyc.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mnihyc.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mnihyc.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mnihyc.com\/blog\/wp-json\/wp\/v2\/comments?post=1024"}],"version-history":[{"count":0,"href":"https:\/\/mnihyc.com\/blog\/wp-json\/wp\/v2\/posts\/1024\/revisions"}],"wp:attachment":[{"href":"https:\/\/mnihyc.com\/blog\/wp-json\/wp\/v2\/media?parent=1024"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mnihyc.com\/blog\/wp-json\/wp\/v2\/categories?post=1024"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mnihyc.com\/blog\/wp-json\/wp\/v2\/tags?post=1024"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}