3386 - Induced Favoritism 3386 - Favoritismo Inducido 3386 - Induced Favoritism

Statistics Sub: 118 | AC: 41 | AC%: 34,75 | Score: 2,70
Created by Torneo Argentino de Programación ACM-ICPC 2015 - Melanie Sclar
Added by fidels (2015-10-12)
Limits
Total Time: 30000 MS | Test Time: 2000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

In a kingdom far, far away there are N cities numbered 1 through N, some pairs of cities being connected by roads. When two cities are directly connected by a road, we will say these cities are neighbors. As a result of the careful planning of its monarchs, the kingdom's road system has very special characteristics. We know there are no two cities connected by more than one road, and that all roads connect different cities. Another very peculiar property of the roads is that there is exactly one path between any two cities, consisting of a sequence of roads connecting neighboring cities from the initial to the final one.

In this kingdom far, far away, the king wants to impose curling as the national sport. He therefore wants each city to have a favorite curling team, so that the feeling of belonging of its citizens is enhanced by all of them supporting the same team. There are some cities which already have a favorite team, and because curling is a deep passion these choices cannot be changed. However, other cities don't yet have a favorite curling team, so one will have to be assigned to them in order for it to become the city's favorite.

The president of the Institute for the Competitive Practice of Curling (ICPC) has requested your help, because the king has entrusted it with assigning the favorite teams for the cities that don't yet have one. The problem is that there are too many cities in the kingdom, so the ICPC doesn't really know how to complete this task. We know there are E curling teams which have been numbered 1 through E, and there is no budget to create more. The ICPC has provided you with a riot index between teams for every pair of teams, i.e. an integer D[i, j] representing the degree of hostility between followers of teams i and j, for i, j = 1, 2, ..., E. Note that there even exists a riot index for a given team with itself, as it is possible that inhabitants of two neighboring cities with the same favorite team start to fight in order to see which one has the best following.

The ICPC has asked you to assign a favorite team to every city in the kingdom not having one yet, in such a way that the riots between neighboring cities are minimized. In order to do this, you should minimize the national riot index, which is calculated by summing all the riot indices for teams assigned to neighboring cities. Can you help the ICPC determine the minimum possible value of the national riot index?
En un reino muy muy lejano hay N ciudades numeradas del 1 al N, estando algunos pares de ciudades conectados mediante rutas. Cuando dos ciudades están conectadas directamente por una ruta, se dice que dichas ciudades son vecinas. Como resultado del cuidadoso planeamiento de sus monarcas, el sistema vial del reino tiene características muy especiales. Se sabe que no hay dos rutas que conecten al mismo par de ciudades, y que todas las rutas conectan dos ciudades distintas. Además, una característica muy particular de las rutas es que hay exactamente un camino entre dos ciudades cualesquiera, constituido por una secuencia de rutas que conectan ciudades vecinas desde la ciudad inicial hasta la ciudad final.

En el reino muy muy lejano en cuestión, el rey quiere imponer el curling como deporte nacional. Para ello, quiere que cada ciudad tenga un equipo favorito de curling, pues si toda la ciudad apoya a un mismo equipo se incrementa el sentimiento de pertenencia de sus ciudadanos. Hay algunas ciudades que ya tienen un equipo favorito, y como el curling es pasión de multitudes no se puede cambiar dicha elección. Otras ciudades aún no tienen uno predilecto, de modo que deberá asignárseles un equipo para que pase a ser su favorito.

El presidente del Instituto de Curling Público Competitivo (ICPC) los llamó para pedirles ayuda, porque el rey le encargó que asigne los equipos favoritos para las ciudades que aún no tienen uno. El problema es que hay demasiadas ciudades en el reino, de modo que el ICPC no sabe cómo completar la tarea. Sabemos que en todo el reino hay E equipos que han sido numerados del 1 al E, y no hay presupuesto para crear más. El ICPC les facilitó un índice de disturbios entre equipos para todo par de equipos, es decir un entero D[i,j] que representa el grado de enemistad entre los seguidores de los equipos i y j, para i, j = 1, 2, ..., E. Nótese que incluso existe el índice de disturbios para un equipo consigo mismo, pues podría ocurrir que los habitantes de dos ciudades vecinas con el mismo equipo favorito puedan comenzar a pelearse para ver cuál es la mejor hinchada.

