8602: Magic Ritual
内存限制：1024 MB
时间限制：4 S
题面：传统
评测方式：文本比较
上传者：
提交：2
通过：1
题目描述
There is an ancient tree T=(V,E) with n vertices and n−1 edges. The vertices are numbered through 1,2,…,n. A magic ritual lasts mmm days. On the i(1≤i≤m)-th day, there is a subset
Si⊆E of edges being chosen, and you can choose to keep the edges in Si and discard the rest, or you can choose to keep the remaining edges in E∖Si and discard all edges in Si. Either way, the vertices in V will be partitioned into several connected components. By the end of the day, the discarded edges will grow back, and the same tree persists the next day.
You wish to compute, for each vertex v∈V, if you are able to decide whether keeping the edges in Si or E∖Si for each day, what is the maximum possible size of the intersection of the connected components containing v on all m days?
As this is a forbidden ritual, you will not be given the tree T nor the set of edges Si on each day. Instead, you will only receive the information of the connected components after keeping edges in Si or E∖Si respectively for each day. It can be shown that the answer can be uniquely determined given the information.
Si⊆E of edges being chosen, and you can choose to keep the edges in Si and discard the rest, or you can choose to keep the remaining edges in E∖Si and discard all edges in Si. Either way, the vertices in V will be partitioned into several connected components. By the end of the day, the discarded edges will grow back, and the same tree persists the next day.
You wish to compute, for each vertex v∈V, if you are able to decide whether keeping the edges in Si or E∖Si for each day, what is the maximum possible size of the intersection of the connected components containing v on all m days?
As this is a forbidden ritual, you will not be given the tree T nor the set of edges Si on each day. Instead, you will only receive the information of the connected components after keeping edges in Si or E∖Si respectively for each day. It can be shown that the answer can be uniquely determined given the information.
输入格式
The first line contains two integers n,m(1≤n,m≤106,1≤n×m≤106), denoting the size of the tree and the duration of the magic ritual in days, respectively.
Then the information of the mmm days of the magic ritual follows. The information of the i(1≤i≤m)th day of the magic ritual is given as follows:
First, the description of the connected components in the graph Gi=(V,Si) is given. The first line consists of an integer ai(1≤ai≤n), denoting the number of connected components after keeping all edges in Si and discarding the rest.
Then ai lines follow, in the j(1≤j≤ai)-th line an integer k is given, denoting the size of a connected component, then k integers cj,1,cj,2,…,cj,k follows, denoting the number of vertices in the connected component. It is guaranteed that the input given by the ai lines forms a valid decomposition of the vertices.
Then the description of the connected components in the graph Hi=(V,E∖Si) is given. A line follows with an integer bi(1≤bi≤n), denoting the number of connected components after keeping edges in E∖Si and discarding all edges in Si.
Then bi lines follow, in the j(1≤j≤bi)-th line an integer k is given, denoting the size of a connected component, then k integers dj,1,dj,2,…,dj,k follows, denoting the number of vertices in the connected component. It is guaranteed that the input given by the bi lines forms a valid decomposition of the vertices.
It is guaranteed that there exists at least one tree T and choices of S1,S2,…,Sm that are consistent with the input.
Then the information of the mmm days of the magic ritual follows. The information of the i(1≤i≤m)th day of the magic ritual is given as follows:
First, the desc
Then ai lines follow, in the j(1≤j≤ai)-th line an integer k is given, denoting the size of a connected component, then k integers cj,1,cj,2,…,cj,k follows, denoting the number of vertices in the connected component. It is guaranteed that the input given by the ai lines forms a valid decomposition of the vertices.
Then the desc
Then bi lines follow, in the j(1≤j≤bi)-th line an integer k is given, denoting the size of a connected component, then k integers dj,1,dj,2,…,dj,k follows, denoting the number of vertices in the connected component. It is guaranteed that the input given by the bi lines forms a valid decomposition of the vertices.
It is guaranteed that there exists at least one tree T and choices of S1,S2,…,Sm that are consistent with the input.
输出格式
The output consists of a line containing n integers, denoting the answer for the vertices 1,2,…,n, respectively.
输入样例 复制
6 2
3
4 1 2 3 4
1 5
1 6
4
3 2 5 6
1 1
1 3
1 4
3
4 2 3 5 6
1 1
1 4
4
2 1 2
2 3 4
1 5
1 6输出样例 复制
2 3 2 2 3 3数据范围与提示
For the sample test, one valid tree T=(V,E) and choices of S1,S2 corresponding to the input, is given as E={(1,2),(2,3),(3,4),(2,5),(2,6)}, S1={(1,2),(2,3),(3,4)} and S2={(2,3),(2,5),(2,6)}, as shown in the following graphs, where red edges represent edges in S1 and S2, and blue edges represent edges in E∖S1 and E∖S2, respectively.
For vertex 1, one optimal way is to keep S1 and E∖S2, leading to an intersection set {1,2} of size 2.
For vertex 2, one optimal way is to keep E∖S1 and S2, leading to an intersection set {2,5,6} of size 3.
For vertex 3, one optimal way is to keep S1 and S2, leading to an intersection set {2,3} of size 2.
For vertex 4, one optimal way is to keep S1 and E∖S2, leading to an intersection set {2,3} of size 2.
For vertex 5, one optimal way is to keep E∖S1 and S2, leading to an intersection set {2,5,6} of size 3.
For vertex 6, one optimal way is to keep E∖S1 and S2, leading to an intersection set {2,5,6} of size 3.
For vertex 1, one optimal way is to keep S1 and E∖S2, leading to an intersection set {1,2} of size 2.
For vertex 2, one optimal way is to keep E∖S1 and S2, leading to an intersection set {2,5,6} of size 3.
For vertex 3, one optimal way is to keep S1 and S2, leading to an intersection set {2,3} of size 2.
For vertex 4, one optimal way is to keep S1 and E∖S2, leading to an intersection set {2,3} of size 2.
For vertex 5, one optimal way is to keep E∖S1 and S2, leading to an intersection set {2,5,6} of size 3.
For vertex 6, one optimal way is to keep E∖S1 and S2, leading to an intersection set {2,5,6} of size 3.