시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 148 35 32 36.364%

문제

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+XHViMmU4LCBcdWM1YjRcdWI1YTQgXHViMTc4XHViNGRjXHViOTdjIFx1YzBjOVx1Y2U2MFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgXHVhZGY4IFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWJkODBcdWJhYTggXHViMTc4XHViNGRjXHVhYzAwIFx1Yzc3NFx1YmJmOCBcdWMwYzlcdWNlNjBcdWI0MThcdWM1YjQgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YjhlOFx1ZDJiOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHViYTNjXHVjODAwIFx1YzBjOVx1Y2U2MFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWFkZGNcdWNlNTlcdWM1ZDAgXHViNTMwXHViOTdjIFx1YjU0YywgXHVjZDVjXHVjMThjXHVjNzU4IFx1YmU0NFx1YzZhOVx1YzczY1x1Yjg1YyBcdWQyYjhcdWI5YWNcdWI5N2MgXHVjMGM5XHVjZTYwXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDJiOFx1YjlhYyBcdWIwYjQgXHViMTc4XHViNGRjXHVjNzU4IFx1YzIxOCBOXHVhY2ZjLCBcdWI4ZThcdWQyYjhcdWM3NTggXHViYzg4XHVkNjM4IFJcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSZsdDs9TiZsdDs9MSwwMDAuIDEmbHQ7PVImbHQ7PU4pIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgQ1tpXVx1YWMwMCBcdWNjMjhcdWI4NDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWQ2YzQgTi0xXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQyYjhcdWI5YWMgXHViMGI0XHVjNzU4IFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1MCBcdWMyMThcdWFjMDAgVSwgVlx1Yjc3Y1x1YmE3NCBVXHViYzg4IFx1YjE3OFx1YjRkY1x1YzY0MCBWXHViYzg4IFx1YjE3OFx1YjRkYyBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVhYzA0XHVjMTIwXHVjNzc0IFx1Yzc4OFx1YzczY1x1YmE3MCwgVVx1YWMwMCBWXHVjNzU4IFx1YmQ4MFx1YmFhOFx1Yjc3Y1x1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCwgXHVkMmI4XHViOWFjXHViOTdjIFx1YzBjOVx1Y2U2MFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjEsIDMsIDUsIDIsIDRcdWM3NTggXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzBjOVx1Y2U2MFx1Yzc0NCBcdWQ1NThcdWJhNzQgXHVjYzI4XHViODQwXHViODVjIDEmdGltZXM7MSwgMiZ0aW1lczsxLCAzJnRpbWVzOzQsIDQmdGltZXM7MiwgNSZ0aW1lczsyXHVjNzU4IFx1YmU0NFx1YzZhOVx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWMxMWMgXHVjZDFkIDMzXHVjNzU4IFx1YmU0NFx1YzZhOVx1Yzc3NCBcdWI0ZTRcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTc2MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvbG9yIGEgVHJlZSIsImRlc2NyaXB0aW9uIjoiPHA+Qm9iIGlzIHZlcnkgaW50ZXJlc3RlZCBpbiB0aGUgZGF0YSBzdHJ1Y3R1cmUgb2YgYSB0cmVlLiBBIHRyZWUgaXMgYSBkaXJlY3RlZCBncmFwaCBpbiB3aGljaCBhIHNwZWNpYWwgbm9kZSBpcyBzaW5nbGVkIG91dCwgY2FsbGVkIHRoZSAmcXVvdDtyb290JnF1b3Q7IG9mIHRoZSB0cmVlLCBhbmQgdGhlcmUgaXMgYSB1bmlxdWUgcGF0aCBmcm9tIHRoZSByb290IHRvIGVhY2ggb2YgdGhlIG90aGVyIG5vZGVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Cb2IgaW50ZW5kcyB0byBjb2xvciBhbGwgdGhlIG5vZGVzIG9mIGEgdHJlZSB3aXRoIGEgcGVuLiBBIHRyZWUgaGFzIE4gbm9kZXMsIHRoZXNlIG5vZGVzIGFyZSBudW1iZXJlZCAxLCAyLCAuLi4sIE4uIFN1cHBvc2UgY29sb3JpbmcgYSBub2RlIHRha2VzIDEgdW5pdCBvZiB0aW1lLCBhbmQgYWZ0ZXIgZmluaXNoaW5nIGNvbG9yaW5nIG9uZSBub2RlLCBoZSBpcyBhbGxvd2VkIHRvIGNvbG9yIGFub3RoZXIuIEFkZGl0aW9uYWxseSwgaGUgaXMgYWxsb3dlZCB0byBjb2xvciBhIG5vZGUgb25seSB3aGVuIGl0cyBmYXRoZXIgbm9kZSBoYXMgYmVlbiBjb2xvcmVkLiBPYnZpb3VzbHksIEJvYiBpcyBvbmx5IGFsbG93ZWQgdG8gY29sb3IgdGhlIHJvb3QgaW4gdGhlIGZpcnN0IHRyeS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBub2RlIGhhcyBhICZxdW90O2NvbG9yaW5nIGNvc3QgZmFjdG9yJnF1b3Q7LCBDPHN1Yj5pPFwvc3ViPi4gVGhlIGNvbG9yaW5nIGNvc3Qgb2YgZWFjaCBub2RlIGRlcGVuZHMgYm90aCBvbiBDPHN1Yj5pPFwvc3ViPiBhbmQgdGhlIHRpbWUgYXQgd2hpY2ggQm9iIGZpbmlzaGVzIHRoZSBjb2xvcmluZyBvZiB0aGlzIG5vZGUuIEF0IHRoZSBiZWdpbm5pbmcsIHRoZSB0aW1lIGlzIHNldCB0byAwLiBJZiB0aGUgZmluaXNoaW5nIHRpbWUgb2YgY29sb3Jpbmcgbm9kZSBpIGlzIEY8c3ViPmk8XC9zdWI+LCB0aGVuIHRoZSBjb2xvcmluZyBjb3N0IG9mIG5vZGUgaSBpcyBDPHN1Yj5pPFwvc3ViPiAqIEY8c3ViPmk8XC9zdWI+LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgYSB0cmVlIHdpdGggZml2ZSBub2RlcyBpcyBzaG93biBpbiBGaWd1cmUtMS4gVGhlIGNvbG9yaW5nIGNvc3QgZmFjdG9ycyBvZiBlYWNoIG5vZGUgYXJlIDEsIDIsIDEsIDIgYW5kIDQuIEJvYiBjYW4gY29sb3IgdGhlIHRyZWUgaW4gdGhlIG9yZGVyIDEsIDMsIDUsIDIsIDQsIHdpdGggdGhlIG1pbmltdW0gdG90YWwgY29sb3JpbmcgY29zdCBvZiAzMy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jb2xvcmF0cmVlLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjMyMXB4OyB3aWR0aDozNDJweFwiIFwvPjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIHRyZWUgYW5kIHRoZSBjb2xvcmluZyBjb3N0IGZhY3RvciBvZiBlYWNoIG5vZGUsIHBsZWFzZSBoZWxwIEJvYiB0byBmaW5kIHRoZSBtaW5pbXVtIHBvc3NpYmxlIHRvdGFsIGNvbG9yaW5nIGNvc3QgZm9yIGNvbG9yaW5nIGFsbCB0aGUgbm9kZXMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIHNldmVyYWwgdGVzdCBjYXNlcy4gVGhlIGZpcnN0IGxpbmUgb2YgZWFjaCBjYXNlIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBSICgxICZsZTsgTiAmbGU7Jm5ic3A7MTAwMCwgMSAmbGU7IFIgJmxlOyBOKSwgd2hlcmUgTiBpcyB0aGUgbnVtYmVyIG9mIG5vZGVzIGluIHRoZSB0cmVlIGFuZCBSIGlzIHRoZSBub2RlIG51bWJlciBvZiB0aGUgcm9vdCBub2RlLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgTiBpbnRlZ2VycywgdGhlIGktdGggb2Ygd2hpY2ggaXMgQzxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBDPHN1Yj5pPFwvc3ViPiAmbGU7IDUwMCksIHRoZSBjb2xvcmluZyBjb3N0IGZhY3RvciBvZiBub2RlIGkuIEVhY2ggb2YgdGhlIG5leHQgTi0xIGxpbmVzIGNvbnRhaW5zIHR3byBzcGFjZS1zZXBhcmF0ZWQgbm9kZSBudW1iZXJzIFYxIGFuZCBWMiwgd2hpY2ggYXJlIHRoZSBlbmRwb2ludHMgb2YgYW4gZWRnZSBpbiB0aGUgdHJlZSwgZGVub3RpbmcgdGhhdCBWMSBpcyB0aGUgZmF0aGVyIG5vZGUgb2YgVjIuIE5vIGVkZ2Ugd2lsbCBiZSBsaXN0ZWQgdHdpY2UsIGFuZCBhbGwgZWRnZXMgd2lsbCBiZSBsaXN0ZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkEgdGVzdCBjYXNlIG9mIE4gPSAwIGFuZCBSID0gMCBpbmRpY2F0ZXMgdGhlIGVuZCBvZiBpbnB1dCwgYW5kIHNob3VsZCBub3QgYmUgcHJvY2Vzc2VkLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IGEgbGluZSBjb250YWluaW5nIHRoZSBtaW5pbXVtIHRvdGFsIGNvbG9yaW5nIGNvc3QgcmVxdWlyZWQgZm9yIEJvYiB0byBjb2xvciBhbGwgdGhlIG5vZGVzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Asia > China > Beijing > Beijing Regional Contest 2004 F번

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