El ICPC les pidió que asignen equipos favoritos para todas las ciudades del reino que aún no tienen uno, de manera tal que se minimicen los disturbios entre ciudades vecinas. Para ello, deben minimizar el índice nacional de disturbios, que se calcula sumando todos los índices de disturbios de equipos asignados a ciudades vecinas. ¿Pueden ayudar al ICPC a determinar cuál es el mínimo valor posible del índice nacional de disturbios?
In a kingdom far, far away there are N cities numbered 1 through N, some pairs of cities being connected by roads. When two cities are directly connected by a road, we will say these cities are neighbors. As a result of the careful planning of its monarchs, the kingdom's road system has very special characteristics. We know there are no two cities connected by more than one road, and that all roads connect different cities. Another very peculiar property of the roads is that there is exactly one path between any two cities, consisting of a sequence of roads connecting neighboring cities from the initial to the final one.

In this kingdom far, far away, the king wants to impose curling as the national sport. He therefore wants each city to have a favorite curling team, so that the feeling of belonging of its citizens is enhanced by all of them supporting the same team. There are some cities which already have a favorite team, and because curling is a deep passion these choices cannot be changed. However, other cities don't yet have a favorite curling team, so one will have to be assigned to them in order for it to become the city's favorite.

The president of the Institute for the Competitive Practice of Curling (ICPC) has requested your help, because the king has entrusted it with assigning the favorite teams for the cities that don't yet have one. The problem is that there are too many cities in the kingdom, so the ICPC doesn't really know how to complete this task. We know there are E curling teams which have been numbered 1 through E, and there is no budget to create more. The ICPC has provided you with a riot index between teams for every pair of teams, i.e. an integer D[i, j] representing the degree of hostility between followers of teams i and j, for i, j = 1, 2, ..., E. Note that there even exists a riot index for a given team with itself, as it is possible that inhabitants of two neighboring cities with the same favorite team start to fight in order to see which one has the best following.

The ICPC has asked you to assign a favorite team to every city in the kingdom not having one yet, in such a way that the riots between neighboring cities are minimized. In order to do this, you should minimize the national riot index, which is calculated by summing all the riot indices for teams assigned to neighboring cities. Can you help the ICPC determine the minimum possible value of the national riot index?

Input specification

The first line contains two integers N and E, representing respectively the number of cities and the number of curling teams in the kingdom (2 <= N <= 5 * 10^4 and 1 <= E <= 50). The following E lines describe the riot indices between the curling teams. Each of these lines contains E integers, the j-th integer of the i-th of these lines being D[i, j], the riot index between teams i and j (0 <= D[i, j] <= 1000 with D[i, j] = D[j, i] for i, j = 1, 2, ..., E).

The following E lines describe the favorite teams of the cities which have already chosen one. The i-th of these lines starts with a non-negative integer K[i] followed by a list of K[i] cities whose favorite team is number i (0 <= K[i] <= N for i = 1, 2, ..., E). No city has more than one favorite team, and there are no repeated cities in the lists.

The last N-1 lines describe the roads between the kingdom's cities. Each of them contains two integers A and B, indicating that there is a road between city A and city B (1 <= A, B <= N with A ≠ B). The roads are bidirectional and there are no repeated roads in the input. It is guaranteed that there is a unique path between every pair of cities, possibly going through other intermediate cities.
La primera línea contiene dos enteros N y E, que representan respectivamente la cantidad de ciudades y la cantidad de equipos de curling que hay en el reino (2 <= N <= 5 * 10^4 y 1 <= E <= 50). Las siguientes E líneas describen los índices de rivalidad entre los equipos de curling. Cada una de estas líneas contiene E enteros, siendo el j-ésimo entero de la i-ésima de estas líneas D[i,j], el índice de disturbios entre los equipos i y j (0 <= D[i,j] <= 1000 con D[i,j] = D[j, i] para i, j = 1, 2, ..., E).

