{"id":66,"date":"2016-09-18T20:51:57","date_gmt":"2016-09-18T12:51:57","guid":{"rendered":"http:\/\/tyswly.com\/?p=66"},"modified":"2016-09-18T20:51:57","modified_gmt":"2016-09-18T12:51:57","slug":"noip2014%e8%81%94%e5%90%88%e6%9d%83%e5%80%bc","status":"publish","type":"post","link":"https:\/\/tys.fun\/?p=66","title":{"rendered":"[NOIP2014]\u8054\u5408\u6743\u503c"},"content":{"rendered":"<p>\u539f\u9898\u89c1<a href=\"http:\/\/cogs.pro\/cogs\/problem\/problem.php?pid=1804\">COGS<\/a>\u6216<a href=\"http:\/\/syzoj.com\/problem\/80\">SYZOJ<\/a><br \/>\n\u8054\u5408\u6743\u503c\u8fd9\u9053\u9898\u554a\uff0c\u662f\u4e00\u9053\u6570\u5b66\u9898\uff08\u6b64\u5904\u5927\u96fe&#8230;<br \/>\n\u6211\u8fd8\u662f\u6709\u70b9\u4e0d\u80fd\u7406\u89e3\u8fd9\u79cd\u7b97\u6cd5\u3002\u3002\u660e\u5929\u518d\u7ec6\u7ec6\u7814\u7a76\uff0c\u5148\u628a\u4ee3\u7801\u8d34\u51fa\u6765\u3002<br \/>\n\u5bf9\u4e86\uff0c%\u6668\u8000\u9632\u6b62\u7206\u96f6\u3002\u3002<\/p>\n<pre class=\"lang:c++ decode:true \">#include &lt;iostream&gt;\n#include &lt;cstdio&gt;\n#include &lt;algorithm&gt;\n#include &lt;queue&gt;\n#include &lt;vector&gt;\n#define LL long long\n#define Chenyao2333 10007\nusing namespace std;\nconst int MX = 200005;\nLL w[MX];\nLL maxn, sum, n;\nbool vis[MX];\nvector &lt;int&gt; g[MX];\nqueue &lt;int&gt; q;\nint main() {\n\tfreopen(\"linkb.in\", \"r\", stdin);\n\tfreopen(\"linkb.out\", \"w\", stdout);\n\tscanf(\"%lld\", &amp;n);\n\tfor (int i = 1; i &lt; n; i++) {\n\t\tint u, v;\n\t\tscanf(\"%d%d\", &amp;u, &amp;v);\n\t\tg[u].push_back(v);\n\t\tg[v].push_back(u);\n\t}\n\tfor (int i = 1; i &lt;= n; i++) {\n\t\tscanf(\"%lld\", w + i);\n\t}\n\tq.push(1);\n\tvis[1] = 1;\n\twhile (!q.empty()) {\n\t\tint u = q.front();\n\t\tq.pop();\n\t\tLL suma = 0, sumb = 0;\n\t\tLL max1 = 0, max2 = 0;\n\t\t\/\/cout &lt;&lt; g[u].size();\n\t\tfor (int i = 0; i &lt; g[u].size(); i++) {\n\t\t\tint v = g[u][i];\n\t\t\tsuma = (suma + w[g[u][i]]) % Chenyao2333;\n\t\t\tsumb = (sumb + (w[v] * w[v] % Chenyao2333)) % Chenyao2333;\n\t\t\tif (w[v] &gt; max1) {\n\t\t\t\tmax2 = max1;\n\t\t\t\tmax1 = w[v];\n\t\t\t} else if (w[v] &gt; max2) {\n\t\t\t\tmax2 = w[v];\n\t\t\t}\n\t\t\tif (!vis[v]) {\n\t\t\t\tvis[v] = 1;\n\t\t\t\tq.push(v);\n\t\t\t}\n\t\t}\n\t\tsum = (sum + ((suma * suma) % Chenyao2333 - sumb + Chenyao2333) % Chenyao2333) % Chenyao2333;\n\t\tmaxn = max(maxn, max1 * max2);\n\t}\n\tprintf(\"%lld %lld\", maxn, sum);\n\treturn 0;\n}<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u539f\u9898\u89c1COGS\u6216SYZOJ \u8054\u5408\u6743\u503c\u8fd9\u9053\u9898\u554a\uff0c\u662f\u4e00\u9053\u6570\u5b66\u9898\uff08\u6b64\u5904\u5927\u96fe&#8230; \u6211\u8fd8\u662f\u6709\u70b9\u4e0d\u80fd\u7406\u89e3\u8fd9\u79cd\u7b97\u6cd5 &hellip; <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[4],"tags":[],"class_list":["post-66","post","type-post","status-publish","format-standard","hentry","category-report"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/posts\/66","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=66"}],"version-history":[{"count":0,"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/posts\/66\/revisions"}],"wp:attachment":[{"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=66"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=66"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=66"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}