아주 오래 산 거북이의 등껍질에는 빗물이 흐르는 통로가 새겨져 있다. 통로들은 번 정점을 루트로 하는 순서가 있는 루트 트리를 이룬다. 물방울은 루트에서 출발하여 통로를 따라 내려가고, 어떤 리프에 도착하면 그 리프가 물방울을 받는다.
각 내부 정점 에는 자식 통로 중 하나를 가리키는 회전판이 있다. 의 자식이 입력에서 주어진 순서대로
라 하자. 물방울 하나가 에 도착하면 다음 일이 순서대로 일어난다.
물방울은 하나씩 떨어진다. 하나의 물방울이 리프에 도착한 뒤에 다음 물방울이 루트에서 출발한다.
거북이가 사는 동안 비는 총 번의 계절에 걸쳐 내린다. 번째 계절에는 정확히 개의 물방울이 루트에 차례대로 떨어진다. 한 계절이 끝나도 어떤 회전판도 초기화되지 않으며, 모든 회전판의 상태는 다음 계절까지 그대로 유지된다.
첫 번째 계절이 시작되기 전에, 각 내부 정점의 회전판이 처음 가리킬 자식 통로를 서로 독립적으로 자유롭게 정할 수 있다. 첫 번째 물방울이 떨어진 뒤에는 회전판을 직접 조작할 수 없다.
각 리프 에는 최대 개의 성장판이 있다. 성장판 하나를 완성하려면 모든 계절에서 각각 한 방울씩의 물이 필요하며, 하나의 물방울을 둘 이상의 성장판에 사용할 수는 없다.
리프 가 번째 계절에 개의 물방울을 받았다면, 완성되는 성장판의 수는
이다. 리프 의 성장판 하나가 완성될 때마다 등껍질의 아름다움이 만큼 증가한다.
모든 내부 정점의 회전판이 처음 가리킬 통로를 적절히 정하여, 완성된 등껍질의 아름다움 총합의 최댓값을 구하라.
첫 번째 줄에 정점의 수 과 계절의 수 가 공백으로 구분되어 주어진다.
완성된 등껍질의 아름다움 총합의 최댓값을 출력한다.
루트인 번 정점에는 자식 통로가 순서대로 번, 번, 번 정점을 향해 놓여 있다. 각 계절에는 물방울이 두 개씩 떨어진다.
회전판이 처음 번 정점을 가리키도록 정하자. 첫 번째 계절의 두 물방울은 차례대로 번과 번 정점에 도착하고, 회전판은 번 정점을 가리키게 된다. 두 번째 계절의 두 물방울은 차례대로 번과 번 정점에 도착한다.
두 번째 줄에 각 계절에 떨어지는 물방울의 수를 나타내는 개의 정수 가 공백으로 구분되어 주어진다.
다음 개의 줄에 정점의 정보가 번 정점부터 번 정점까지 순서대로 주어진다.
정점 가 개의 자식을 가지는 내부 정점이라면, 한 줄에 개의 정수
가 공백으로 구분되어 주어진다. 나열된 순서는 회전판이 회전하는 순서이다.
정점 가 리프라면, 한 줄에 세 정수
가 공백으로 구분되어 주어진다.
입력으로 주어지는 정점과 간선은 번 정점을 루트로 하는 트리를 이룬다. 번 정점을 제외한 모든 정점은 정확히 한 번 자식으로 등장한다.
또한 모든 리프 에 대한 의 합은 이하이다.
따라서 두 계절에 모두 물방울을 받은 리프는 번 정점뿐이다. 번 정점에서 성장판 하나가 완성되어 아름다움이 만큼 증가한다.
처음에 번 정점을 가리키면 얻는 아름다움은 , 번 정점을 가리키면 얻는 아름다움은 이다. 따라서 가능한 최댓값은 이다.
