Description

无向连通图 G 有 n 个点,n−1 条边。点从 1 到 n 依次编号,编号为 i 的点的权值为 Wi,每条边的长度均为 1。图上两点 (u,v) 的距离定义为 u 点到 v 点的最短距离。对于图 G 上的点对 (u,v),若它们的距离为 2,则它们之间会产生Wv×Wu 的联合权值。

请问图 G 上所有可产生联合权值的有序点对中,联合权值最大的是多少?所有联合权值之和是多少?

Input Format

第一行包含 1 个整数 n。

接下来 n−1 行,每行包含 2 个用空格隔开的正整数 u,v,表示编号为 u 和编号为 v 的点之间有边相连。

最后 1 行,包含 n 个正整数,每两个正整数之间用一个空格隔开,其中第 i 个整数表示图 G 上编号为 i 的点的权值为 Wi。

Output Format

输出共 1 行,包含 2 个整数,之间用一个空格隔开,依次为图 G 上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大,输出它时要对10007取余。

Sample Input

5
1 2
2 3
3 4
4 5
1 5 2 3 10

Sample Output

20 74

Hint

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAUEAAAEfCAIAAABQ6OPhAAAgAElEQVR4nO3deXRcV50v+iN5TGLHcUKcAMklTQhheIQhsOgwdC4E0p0mt7N6SICVMPP6chne6w48ukO/Bh7NvSyS22FKyOhZtuahNFuyZpVqUlWdYQ+/vc+pSZJleZBkS9YsVb0/jl3Iki1LsqSqkn6fBYlSquG3verrfc4+e++jJBBCmUxJdQEIoeuCGUYos2GGEcpsmGGEMhtmGKHMlpEZHhwc/MEPfvDFL35xamoq1bUglGIZmeH+/v5bb71VUZQLFy6kuhaEUizzMpybm/v2t79dURTMMEKJ68nw9PR0MBh0Op25ubklJSWVlZW1tbVVVVWlpaUFBQXNzc2dnZ1DQ0MrWOsnPvEJ5XKYYYSWk+HR0dHOzs5Dhw7V19cTQqSUnHOYhXPOGGtsbMzLyzt27Nj58+dXpNZPfvKT995777333vvOd74zOzsbM4xQYhkZdrvd+fn5Ho+HMRYKhQzDIITA5UzT5JwTQoQQXq83Ly+vubl5BYseGhq6+eabMcMIJZaa4fr6+pqaGkop55xSmkwvY2x2hg3DEELMfry+vt7hcIyPj69I0UNDQ7t27cIMI5RYfIbj8fihQ4ecTqdlWZFIBACEEEIIfsn8ftgwDMaYuETTtD/84Q/T09PXXzRmGKGkxWa4pqbG5XJRSoUQhmEkT3rnpDfZLXPOZyecUsoYU1W1rKzs+ovGDCOUtKgMt7W1HT9+fHZKKUgqJAcmgAigIIQBUucAEoBpwNn8YNujX21tbYWFhdc5NwMzjFDSojJcXFw854z3UoZBABVAKWcapcy0GOdSMD4vw3ZXbPfJjY2Nvb2911M0ZhihpGtneP/+/T6fb+7RMggqxKUME86pFbIIYxyAc3q1Q2v7iFrTtNzc3OspGjOMUNI1MhyLxRwOx/yTXg7AhOAAAEwAYSQouC4E8wcCdm88+8lCCMZY8uTZNM36+nqn07nsojHDCCUtlOGpqSmn06lp2pwDaTvD9v8AuABigWoRf+7Rg2+96+7DBaUMxJx+2B7fklLakQYAh8Ox7KIxwwglLZThiYmJw4cPm6Y5P8MAnDHKhWCMAdMj3G+4Gx968INKVvbeAgcV5rznXxZp0zSLioqWXTRmGKGkhTI8OjpaXl5OKbUvKV0eYQrAGIAZCr3x2svfeOrxmxRl5xYle+u2g+XHDS4XyLD9Vi0tLT09Pcsr+sKFC/fff//tt98+Ojq6vHdAaN1YKMNnz56tq6uLxWL2BeHLe2EDuAFSGoz91ef+Yoei7FKUGxRF2bzl5fwqIsMLZNgeoPZ4PIcOHVqzdiK0Xi2U4TNnzng8Hl3X5+dQApVAVELMcJgbfrOzsStw/B+f/hsle8urJY0atxbIsD1G7ff7X3/99TVrJ0Lr1TUy7PP5dF23U3d5hhmnGlgWASGZ2kM7erWG//H0f1M2bXu5qMFYsB+2rxIbhvHSSy+tWTsRWq+ukWG/308pvdKwFhVCFdwiEDFMZjLRZxz/4TPv36Zs/2NRiyYX6ocBgBCCGUZoRVwjw06n0zRNSql9WWh2huFihkOGySQzT5LGZ5/5wFZl+ytFzbpcaFyaUgoAeCyN0IpYKMPnzp1rampKrnC47HgYGAhdcMkuZbiXNP/TVx7Yqmx7pbhp4QyHQiHTNNva2g4cOLBm7URovVoow2NjY1ecpAUADDgXhmCScdMwKbBwN237v77ykS3KtteLGgyx0LUle1y6ubm5u7t7zdqJ0Hq1UIYnJyePHDlCCJkfYyqACiKYAC6oJIyHo8z9/a9+dLOy7Y3C+itmePZKYyllcXHxmjUSoXVsoQzH43Gfz2cvObpChiUzmRAcqCScd8XMwHe++vHNyrZDZccNcYUAz/6ZEFJXV7dmjURoHbvGmofe3t7S0lJ7uf/sTBIhiOAmA8kZlbrOYoJ1fv/bD29Rth8sriViboCTPTBjjBDS0NDg9XrXpoUIrW/XXnt44MABt9s9p18lwjQkNxmYjDKpBWlUgCpZBdeZHuolcPliY0qllPbSJfs6c05Ozhq0DaGN4NoZnpmZKS0tnbvrnTB1CSbjIUaZ1DTWDcKImvUhEfLTKLv8dHj2uiVKaU1NTTgcXoO2IbQRLGofD5/PV1dXZ58V26PKBIQhuGTMYoSBTkQX4yRstgMFIqMUrrAXjz1XpKWlpaqqarVbhdDGsagMx+Px48eP+3w+wzBisZi9cfTsZf1XY59Ia5pmWRalVNO0ffv2XecmHgih2Ra7r+Xo6GhlZeXx48ftdYhzxpnnJzmZ8GTa3W53YWHhwMDA5ORkY2OjEGJVG4bQBrG0PeKdTmdZWVlnZ6c9RmUfXc9dWgxgh9zOsB3ghoaGsrKy2dtZxmKxioqKkZGRlW4RQhvLku/VEo1GDx8+3NTUpOt6cgfp+ae+9jiWYRhtbW25ubmBQGD+7vCjo6NOp9Pj8axQWxDaiJZ530Ov11tUVFRXV+d2u+dk2O5+fT7f8ePHS0pK3G73wrtJnzx5srGx8cyZM8urBKEN7rruPxyNRg8dOnTw4MHCwsLi4mKHw1FWVlZUVHTw4MF9+/ZZlrX4t/L7/U1NTTMzM9dTD0Ib0MrcQ/z8+fO9vb1dXV29vb39/f3Li+KZM2caGhpM01yRkhDaIFYmwytI1/WWlhbc7A6hRUq7DCcSiampqeLiYuyQEVqMdMywLRQKNTY2DgwMpLoQhNJa+mbYduzYsXA4jGNdCF1Numc4kUicPXvW4XCcPXs21YUglI4yIMO2QCAQDAYnJiZSXQhC6SVjMpxIJIaHh/Py8vAeSwjNlkkZtjHGqqurJycnU10IQmkh8zKcSCSmp6cbGxsjkUg8Hk91LQilWEZm2Hby5Mnf/e53GGO0wWVwhhOJxNTUlMfj8Xg8mGS0YWV2hm0DAwMNDQ148QltTOshw4lEYmpqKhAIVFRUpLoQhNbaOsmwrb+/v7GxMRQKpboQhNbOusqwjXNeVVWFs0HQBrEOM5xIJM6dO9fe3q6qaqoLQWjVrc8M2wDA5XINDg6muhCEVtF6zrCtoaGBUooXn9B6tf4znEgkuru7jx07durUqVQXgtDK2xAZtrlcLtM0x8fHU10IQitpA2U4kUiMjIy8+eabeIaM1pONlWEbIaS5uXl4eDjVhSC0AjZihm2VlZWnTp3CsS6U6TZuhuPxeFdXV1FR0cK3oUAozW3cDCe1tbUZhoHb7qEMhRlOJBKJwcHBnJwcvAkjykSY4YsmJydVVa2pqUl1IQgtDWb4MhcuXKivrz9x4gSOdaFMgRm+gkgk4nA4Ul0FQouCGb6ygYEBp9NpGEaqC0HoGjDDC5FSNjU1DQ0NpbqQFTMxMZGXl1c4T15eHs5CzVCY4WuYmJhwuVwdHR2pLmRltLW1KVdx+vTpVFeHlgMzvCjRaNTtdvf29qa6kOv12muvKYry4Q9/+Oc///lPL4c30MhQmOElaG1tNU0zo+d1ffe731UU5dixY6kuBK0YzPDSnD59uqamJnM75GeeeUZRFMuyUl0IWjGY4eVQVTUYDGbiyqfHH39827Ztvb29LpcrNzc3NzcXAFJdFLoumOHlKywszLgh6wcffHD+aNbdd9+NJ8OZCzN8XaSUDodjbGws1YUs1o033mjn9t3vfvc///M/33bbbfZ/vve97x0YGEh1dWg5MMMroL6+PhqNZsTtVG+66aZbbrmlrKws+chLL71kx/hv/uZvUlgYWjbM8AqIx+Pnz58/fPhwqgu5tpGRkflHDd/5zncURfngBz+Y0UPuGxZmeMXE43G3293U1JRxS5FN01QU5fbbb8epWpkIM7zCZmZmysrK+vv703Dlk9fr9Xg8kUhkzuO6riuK8sADD2A/nIkwwytvamrKNM3Z55xpYtOmTYqi/OVf/uWcx9///vcrivLZz342444gUAIzvHrOnz/f1NQkpUx1IX/ywgsvKIpyyy23FBQUJB988cUX7TGtF154IYW1oWXDDK+uM2fOlJeXp8955rve9S47sXv27Pn2t7+9e/duRVGysrLe+973pro0tEyY4VU3NDTk9XpdLleqC0kkEolwOGyPQs/2ox/96OzZs6kuDS0TZniNdHd3t7S0pMk9n86fP9/c3FxbW6uqavocI6DlwQyvKafT2dramuoq0LqCGV5rsViso6MjFotdz5sMDAzEYrFoNIrHwAgznBoulwsAFr/yaWxsrLe3t729fd++fSUlJWVlZZWVlVVVVeXl5YWFhQcOHGhoaOju7s6gmdtopWCGU2ZkZKSqqqqrq+uaz2SMFRQUlJeX67pOKaWUCiEAgHMOAABgGAYh5Pjx44WFhe3t7WtQPEofmOEUI4R0dHRcbc1Qb29vbU1NfX29qqqcAwNgABRAAOUADIAJAcCl4IxoAKCqakNjk8PhyNxdCtBSYYbTQnl5+blz52ZPdYzH44ODg7m5ucFgMNnf2qFlQgggHIAKSYUE4AKIBB2AMQAmpaZpeXl5uNP9BoEZThe9vb3l5eUTExP2fwaDwfLyck3TAIBSamf4Ut97sR+mQlAhADgAFUAvZliIUCjEGKutrW1paUlto9AawAynl6amJsMwhBDFxcWUUsuyNE1L9sOz8Ivd8p8eYfb/KbuIc15UVBQKhVLdJrS6MMNpZ2pq6siRI5ZpCiE0TQuHw0IIAAaCCcEEMAGMCsEvHVwnO2QGAMClBL/fL6Xs7OyUUubm5mbE5gRo2TDDaefQoUN+vx84FwCccwacAuWCcaDADROoZAa1IgajEiijGghBhEnMiMGBcwpAhRDJrjsYDGbE5gRo2TDD6SUSiVRXVzPGBAdhHyILzgQzmA6CSiCS6ibRmj3+Y8frG+ur3e1NAKCJUECENZCcGSaQ2cfcUsr6+nrcvHIdwwynl/z8fE3TLmaYX8qwZNICQoKxEATcbV/5+ye233z71u033LJjy803bHvmma+4dQia3S2eADE0ybXLzps5p5Tm5OSkumVotWCG00hfX19JSYmUknMuuRAcGAAVnJqMct00GTf83376qe2KcuNtb3/qS1/6ypf+ftf2zVlZWX/1919285hmRk3JJA3OGf6ilFZWVlJKU90+tCoww2mkqqrK5XLpug4AkgvBRTLDTBDGg83Hq2/euummbOVQaa1GiEn8xUf3btu+Vdm840hVs2ZGBZAQXNYPE0LC4bC90Veq24dWBWY4jVRXV3PODcMAAAEGADWEMKSkAhinUpDf/OcLWVnZX/naN/z0nCDhE3r7KVL/mU/cp2zL/uXrrwVj3cS0LrveBMA5F0IQQsrLy3HKx7qEGU4Xk5OTZWVlFy/1MiaEDsANKQ1pUiGAE6YH//jy7//6rx//zR9eCdKesJBRtbWHNH30gf+y+YYtv3rtjU4rEmRMyLmXkoUQQojS0lLM8LqEGU4XExMTlZWVuq4zxoQQczIcskRYMBOYphlMhsywBuC1iPtXP/tJlpK9eeuuY22dfrB0TqQ1bzoI55zz6upqzPC6hBlOF2NjYw6H40/9MBizM0yJKpkWkowzFtANy2xweyoeffQz22+4ZdPm3b/45e81zQQhZQh0ps4fl+acV1VVYYbXJcxwuhgfH6+trbVXEQKAEISJixnmAKZgJlNNpnNGOwPqr37+vS1blM037Pwv933ot6/lUhY1hSmBUKaLy/th+2RYSllTU4Nbz65LmOF0MT4+XlFRYY8kc87hTxmWHEAwLWoa3Oj0elw7duy8UVG2bN7+Tz/5D4/o0sNdMiQED1igSgnGpQUSc/phPJZerzDD6WJqaqq8vBwATNOcn2HJ9TBXJQk89LEHN2Vn/9V//bva6g5ddAWFaYQ5DQWZ8IXClDEqpDknw4wxACguLsYMr0uY4TRiz8Swu825GWZab5i9/JtfbVaUt7/1Tl9nd6DT1FUGggQMd4D7jRDTOAMhAOYOTHPOCSEVFRWY4XUJM5xGamtrGxsb7ZPYORm2hEH9zm8/8+TWLGXHjTfuuev+O+686x137Lnnjj1vvWPPnrvf9fsD+SRykknJOYV52traqqqqUt0+tCoww2lkaGioqKjI7jlB0IsZFpILJpkaA/XRv3hoa5ayOTtL2bY5a6uyI0u5RVG2K1sU5bb/3F/tEb1UmpzPHZdmjFVUVHi93ubm5sVs34UyC2Y4vTgcDkKIfQZrx8++uju/a72m5JmwpmnJGyypqlpbW4vbX64nmOH00tfXV1hYmNyIQwhh/7DU9Cb/IiCE1NbWdnd3Jz9iZGSkuroaO+R1AzOcdoqLi10ul51emLUB7eIDnNy8lhCiqurevXvnfwrnvLGxcXR0dO0biFYWZjgd5eTkaJompbTnXVJ6hWGqBTIspSSE2Fv5LLByeGZmpry8nDG2lk1DKw4znI7OnDmTm5trHw8nO+TFs19lGEZJSck1N5ru7u5ubGy82gbXKP1hhtPU6dOnCwsLVVU1TRMuH9+ac3TNGDNNk1Jq99sAYBiGYRjFxcWL7GNnZmZaW1uFEHgBORNhhtPXxMTE0aNHvV6vHeBQKGQvLZ5/aE0IiUQilmXZh9CGYbz++usTExNLyuTp06cPHTp0/vz51WsRWg2Y4bTW39/v8/lKSkr8fr+9FsKexTUfpZQxFggEKioqWlpaln0/RJ/PFwgEZt9xAqU5zHAGGBoaKiwsLCsrc7vdydumAYA93EUICQaDbre7tLS0oKAgGo1e58cNDg6WlZXhGXKmwAxnhunp6cHBwWg0evDgwX379h09erSwsLCwsPDo0aP79u3bv3+/EKK/v396enpFPm5mZsYwjNLS0hV5N7SqMMOZanx8fHx8fFU/YmxsrKmpafb8EJSGMMPoGqSUVVVVyZu5oXSDGUbXNjw87HQ6A4FAqgtBV4AZRosVjUZbW1vx4lO6wQyjJYjH4w0NDcFgMNWFoD/BDKMli0aj7e3t15zFidYGZhgtU2tra1dXF451pRxmGC3f4OBgSUnJ4OBgqgvZ0DDD6Hp5vV6Px4NLkVMFM4xWRlFR0dDQEK58WnuYYbQyZmZmAAB3z1x7mGG0kqanpxsaGizLSnUhGwhmGK28s2fPlpWVrdQCDLQwzDBaFYODg36/3+VypbqQ9Q8zjFZRd3d3a2vrsjckQIuBGUara3JyMhAItLW1pbqQdQszjNZCOBz2+/09PT2pLmQdwgyjtdPS0tLT04PTM1cWZhitqYGBgYqKCpzUtYIwwygFOjo6fD7fau8ltEFghlHKFBYWjo2NzczMpLqQzIYZRikzNTUViURweuZ1wgyjFJuZmWloaBBCpLqQTIUZRqkXj8dnZmaOHj2a6kIyEmYYpYuhoSFVVb1eb6oLyTCYYZReQqFQc3MzTs9cPMwwSjsTExMA4Pf7U11IZsAMozQVDoc9Hs/13wJu3cMMo7TW0NDAOcfpmQvADKN0d+7cubq6uv7+/lQXkqYwwygzdHZ2BgIB7JDnwwyjTLJ///7+/n7cPXM2zDDKJDMzM5ZlNTY2prqQNIIZRplnfHy8pqaGc57qQtICZhhlpHg8Pjw8XFhYmOpCUg8zjDLYyMiIrusb/F6q6ZjhkydPnj59+mq/nZiYiMVisVgMLzYgWyQSqa6uXk+3bpuenu7p6RFCWJZ1ze952mX4/Pnzd9xxx9ve9rYr/nbv3r3vec97du/evXv37rvvvvuDH/xgKBRa4wpRGrJ3z/R4PKkuZAUUFxe///3vf8tb3nLDDTfs2LHj7rvvfuSRRxZIctpl+NVXX1UURVGU+dcPXnzxRftXmzZteuCBB+yf3/a2t5mmmZJSUbrp6enp6OiIxWKpLmT59u/fb3+xt27d+vGPf/yee+6x//Pee+/t6+u74kvSJcPnzp3r7u7+6le/qlwyJ8N9fX3243/3d39nPxKNRnfu3Kkoysc//nHczwUlud1ul8s1NTWV6kKWbGhoyA7trbfeOjw8bD/4i1/8wv7m/+AHP7jiq9Ilw29/+9uVy83J8E9/+lP78dkHFT6fT1GU7du3Z/RfvWjF2dMzr9ZxpS0hhKIod95555x9P7/73e8qivLpT3/6iq9Klwx//etff+qpp5566qmPfexjV8zwY489pijKT3/60zkvtMN/7NixNSwWZQZd19va2iYnJ1NdyGIdO3ZMUZRHH310zuMNDQ2KouzateuKr0qXDCcdPHjwihnevXu3oihut3vO85944glFUf71X/91DWtEGWNmZmbv3r2ZsoAxGAz+wz/8w7//+7/PefyPf/xjBvTDSVfLsKIoW7Zs0TRtzvOffvppRVGeffbZNawRZZhwOHz8+PEM3c66rKzMTsTXv/71Kz7hujI8OTl58uTJkydPer3e0tLSI0eOFBcXt7S0nDhx4uTJk2NjY8t4zwUyvHXr1vkZ/ta3vqUoyl133bX8ZqANYHJysrKyEgCW8cITJ0709fV1dnaWl5fn5OSUlJR0dHT09vaeOnVqVW9YceHChaNHj9pxuPvuu7u6uq74tOVnuKamJi8vr6Kioq2tTdM0XdcNw9A0TVXVQCBQWVlZWFiYl5e31CQvNcPPPPOMoih/+7d/u+yGoI1jcHAwPz9/aGhoMU+Ox+MVFRWHDh06duyY2+0mhBBCKKXBYJAxpqpqeXl5QUFBYWHhaqyIbGpquuuuu7KzsxVFueeee3p7e6/2zCVneHx83Ov1FhcXt7e3G4bBGBNCCCEAAAA455xzxhhjDABcLldlZaXb7V78nKrlZXj+KQRCVzQ5Oen3+3VdX+A5U1NTTqfz6NGjLpeLUso5BwDGGCHE/sLb33Nd1wkhbre7sLCwtbU1eTXoOhFCvva1r9kp2LVr169//euF11ouLcOjo6OvvvqqqqqUUkJIMq6UUvufyR9M0zRN0zAMAOjs7Dx06NDg4OBiln1eLcN33HGHoijz7yv/5JNPKorywgsvLKkhaIM7e/ZsXl7e+fPn5/+qv78/Jyeno6MDZrGTbPdVjDEppf0ltx+0LMvlch0+fPjEiRPXWdipU6fs7/+OHTueeOKJxVzlXkKGOefl5eU+n49SKoSglCY73tk/2A22/8kYsx9UVbWqqmoxN5K+WoYfeeQRRVF+9rOfzXm+PV69jPMctMHF43HDMFpbW2d/04QQBQUFqqpKKQkhye/5nG+4/bNhGPYP9ledMVZcXLxwD7+wsbGxBx98UFGUrKysQCCwyFctNsOmaZaWlmqadvGgQjLDso8wwBKSg06kSkyVAQMmGaMgCGUa5zpwXQoKwCjl1bV1Lk/nwh90tQz/5Cc/sR+ffWLw29/+1h7QwvUPaHn6+/ubmprs4aJQKFRcXMwY48BAMC4YE8AEEM6YAAoMBGOc6KZGjIgpgNMWyYCzCDVVKiSwLiE6Kyoqln3fmWAwaM/xWNIJ9qIyHI/HDxw4YBiGfQgRCoWCRDUsZlrS5IIEVOCEmTozDQ5ccFNIkzIDBAOgAIQxgzHKOYAZKi6tuHDhwgKfdbUMnzhxwj6/f/jhh6enp6enpw8cOGA/8wtf+MLiG4zQfB6P59ChQ3v37rXP/oTkIBgIBsAZAOFM1bRwxAKgBtGI1AC6GSHRWECCyXmISZWBABYV0m+aZl5enmVZyyjjc5/7nKIo7373u48ePfrmPFe7udyiMuxwODo7O+2DCiEEY4ybQE1GiGYxblICTGegU2FwzgWTlEszFJHS5JxxRoEzKQRjnAsR0Iy8vLwFloldLcOJRGLfvn32r7Kzs2+//Xb750cffTSDJuKgtHXgwAF72BkAAJi4mGEGwAjRGSNScik5AIUQJdQCzk1LBZ7MMAALg1A554SQgoKC6enppdawdetW5eo+9alPXfFV185wJBJpaGiYc0pAOTM4iYZNoQcjQJih6kTXiG4YBtVJQONBDVQdAKQUUgpJCQEAwjkFCAaDPp/vah/X0tLy2GOPPfbYY1f8bX5+/mc/+9n77rvvz/7szx588MEnn3xyeVehEZqto6OjpaXFHujRdV0ACAABTACTwASnlgRdCzrb25oaG4831hgGcBBB4tep4NwE0AE4cIsLIqUMBAIul2sZ92R9bEHPPffcFV91jQxPTEy88cYb9qDc7HN6EMIwDJMbUdD++OKv3rJ71+7du2/Zfevu3bfedsvu3bfc+bVvfVcnJuOmFBZnTArBOSeMMQEA4HA4lj0ffWZm5sKFC8PDw7hNKVopxcXFdg9sXzoCAAEgOZfATE4E1Y9VV77j7rt27thx886dN++86Y49e44WFKnAVSoYSAACwDgIdmkcmzFWXl6+NmunFspwPB4XQrS3tyeHmpMYAOcgmRpinf/PD/7PTYpy22177nzrO2699fa33nnnrXvu+tq3v69RE2SYMfjTaB4AEyCl9Pl8ixmjRmgNOJ1O+0t+OSEBTE5NZnA9+L773rUpK+s9777/S1/68kMf+eDmzcqNO3flOupUYdqXZwQQLoghLACQUgKA1+stKytbg/oXyvDExERubq59RXtO+xgXQkgTVGE4H/rI/TffdFOn3/AGqDCjmq4awgowU4OQShgIYYc3OUJAKQ2Hwzk5OWvQPIQWNjMzc+DAAVVVL7saDMBBCAGSU5Np//Gz57Ztyv7Ygx9RVU1IM2QEv/DXn1G2bH/i6e8FrQiT1GQgQedS10XUHjOyp07s3bt3GWfFS7VQhsfHxwsKCuyx6DkZ5mBKaZkQpFrzzhs2f+LPP85FzBDdOjd1pgUY12WYWFaQGMKS9ki9nWF+6QJyfX39arcNoWvq6ekpLS21pxX+KcNCUiGFAAnU5NpDH/tgtqIcPnxQJ4RboQhRDx9+Wdm8/c77/0INx5g0TCYl6FyqquhOvhUhpLy8XEq52k1YKMP2Qmp73tX8DDNhCvB7XJXbt2z6/Oc//5s/vPHDf/mPZ//lJ68feN1L9YDgugQiOQHCgYCgdobtUwUAcDqdzc3Nq908hBYWjUabm5vnHGkSKYkpuQQBVHD15d/9+l9+/E+BQJ3JrwAAABaNSURBVCeVQhMiqge//72vK1tuePRLz7pBMqlb1DK5xs2AKk4m+2HOud/vNwxjtZuwUIbPnDnjdDrnnScAAFAuGEgBwfqaIzdtz87O3qRk79i85dasLduzspX7P/RAW6DTz4khKZOUgQGC2CfRABdPj30+3xtvvLHazUNoYbFYTNO0ORk2hEmk4JIJMICr3OgUoEuL5xbm/eT/+8UXPvWJ7CzlxtvfXtfZ12lGuNBMakquMTOgwYnkVOpwOAwA82f4r7hrZNjj8dizoO3T9FmNNHSuRbnIf+V3N2crWzbv+skvXj9aUv37//3zd25Ttmbd8hePfVm3TtBwRGcGFwSEIYAJAAGmaZpCCFVV33zzzdVuHkILs1cyzBvuCQEQBk7LCkrCIzxi8aAl2//xW3+/WVE2K8oWJev2PfeWN3Pd6IoR3WS00+oOmFYY2ua8VWtr62o34RoZ9nq9yaPfyw42AMLdEaF7XVWO3//yf5WV1vqhW5NRi6l6Xd5tO9+6adudbX5BzIhKDBAEBLmUYWEP3+u6/tJLL6128xBaWCAQmH+qyEASwUBqHHSgwImUwAjxBjVPc0vz0bwDDz/04W2bspTttzYHTc65xXVdmqoMAczt0tdg3OfaGSaEzB/WItwkgnWH/d1GIKyahEDApGb3yQiYlqf8gfd+RNl6Z0OHTq0unTEO9FKGuQBhWRalVFXVvXv3rnbzEFoYANjzK2fTGSVCgAwzMDkHXTd0wmS4S+OmJkBE6Emz5X133aBsUvbWtAZlyIKgAGqICIHInAw7nc7VbsK1z4cNw7CXZcyujIuwzkhEen/9/z73nae/09TUbERIEHiIc8tf+777P5S15c7GdiNIQ0yYABwEE4KJS2NalNJAIPDqq6+udvMQWlgsFvP7/XMybIAmrBAxogJi7R2tO3ftuHn37X41TGSPJkFItZvUf/aj71C2Kq/WNHWGLAlBAZTyKGVdAGCvqLfXM6V4TGtkZKS2ttauJrnK30YBKHDJtG986akbszb/8n/+MsB1ERHA/PUl+3Zsf8vb3vEhlfcEiQUyzPnFDNtjWvZ6LpfLtQanCggtLBqN2kuFL1tCKwKckah1CkjIMDxv2bMrK2vzyy8f1YyIYbJekzeWHNy1TVG23FDU7tFMxoWmi5AOMZPxZIYZY8FgkBCy2k24xhyPgoKCUCgEAHPO+wnXuSlAN19+8T83K8pNN+346rf+e4Hj6HP/9p07bt6Rrdz05a9/H8J9BrMIAwAQl+Z4AICUUlXVurq6Nbj8jdDC+vr68vPzk0eadnclIWABCbGwxUAwz6/+5w83Z2XdsvPOf/q/f1xRVfr8j3/y1h03b9m084lvPuuDkBBBJojX7FFFpIv67NFfxpi9XHfZ6xAXb6EMT01NFRUVRSKR5FL+JGESVQ+avFsP+H/0w2/tvnW3knXD5u3Zyiblhi3bvvj0N91BYkCISRMAgHNxcQnIRaZpFhUVrXbbEFqMffv2Jedp2fOrBNdNICHOQ9wwuc/knu/949c3KVlbN2/JzlZ2Zm+9IfvGp7/xbAvp0yEc5Z0AhsfqVWW4i3bYiwssy1JV9fXXX1+DKdPXWPNg33N9/lxLg6qRqMkImCCkMCg1Ducc+c3vXywsOqqphiFM2RWDkKURA4CLiwfSl47DKTUMo6mpabXbhtBiuFyupqYme+DWPtFjXHLgIDUpVRNUovpiYebztrz00m//83+/+Lvfv9Lp9WlE+s3T1OqJskCIBVQRVqUV4p3J77nP5ysoKFiD+q+R4bGxsZycHHtrksv6YSFBUEL9AqSEiGkChU5KCTHC0uzSBdMlDZCAMBkHY06G7S1LFrm3IEJroKSkRNf1ZIYN6NZFmJpBKlXgEA5FhNCE1Um5aooudyjEZKcJviCYqnXCYqSbeCU3dCkN+afJ0qWlpalft2Tzer3Nzc3JLe8ubgtGOQcqTE2A4DTCOREyaJoWZzEOISoZASJDglA9uZDaTi/n4Ha7cZYlSisej8c+3rRPG6mIETNMTZ2aBuVAiAAgIAMMdM7DHSZwM2ByNxWgQkRwHmUBi2sEhC5M+0y4vb19zVbmLWofD3sTacuypJTJvTlhKeztxew/oEOHDuH2Vyh9xOPxyspKe/WSZVn2pSb7ytD86R/z2aFN5oJSquv6wYMH16z+RWV4YGAgNzfXMAxhL/03zfkztxbGOTdNEwBKSkoAoL6+Hu82itJBS0uLEOL8+fPDw8PFxcWBQMC+EAOzlhAu/N22Q5HcAZNSWlpa2tPTs2ZNWOy+lmfOnHE4HKqqhsPhQCAw5/R4YXYLdV2vrq6mlNpvaLczQ2+Bg9aBnp6empqakydPJh8BAIfDcfFwet68pqshhNj9k/2S6upqj8ezlg1Zwv7SY2NjBw8enD9B/JrszeKLi4tnbysbj8dHR0fz8/PPnTu3Cu1CaCGlpaUXLlyYP0PBsqzDhw/7/X77YDM58WOBr7e9E7V9CF1QUHA9+0svz9Lu83Dq1Kn8/PyGhga76OSaj+RRh/1XV/LUVwhBCGlqaioqKrrabp2qqnZ0dKzUfS4QWsDMzIzT6fT7/Ve8w4PtwoULZWVl9pfc/iYnt9qyv9X2lzz5DeecSymbm5tLSkoWuCvS6lnOPdPq6+tLSko8Ho/dx9p5Tm6al5zvYhiGz+erqKgoLS295nuWlpaePn0aZ26hVTIzMzMwMJCfn7/I53s8ntzcXJfLZd9jyY7r7Nzax9vBYNC+FdEarG24mmXe93BkZKS3t/fw4cP5+fnNzc1er1fXdbtbDgQCLS0tpaWl+/btCwQCiz9UPnXqlMPhyJTbPaMMMjo6Wl1d3d3dvaQLtsPDw4ZhvPHGG4WFhU1NTZ2dnfZ9TqSUHo+ntbU1Nzf3zTffJIQs0Kuvgeu9h/jw8HB7e7u9M2BHR4fT6Wxra2ttbV32zaM0TfP7/SMjI9dZGEKJRGJ0dDQYDM6/1d6SDA4OOp1Ot9ttf7fb29tbW1s7OjoGBgZWqs7rcb0ZXg0zMzMVFRWBQGAx90lE6GoGBgaKiorW/VXMdMyw7cSJE9XV1dd/M0i0AfX29jY0NEQikVQXshbSN8M2r9fb1taGh9ZokSYnJ30+33UePGeWdM9wIpGYmZk5cuQI4B2G0bUQQnJzc9dmpUH6yIAM27q7uxsaGvDQGl3RwMDAsWPHYrFYqgtJgYzJsK29vd3lcuHULpR04cIFp9Pp9XpTXUjKZFiGE4nE2NiYvRYy1YWg1JNSVlRUjI6OprqQVMq8DNuEEG632zTNVBeCUqOrq6ujoyMcDqe6kNTL1AzbVFVta2vD24hvKKOjoy6Xq6OjI9WFpIvMznAikTh37hyl1O12p7oQtBbsCY+pnduYbjI+w7ZIJNLa2hoKhVJdCFotUkqXy4XT6edbJxm2nT9/vri4ONVVoJVXWFiIFyOuZl1lOJFIDA8PBwIBPFlaN5qamoLBIAZ4Aestw7ahoaHa2tqTJ0/iqokMFY/HT5w4UVNTk+pCMsD6zHAikZiamorFYgcOHEh1IWg59u/f39vbu+6XHK2IdZvhJJfL5Xa7JycnU10Iurbx8fHOzk48FVqS9Z/hRCJx/vz5oqIivCCR5k6fPl1RUYFr1JZqQ2Q4kUjE4/FQKFRSUrLB5+Wlp/7+fofD0dXVlepCMtJGybBtcnKyo6MD51qnj5mZGVVVfT4fnvou28bKsG1oaCgvL6+vrw9HrVNoZmYmFou98sorOFRxnTZihm0nTpyor6/HL1BKjIyMVFVVdXd3p7qQ9WDjZjiRSExOTtpTCFJdyAYyPDzs8XhcLhceBK2UDZ1h29TU1N69e/FWjGvg5MmTBQUFG22vnNWGGU4kEomZmRkpZVNTE46srJJTp061trZukI0m1xhm+DKFhYVSSrz+tIKGhoYMw6itrU11IesWZniuoaGhsrIyjPGK8Hq9TqcTp22sKszwlfn9fo/HM/vmtGhJLMtyu91Xu9klWkGY4YXU1dWZponXn5ZkfHzc/nNLdSEbBWb4Gvr6+pxOJ15/WqS2tjbDMAYHB1NdyAaCGV4UxlhnZ2ea3OcuPcVisbq6ur6+vlQXsuFghpfA7XbjqvQreuWVV3Azs1TBDC9NT0+Py+XCVRO26enpjo6OQCAwPT2d6lo2LszwcoRCoYaGhg1+aN3X11dVVbXB/xDSAWZ4mSYmJtra2trb21NdSAqMjIwUFhZ2d3fjnOd0gBm+Lv39/U1NTRvqVNDv9+u6jtfb0gdmeAUAQE1NzfDwcKoLWV1dXV25ubm4pVG6wQyvjMnJSbfb7XQ6U13IqpiennY4HGfOnMGD5zSEGV5Jp0+f9nq962mK0sTEhN/vb2trGx8fT3Ut6MowwyvPNM2cnJxMvxvjzMzM4OBgUVFRqgtB14AZXhVjY2OhUKilpSXVhSxTX19fQ0NDV1cXLqhOf5jhVdTX13f8+HEhRKoLWYLBwUEhROb+7bMBYYZXVzwen5iYyMnJSXUhixIKhSorK3GvnMyCGV4L4+PjwWCwra1tpd5wYGAgHA4DQHd394qMNoVCIb/fL6W8/rdCawwzvKYcDsfp06eXMbt4enr6zJkzmqbt27evqKiopKTE4XBUVlaWlZWVlJQcPHiwpKTkzJkzQ0NDS33n0dFRt9ut6/pSX4jSBGZ4TU1PT/f395eWli7pVfb9ohwOh8/n03Wdcw4AjDHGGL8kGAy6XC6Hw3H8+PHFD0Q1NTW53e51PztlfcMMp0ZHR4ff779w4cLCTxsYGOjs7CwvL/f5fHZu7QDPkXycENLa2nro0KFrDqR1d3fX19f39vauXJtQamCGU6moqGh0dPRqk5/GxsZycnJ8Pp8QYn5uF2CaZkVFRVVV1RU7ZHuMLbNGy9ECMMMpFo1G6+rqTpw4Mefx/v7+wsJCr9drWRaldPEB5pxTShljTU1NZWVlc97W4/F0dHRk+vwTNBtmOC24XC7OeXJD3IGBgby8PE3T7EBKKZfUDwshCCFSyvr6+ubmZvs9Y7FYdXU17tS5/mCG08XU1FR+fr69mWtZWZkdYCGEEOKK58ALYIxFIhFVVWOxWFVVVUdHh8PhwJHn9QoznF4ikUhubm5raytwCRw4pxwMDjoXBgPGABhYjIeooUWjYOjONw8V5Re3BIUVCOknSHvM0Pyyxx6ytsNMCDl8+HBPT0+qW4ZWC2Y4vYyMjBw5coQQAiABBAADYYDQQegMGAPBuMV4OBYRqvvYD7/3jLJpz4c/9ZWgJL5IsId4u3S90+yZ0y2rqtrZ2ZnqlqHVghlOL5qmBYNBQggDwUEAcAAGgoKgAAwAgANwYQp/1cE/7tmUrWy9+//4/De4cKqWrtEBQUO6qc8OMCFECFFQUHDu3LlUNw6tCsxwejly5EggEAAAKoAKYEIwkHafLIALIEJoQmhtTcX33333HkXZlH3r+x77JpEuIkiQThLeo1v++WfITqezoaEh1Y1DqwIznEa6u7vLy8uj0SjnnEpGJacgGQ8BDwluSc4laBb4LeF9/HN/vnnrHX/4+b/etPmGDz/xfa8FTBqgn2UsqlranPGtUChECHE4HLgLx7qEGU4jNTU1Pp/Pnjt5KcMm4yHgEcEtTmhYGoJ5nv/Vj7dvufEzT/9zW33+NmXbez7/A7fZLaWvS5chbmrm3IvJnHPGWGVlJWZ4XcIMp5Ha2lr7khLnnApGBTCQwC3gFjAQnFqglhYeuGHrlne+/7828a7m43uzN+9692d/aMiwJVpNg1gGoTwwJ8AAQCltaGjADK9LmOF0EY/H6+rq7D6Tcw4gAAQACOACOHASMrmh+z78ofdt3aK8VuRROWmqe0m58c73/+WPopJJ060SM0QNU849H7YvNTmdzv7+/lS3Eq08zHC6mJ6erqiogEsLGAQzBZeCcwGGEJqQqq57vva1L2VnKz/99+e8cDIkteZjbyjbd37k0a9phk8LWcBOSqCdYW1+hjnnHR0dOEd6XcIMp4vp6emqqqrk0a+kYclMyZkUmhRBEH7G/R944H1ZWVk7d+zYvHnzJkXZqijKlk3Kpi3K1uyv/PhXIbVHmHC8a+7ETPvg3Ol0rqcNN1ESZjhdxOPx2tpaIYR9SgzcvhR88V/SlMFg4IknnvjkJz/50EMPPfLIJz7+sUd23bFdyd6xeesd9z/4rl/86g3Gw4S6TXlqdoAppaZp2hnG2wKvS5jhNFJdXZ1c4n/FsWUppf1bzjqB9VQ25Chbbv7zh/82IL0GP60ZQloBMLrmvFYIYRhGU1MTjmmtS5jhNFJbW+t0Og3DMAxj/jmtaZp2vyqlFKYm4ERVQ56SfePDjz6pWQEqTkVivQZ1SbhsrqW9DjESiRQXF2OG1yXMcBo5c+ZMWVmZYRj2ioU5UUwuY6KUMh4MWb3HWx1K9vZH/uopGtEpOwEyzEWA6KE5r9U0jTFWXV2NGV6XMMPpJScnxx6CuuK4FADYXTQHHSDCQwECISJixNQMFgNhMR6QIjY//83Nzbhl9HqFGU4vkUiks7Nz1lViuMriYQLcYlJlICmEqCSMhwAAhA7cSr4quQixsLBwqZUMDg7m5+c/8cQTn/nMZ5588km3233N3b9QSmCG08vIyMjBgweT6b366n8GXHIwOAgGkgnKQQJwEBS4mN11Sym9Xm8wGFxSGa+99tpb3vIW5XL33Xff/D2DUMphhtNOR0eHPWHLPgy+Sob/dJQNwC/9MCvijNmvDQaD+fn5AwMDiy8gGo3ecsstiqLce++9zz333P79+7/85S/bjyiKktwwCKUJzHA6qq2tdbvd9i48V9uP9uJyYmAXf7i0wJhzlrwQZRhGWVnZUqdY5ufnK4py5513zh4DO3jwoJ1hv9+/0s1F1wUznI7OnTuXl5dnLyS+coa5AGAAUgAVQAQACAOAAQgAamcYAOrq6lpbW5f66V/96lcVRfm3f/u32Q/G43E7w/n5+SvXULQCMMNpamBg4OjRo16vFy5N8CCE2Hmec/U4edRt72Kb3Enr2LFj1dXVy/jo73//+w8//PD+/ftnPyiltDOsadrKtBCtEMxw+hofH6+urm5ubrYnb1FKhRCqqtoXiu0A2z8Eg0H77NcwDCFEIBAoLS01DGOlLgj39/e/613vsjO8jJtFoVWFGU5rk5OTXq/X4XB0dHTYMQYAe8LWbBcvGnOu63p9fX1xcfGKbGR54cKF+++//8Ybb7TTu2PHjtOnT1//26KVhRnODJWVlbm5ue3t7YQQVVUJIckrwHaAVVUtLS0tKChYwTGn4eHhT3/60/fcc8/u3bvtGN98883LuLUiWlWY4Yxx9uzZvr6+ioqKo0ePHjlyxL6DaX5+/uHDh/ft2+f3+0+fPr0i9yKebXJycmJiIhKJPP/883aMn3/++ZX9CHSdMMOZKh6PT01NrcY7j42NXfGGTN/4xjcURXn88cdX40PRsmGG0WXOnj1r97ft7e1zfmVfIv7ABz6QksLQ1WCG0WXGxsbsDL/44otzfvXss88qivLkk0+mpDB0NZhhNNdHP/pRRVEeeuih5OB2PB53OBx2tn/3u9+ltjw0B2YYzeV0Ojdt2qQoys6dO9/3vvd98YtfvO222zZv3ozzpdMTZhhdwb59+/bs2TNn3dI3v/lNvGlTGsIMoyuLx+OU0pdffvn5559/7bXXzp8/n+qK0JVhhhHKbJhhhDIbZhihzIYZRiizYYYRymz/PzyqrSROHnP7AAAAAElFTkSuQmCC" alt="" />

