시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB64318816035.477%

문제

N개의 노드를 가지고 있으며, 루트가 있는 트리의 각 노드에 가중치가 부여돼 있다. 임의의 노드의 번호를 i라 하고, i번 노드에 부여된 가중치를 C[i]라 한다.

이 트리를 색칠한다고 상상해 보자. 한 노드를 색칠하는 데에는 비용이 드는데, i번 노드가 F[i]번째로 색칠되는 노드라면, i번 노드를 색칠하는 데 드는 비용은 C[i]*F[i]로 계산된다. 전체 트리를 색칠하는 데 드는 비용은 각 노드를 색칠하는 데 드는 비용의 합이다.

단, 어떤 노드를 색칠하기 위해서는 그 노드의 부모 노드가 이미 색칠되어 있어야 한다. 따라서 루트가 가장 먼저 색칠되어야 한다. 이러한 규칙에 따를 때, 최소의 비용으로 트리를 색칠하는 프로그램을 작성하시오.

입력

첫째 줄에 트리 내 노드의 수 N과, 루트의 번호 R이 공백을 사이에 두고 주어진다. (1 ≤ N ≤ 1,000. 1 ≤ R ≤ N) 둘째 줄에는 C[i]가 차례로 주어진다. 이후 N-1개의 줄에는 트리 내의 간선이 두 개의 자연수로 주어진다. 두 수가 U, V라면 U번 노드와 V번 노드 사이에 간선이 있으며, U가 V의 부모라는 뜻이다.

출력

첫째 줄에, 트리를 색칠하기 위한 최소 비용을 출력한다.

예제 입력 1

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

예제 출력 1

33

힌트

1, 3, 5, 2, 4의 순서대로 색칠을 하면 차례로 1×1, 2×1, 3×4, 4×2, 5×2의 비용이 들어서 총 33의 비용이 들게 된다.

