문제
농부 존은 N(2≤N≤10^5)개의 소가 있습니다. 각 소는 1부터 N까지 번호가 매겨져 있으며, 소들 간의 연결은 트리로 설명됩니다. 불행히도, 전염병이 퍼져 나가고 있습니다.
처음에는 일부 소가 감염되어 있습니다. 감염된 소는 매일 밤 이웃 소에게 전염병을 퍼뜨립니다. 한 번 감염된 소는 계속 감염된 상태로 유지됩니다. 몇 밤 후, 농부 존은 문제가 있다는 것을 깨닫고 소를 테스트하여 어떤 소가 전염병에 걸렸는지를 확인하려고 합니다.
숫자 Q(1≤Q≤20)는 밤의 수에 대한 서로 다른 값이 주어지며, 각 값은 [0,N] 범위의 정수입니다. 각 밤 수에 대해 감염된 소가 시작된 최소 수를 결정하거나 주어진 정보와 호환되지 않으면 -1을 결정하세요.
Farmer John has N (2≤N≤10^5) cows labeled 1…N, where the connections between cows are described by a tree. Unfortunately, there is a sickness spreading throughout.
Initially, some cows start off infected. Every night, an infected cow spreads the sickness to their neighbors. Once a cow is infected, she stays infected. After some amount of nights, Farmer John realizes that there is an issue so he tests his cows to determine who has the sickness.
You are given Q (1≤Q≤20) different values for the number of nights, each an integer in the range [0,N]. For each number of nights, determine the minimum number of cows that could have started with the illness, or that the number of nights is inconsistent with the given information.
입력
첫 번째 줄에는 N이 주어집니다.
다음 줄에는 길이가 N인 비트 문자열이 주어집니다. 여기서 i번째 비트는 i번째 소가 감염되었으면 1이고 그렇지 않으면 0입니다. 적어도 한 마리의 소가 감염되었습니다.
다음 N-1개의 줄에는 트리의 간선이 주어집니다.
그런 다음 Q가 주어지고, 이어서 Q개의 값이 밤 수로 주어집니다.
The first line contains N.
The next line contains a bit string of length N, where the ith bit is 1 if the ith cow is infected and 0 otherwise. At least one cow is infected.
The next N−1 lines contain the edges of the tree.
Then Q, followed by the Q values for the number of nights.
출력
Q개의 줄로 각 밤 수에 대한 답을 출력하십시오. 불가능한 경우 -1을 출력하세요.
Q lines, the answers for each number of nights, or −1 if impossible.
예제 #1
5
11111
1 2
2 3
3 4
4 5
6
5
4
3
2
1
0
1
1
1
1
2
5
첫 네 개의 쿼리에 대한 가능성 중 하나는 소 3만 병에 걸렸을 수 있습니다. 다섯 번째 쿼리 (1밤)에 대한 가능성 중 하나는 소 2와 4가 병에 걸렸을 수 있습니다. 여섯 번째 쿼리 (0밤)에 대한 가능성 중 하나는 다섯 소가 모두 병에 걸렸을 수 있습니다.
For the first four queries, one possibility is that just cow 3 started with the illness. For the fifth query (1 night), one possibility is that cows 2 and 4 started with the illness. For the sixth query (0 nights), one possibility is that all five cows started with the illness.
예제 #2
10
1111111111
1 2
2 3
2 4
2 5
2 6
6 7
7 8
8 9
9 10
11
0
1
2
3
4
5
6
7
8
9
10
10
3
2
1
1
1
1
1
1
1
1
첫 번째 쿼리 (0밤)에 대한 가능성 중 하나는 모든 열 마리가 병에 걸렸을 수 있습니다. 두 번째 쿼리 (1밤)에 대한 가능성 중 하나는 소 2, 7, 9가 병에 걸렸을 수 있습니다. 세 번째 쿼리 (2밤)에 대한 가능성 중 하나는 소 2와 9가 병에 걸렸을 수 있습니다. 네 번째에서 열 번째 쿼리에 대한 가능성 중 하나는 소 7만이 병에 걸렸을 수 있습니다.
For the first query (0 nights), one possibility is that all ten cows started with the illness. For the second query (1 night), one possibility is that cows 2, 7, and 9 started with the illness. For the third query (2 nights), one possibility is that cows 2 and 9 started with the illness. For the fourth to eleventh queries, one possibility is that just cow 7 started with the illness.
예제 #3
5
11100
1 2
2 3
3 4
4 5
6
0
1
2
3
4
5
3
1
1
-1
-1
-1
첫 번째 쿼리 (0밤)에 대한 가능성 중 하나는 소 1, 2, 3이 병에 걸렸을 수 있습니다. 두 번째 쿼리 (1밤)에 대한 가능성 중 하나는 소 2만이 병에 걸렸을 수 있습니다. 세 번째 쿼리 (2밤)에 대한 가능성 중 하나는 소 1만이 병에 걸렸을 수 있습니다. 네 번째부터 여섯 번째 쿼리에 대해서는 일관된 가능성이 없습니다.
For the first query (0 nights), one possibility is that cows 1, 2, and 3 started with the illness. For the second query (1 night), one possibility is that just cow 2 started with the illness. For the third query (2 nights), one possibility is that just cow 1 started with the illness. For the fourth through sixth queries, there is no consistent possibility.
로그인해야 코드를 작성할 수 있어요.