距离为 2 的有序点对有(1,3),(2,4),(3,1),(3,5),(4,2),(5,3)。其联合权值分别为 2,15,2,20,15,20。其中最大的是 20,总和为 74。

对于30%的数据,1<n≤100;

对于60%的数据,1<n≤2000;

对于100%的数据,1<n≤200000,0<Wi≤10000。

保证一定存在可产生联合权值的有序点对。

/*
刚开始用的三重循环,华丽丽的TLE了,70分 (⊙o⊙) !!!
正解:枚举每个点,这个点所连接的任意两点的距离为2,把它们都放到一个数组里,取最大的两个数相乘即为当前最优解,对于所有点取大;至于权值和,补充一个数学知识:
(a+b+c)^2=a*a+b*b+c*c+2ab+2ac+2bc, 2ab+2ac+2bc即为当前和,对于所有点取和。
*/
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#define M 200010
using namespace std;
vector<int> grap[M];
int n,a[M],q[M];
int cmp(const int x,const int y)
{
return a[x]>a[y];
}
int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
grap[x].push_back(y);
grap[y].push_back(x);
}
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
int sum=,maxn=;
for(int i=;i<=n;i++)
{
int cnt=,x=,y=;
if(grap[i].size()>)
{
for(int j=;j<grap[i].size();j++)
{
q[++cnt]=grap[i][j];
x+=a[grap[i][j]];x%=;
y+=a[grap[i][j]]*a[grap[i][j]];y%=;
}
sort(q+,q+cnt+,cmp);
maxn=max(maxn,a[q[]]*a[q[]]);
sum+=x*x-y;
sum=(sum+)%;
}
}
printf("%d %d",maxn,sum);
return ;
}