W3sicHJvYmxlbV9pZCI6IjE3NjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI5YWMgXHVjMGM5XHVjZTYwIiwiZGVzY3JpcHRpb24iOiI8cD5OXHVhYzFjXHVjNzU4IFx1YjE3OFx1YjRkY1x1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWI4ZThcdWQyYjhcdWFjMDAgXHVjNzg4XHViMjk0IFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMDEgXHViMTc4XHViNGRjXHVjNWQwIFx1YWMwMFx1YzkxMVx1Y2U1OFx1YWMwMCBcdWJkODBcdWM1ZWNcdWIzZmMgXHVjNzg4XHViMmU0LiBcdWM3ODRcdWM3NThcdWM3NTggXHViMTc4XHViNGRjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBpXHViNzdjIFx1ZDU1OFx1YWNlMCwgaVx1YmM4OCBcdWIxNzhcdWI0ZGNcdWM1ZDAgXHViZDgwXHVjNWVjXHViNDFjIFx1YWMwMFx1YzkxMVx1Y2U1OFx1Yjk3YyBDW2ldXHViNzdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWMwYzlcdWNlNjBcdWQ1NWNcdWIyZTRcdWFjZTAgXHVjMGMxXHVjMGMxXHVkNTc0IFx1YmNmNFx1Yzc5MC4gXHVkNTVjIFx1YjE3OFx1YjRkY1x1Yjk3YyBcdWMwYzlcdWNlNjBcdWQ1NThcdWIyOTQgXHViMzcwXHVjNWQwXHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc3NCBcdWI0ZGNcdWIyOTRcdWIzNzAsIGlcdWJjODggXHViMTc4XHViNGRjXHVhYzAwIEZbaV1cdWJjODhcdWM5ZjhcdWI4NWMgXHVjMGM5XHVjZTYwXHViNDE4XHViMjk0IFx1YjE3OFx1YjRkY1x1Yjc3Y1x1YmE3NCwgaVx1YmM4OCBcdWIxNzhcdWI0ZGNcdWI5N2MgXHVjMGM5XHVjZTYwXHVkNTU4XHViMjk0IFx1YjM3MCBcdWI0ZGNcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzQwIENbaV0qRltpXVx1Yjg1YyBcdWFjYzRcdWMwYjBcdWI0MWNcdWIyZTQuIFx1YzgwNFx1Y2NiNCBcdWQyYjhcdWI5YWNcdWI5N2MgXHVjMGM5XHVjZTYwXHVkNTU4XHViMjk0IFx1YjM3MCBcdWI0ZGNcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzQwIFx1YWMwMSBcdWIxNzhcdWI0ZGNcdWI5N2MgXHVjMGM5XHVjZTYwXHVkNTU4XHViMjk0IFx1YjM3MCBcdWI0ZGNcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzU4IFx1ZDU2OVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU4LCBcdWM1YjRcdWI1YTQgXHViMTc4XHViNGRjXHViOTdjIFx1YzBjOVx1Y2U2MFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgXHVhZGY4IFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWJkODBcdWJhYTggXHViMTc4XHViNGRjXHVhYzAwIFx1Yzc3NFx1YmJmOCBcdWMwYzlcdWNlNjBcdWI0MThcdWM1YjQgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YjhlOFx1ZDJiOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHViYTNjXHVjODAwIFx1YzBjOVx1Y2U2MFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWFkZGNcdWNlNTlcdWM1ZDAgXHViNTMwXHViOTdjIFx1YjU0YywgXHVjZDVjXHVjMThjXHVjNzU4IFx1YmU0NFx1YzZhOVx1YzczY1x1Yjg1YyBcdWQyYjhcdWI5YWNcdWI5N2MgXHVjMGM5XHVjZTYwXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDJiOFx1YjlhYyBcdWIwYjQgXHViMTc4XHViNGRjXHVjNzU4IFx1YzIxOCBOXHVhY2ZjLCBcdWI4ZThcdWQyYjhcdWM3NTggXHViYzg4XHVkNjM4IFJcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxLDAwMC4gMSAmbGU7IFIgJmxlOyBOKSBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IENbaV1cdWFjMDAgXHVjYzI4XHViODQwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHVkNmM0IE4tMVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMmI4XHViOWFjIFx1YjBiNFx1Yzc1OCBcdWFjMDRcdWMxMjBcdWM3NzQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM3OTBcdWM1ZjBcdWMyMThcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHVjMjE4XHVhYzAwIFUsIFZcdWI3N2NcdWJhNzQgVVx1YmM4OCBcdWIxNzhcdWI0ZGNcdWM2NDAgVlx1YmM4OCBcdWIxNzhcdWI0ZGMgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM3ODhcdWM3M2NcdWJhNzAsIFVcdWFjMDAgVlx1Yzc1OCBcdWJkODBcdWJhYThcdWI3N2NcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAsIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWMwYzlcdWNlNjBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWJlNDRcdWM2YTlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD4xLCAzLCA1LCAyLCA0XHVjNzU4IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWMwYzlcdWNlNjBcdWM3NDQgXHVkNTU4XHViYTc0IFx1Y2MyOFx1Yjg0MFx1Yjg1YyAxJnRpbWVzOzEsIDImdGltZXM7MSwgMyZ0aW1lczs0LCA0JnRpbWVzOzIsIDUmdGltZXM7Mlx1Yzc1OCBcdWJlNDRcdWM2YTlcdWM3NzQgXHViNGU0XHVjNWI0XHVjMTFjIFx1Y2QxZCAzM1x1Yzc1OCBcdWJlNDRcdWM2YTlcdWM3NzQgXHViNGU0XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjE3NjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb2xvciBhIFRyZWUiLCJkZXNjcmlwdGlvbiI6IjxwPkJvYiBpcyB2ZXJ5IGludGVyZXN0ZWQgaW4gdGhlIGRhdGEgc3RydWN0dXJlIG9mIGEgdHJlZS4gQSB0cmVlIGlzIGEgZGlyZWN0ZWQgZ3JhcGggaW4gd2hpY2ggYSBzcGVjaWFsIG5vZGUgaXMgc2luZ2xlZCBvdXQsIGNhbGxlZCB0aGUgJnF1b3Q7cm9vdCZxdW90OyBvZiB0aGUgdHJlZSwgYW5kIHRoZXJlIGlzIGEgdW5pcXVlIHBhdGggZnJvbSB0aGUgcm9vdCB0byBlYWNoIG9mIHRoZSBvdGhlciBub2Rlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Qm9iIGludGVuZHMgdG8gY29sb3IgYWxsIHRoZSBub2RlcyBvZiBhIHRyZWUgd2l0aCBhIHBlbi4gQSB0cmVlIGhhcyBOIG5vZGVzLCB0aGVzZSBub2RlcyBhcmUgbnVtYmVyZWQgMSwgMiwgLi4uLCBOLiBTdXBwb3NlIGNvbG9yaW5nIGEgbm9kZSB0YWtlcyAxIHVuaXQgb2YgdGltZSwgYW5kIGFmdGVyIGZpbmlzaGluZyBjb2xvcmluZyBvbmUgbm9kZSwgaGUgaXMgYWxsb3dlZCB0byBjb2xvciBhbm90aGVyLiBBZGRpdGlvbmFsbHksIGhlIGlzIGFsbG93ZWQgdG8gY29sb3IgYSBub2RlIG9ubHkgd2hlbiBpdHMgZmF0aGVyIG5vZGUgaGFzIGJlZW4gY29sb3JlZC4gT2J2aW91c2x5LCBCb2IgaXMgb25seSBhbGxvd2VkIHRvIGNvbG9yIHRoZSByb290IGluIHRoZSBmaXJzdCB0cnkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggbm9kZSBoYXMgYSAmcXVvdDtjb2xvcmluZyBjb3N0IGZhY3RvciZxdW90OywgQzxzdWI+aTxcL3N1Yj4uIFRoZSBjb2xvcmluZyBjb3N0IG9mIGVhY2ggbm9kZSBkZXBlbmRzIGJvdGggb24gQzxzdWI+aTxcL3N1Yj4gYW5kIHRoZSB0aW1lIGF0IHdoaWNoIEJvYiBmaW5pc2hlcyB0aGUgY29sb3Jpbmcgb2YgdGhpcyBub2RlLiBBdCB0aGUgYmVnaW5uaW5nLCB0aGUgdGltZSBpcyBzZXQgdG8gMC4gSWYgdGhlIGZpbmlzaGluZyB0aW1lIG9mIGNvbG9yaW5nIG5vZGUgaSBpcyBGPHN1Yj5pPFwvc3ViPiwgdGhlbiB0aGUgY29sb3JpbmcgY29zdCBvZiBub2RlIGkgaXMgQzxzdWI+aTxcL3N1Yj4gKiBGPHN1Yj5pPFwvc3ViPi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGEgdHJlZSB3aXRoIGZpdmUgbm9kZXMgaXMgc2hvd24gaW4gRmlndXJlLTEuIFRoZSBjb2xvcmluZyBjb3N0IGZhY3RvcnMgb2YgZWFjaCBub2RlIGFyZSAxLCAyLCAxLCAyIGFuZCA0LiBCb2IgY2FuIGNvbG9yIHRoZSB0cmVlIGluIHRoZSBvcmRlciAxLCAzLCA1LCAyLCA0LCB3aXRoIHRoZSBtaW5pbXVtIHRvdGFsIGNvbG9yaW5nIGNvc3Qgb2YgMzMuJm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY29sb3JhdHJlZS5naWZcIiBzdHlsZT1cImhlaWdodDozMjFweDsgd2lkdGg6MzQycHhcIiBcLz48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSB0cmVlIGFuZCB0aGUgY29sb3JpbmcgY29zdCBmYWN0b3Igb2YgZWFjaCBub2RlLCBwbGVhc2UgaGVscCBCb2IgdG8gZmluZCB0aGUgbWluaW11bSBwb3NzaWJsZSB0b3RhbCBjb2xvcmluZyBjb3N0IGZvciBjb2xvcmluZyBhbGwgdGhlIG5vZGVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIFIgKDEgJmxlOyBOICZsZTsmbmJzcDsxMDAwLCAxICZsZTsgUiAmbGU7IE4pLCB3aGVyZSBOIGlzIHRoZSBudW1iZXIgb2Ygbm9kZXMgaW4gdGhlIHRyZWUgYW5kIFIgaXMgdGhlIG5vZGUgbnVtYmVyIG9mIHRoZSByb290IG5vZGUuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyBOIGludGVnZXJzLCB0aGUgaS10aCBvZiB3aGljaCBpcyBDPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IEM8c3ViPmk8XC9zdWI+ICZsZTsgNTAwKSwgdGhlIGNvbG9yaW5nIGNvc3QgZmFjdG9yIG9mIG5vZGUgaS4gRWFjaCBvZiB0aGUgbmV4dCBOLTEgbGluZXMgY29udGFpbnMgdHdvIHNwYWNlLXNlcGFyYXRlZCBub2RlIG51bWJlcnMgVjxzdWI+MTxcL3N1Yj4gYW5kIFY8c3ViPjI8XC9zdWI+LCB3aGljaCBhcmUgdGhlIGVuZHBvaW50cyBvZiBhbiBlZGdlIGluIHRoZSB0cmVlLCBkZW5vdGluZyB0aGF0IFY8c3ViPjE8XC9zdWI+IGlzIHRoZSBmYXRoZXIgbm9kZSBvZiBWPHN1Yj4yPFwvc3ViPi4gTm8gZWRnZSB3aWxsIGJlIGxpc3RlZCB0d2ljZSwgYW5kIGFsbCBlZGdlcyB3aWxsIGJlIGxpc3RlZC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIGxpbmUgY29udGFpbmluZyB0aGUgbWluaW11bSB0b3RhbCBjb2xvcmluZyBjb3N0IHJlcXVpcmVkIGZvciBCb2IgdG8gY29sb3IgYWxsIHRoZSBub2Rlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Asia East Continent > China > Beijing > Beijing Regional Contest 2004 F번

  • 잘못된 조건을 찾은 사람: shjgkwo