만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

균형 트리

시간 제한2초메모리 제한512 MB

요약
일부 노드의 색이 정해진 트리에서 나머지 노드를 검은색 또는 흰색으로 칠해, 모든 노드에 같은 색 노드가 거리 D 이내에 있도록 하는 D의 최솟값을 구합니다.
난이도

어려움10점 중 8점

유형
트리, 동적 계획법, 이분 탐색
정답자
아직 제출이 없습니다

문제

D-균형 트리(D는 양의 정수)는 다음 조건을 만족하는 트리이다.

  • 각 노드는 검은색 또는 흰색이다.
  • 검은색 노드마다, 거리가 D 이하인 다른 검은색 노드가 적어도 하나 있다.
  • 흰색 노드마다, 거리가 D 이하인 다른 흰색 노드가 적어도 하나 있다.

일부 노드의 색이 아직 정해지지 않은 트리가 주어진다. 남은 노드의 색을 정해서 D의 값을 최소화해야 한다. 다만 어떤 양의 정수 D로도 트리가 D-균형이 되지 않을 수 있다(예제 참고).

두 노드 A와 B의 거리는 A에서 B까지 가는 유일한 경로에 있는 간선의 수이다.

정답 D에 대응하는 유효한 색칠까지 찾아야 만점을 받는다.

입력

첫 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같다.

  • 첫 줄에 노드의 개수 N이 주어진다.
  • 이어지는 N-1개의 줄에 간선을 나타내는 (x, y) 쌍이 주어진다.
  • 마지막 줄에 N개의 값 ci가 주어진다.

ci가 0이면 흰색, 1이면 검은색이다. ci가 -1이면 검은색이나 흰색 중 하나를 직접 골라야 한다.

출력

각 테스트 케이스의 답을 별도의 줄에 출력한다.

  • 첫 줄에는 트리가 D-균형이 되는 최소 D를 출력한다. 그런 D가 없으면 -1을 출력하고 다음 줄은 생략한다.
  • 유효한 D가 있으면 둘째 줄에 그 D를 달성하는 노드의 색칠을 출력한다. 고정된 색을 덮어쓰면 오답으로 처리된다.

제한

  • 3 ≤ N ≤ 500 000
  • 한 테스트 안의 모든 트리에 대한 N의 합은 500 000 이하이다.
  • 노드는 1번부터 N번까지 번호가 매겨져 있다.

힌트

예제1

  1. 예제 1

    입력
    3
3
1 2
2 3
0 0 -1
4
1 2
2 3
2 4
0 1 0 0
6
1 2
2 3
2 4
4 5
4 6
1 0 0 -1 1 0
    예상 출력
    1
0 0 0
-1
2
1 0 0 1 1 0