最新文章

  1. Spring整合Ehcache管理缓存(转)
  2. hihoCoder#1135
  3. iOS开发——UI基础-按钮内边距,图片拉伸
  4. sqlSQL2008如何创建定时作业(代理服务)(转)
  5. 最大子段和问题,最大子矩阵和问题,最大m子段和问题
  6. Spark-1.5.2安装
  7. android 获取IMEI号
  8. poj 2185 (KMP)
  9. amoeba安装与实现amoeba for mysql读写分离
  10. 提交App到Apple Store(Xcode4)
  11. FineUI控件之树的应用(二)
  12. poj2864
  13. 近十年one-to-one最短路算法研究整理【转】
  14. css里面position:relative与position:absolute的区别
  15. PHOTOSHOP常用快捷键大全
  16. R语言之内存管理
  17. linux的shell学习笔记
  18. C 语言:返回两个数组中第一个相同元素的指针(我用了loop 、goto loop标签)
  19. 【Unicode编码表】UniCode编码表+转化器
  20. mysql 分区 限制

热门文章

  1. iOS 随机数(Fixed)
  2. 关于bootstrap栅格系统的五等分以及八等分代码
  3. python之道06
  4. 第2节 azkaban调度:1、azkaban的调度任务使用
  5. lru缓存测试类
  6. 2018-10-09中国裁判文书网爬虫vl5x和DocID分析
  7. 一段式fsm
  8. verilog random使用
  9. Python的第二堂课(1)
  10. shell-code-2-传参