A continuación siguen E líneas que describen los equipos favoritos de las ciudades que ya tienen uno elegido. La i-ésima de estas líneas comienza con un entero no negativo K[i] seguido por una lista de K[i] ciudades cuyo equipo favorito es el número i (0 <= K[i] <= N para i = 1, 2, ..., E). Ninguna ciudad tiene más de un equipo favorito, y no hay elementos repetidos en las listas.

Las últimas N - 1 líneas describen las rutas entre las ciudades del reino. Cada una de ellas contiene dos enteros A y B, indicando que existe una ruta entre la ciudad A y la ciudad B (1 <= A;B <= N con A B). Las rutas son bidireccionales y no hay rutas repetidas en la entrada. Se garantiza además que existe un único camino entre cada par de ciudades, posiblemente pasando por otras ciudades intermedias.
The first line contains two integers N and E, representing respectively the number of cities and the number of curling teams in the kingdom (2 <= N <= 5 * 10^4 and 1 <= E <= 50). The following E lines describe the riot indices between the curling teams. Each of these lines contains E integers, the j-th integer of the i-th of these lines being D[i, j], the riot index between teams i and j (0 <= D[i, j] <= 1000 with D[i, j] = D[j, i] for i, j = 1, 2, ..., E).

The following E lines describe the favorite teams of the cities which have already chosen one. The i-th of these lines starts with a non-negative integer K[i] followed by a list of K[i] cities whose favorite team is number i (0 <= K[i] <= N for i = 1, 2, ..., E). No city has more than one favorite team, and there are no repeated cities in the lists.

The last N-1 lines describe the roads between the kingdom's cities. Each of them contains two integers A and B, indicating that there is a road between city A and city B (1 <= A, B <= N with A ≠ B). The roads are bidirectional and there are no repeated roads in the input. It is guaranteed that there is a unique path between every pair of cities, possibly going through other intermediate cities.

Output specification

Print one line containing an integer representing the minimum value of the national riot index that can be achieved by optimally assigning the favorite teams.
Imprimir en la salida una línea conteniendo un entero que representa el mínimo valor del índice nacional de disturbios que es posible alcanzar si se asignan los equipos favoritos de manera óptima.

The first line contains two integers N and E, representing respectively the number of cities and the number of curling teams in the kingdom (2 <= N <= 5 * 10^4 and 1 <= E <= 50). The following E lines describe the riot indices between the curling teams. Each of these lines contains E integers, the j-th integer of the i-th of these lines being D[i, j], the riot index between teams i and j (0 <= D[i, j] <= 1000 with D[i, j] = D[j, i] for i, j = 1, 2, ..., E).

The following E lines describe the favorite teams of the cities which have already chosen one. The i-th of these lines starts with a non-negative integer K[i] followed by a list of K[i] cities whose favorite team is number i (0 <= K[i] <= N for i = 1, 2, ..., E). No city has more than one favorite team, and there are no repeated cities in the lists.

The last N-1 lines describe the roads between the kingdom's cities. Each of them contains two integers A and B, indicating that there is a road between city A and city B (1 <= A, B <= N with A ≠ B). The roads are bidirectional and there are no repeated roads in the input. It is guaranteed that there is a unique path between every pair of cities, possibly going through other intermediate cities.

Sample input

3 2
2 1
1 2
0
0
1 2
1 3

Sample output

2

Hint(s)

Sample input #2
6 3
3 2 1
2 3 4
1 4 3
2 1 3
0
0
1 2
1 3
1 4
3 5
3 6

Sample output #2
7
Sample input #2
6 3
3 2 1
2 3 4
1 4 3
2 1 3
0
0
1 2
1 3
1 4
3 5
3 6

Sample output #2
7
Sample input #2
6 3
3 2 1
2 3 4
1 4 3
2 1 3
0
0
1 2
1 3
1 4
3 5
3 6

Sample output #2
7

Recommendation

We have carefully selected several similar problems: 3378 | 2824 | 3599 | 1946 | 3147 | 1103