하얀 정점 찾기
다이아몬드 III의견: 0
정점이 \(N\)개인 트리가 주어진다. 모든 간선의 길이는 \(1\)이다. 처음에 모든 정점은 검은색이다.
다음 두 종류의 연산을 총 \(Q\)번 처리해야 한다.
-
0 v: 정점 \(v\)의 색을 반전시킨다. (검은색이면 흰색으로, 흰색이면 검은색으로) -
1 v: 정점 \(v\)에서 가장 가까운 흰색 정점까지의 거리를 출력한다. (정점 \(v\) 자신이 흰색이라면 그 거리는 \(0\)이다.) 흰색 정점이 하나도 없다면 \(-1\)을 출력한다.
두 정점 사이의 거리는 두 정점을 잇는 경로 위에 있는 간선의 개수이다.
\(1 \le N \le 100{,}000\)
\(1 \le Q \le 100{,}000\)
\(1 \le u, v \le N\)이며, 주어지는 간선들은 트리를 이룬다.
각 연산에서 \(1 \le v \le N\)
첫 줄에 정점의 수 \(N\)이 주어진다.
이어서 \(N-1\)개의 줄에 각 간선의 두 끝점 \(u\), \(v\)가 주어진다.
그 다음 줄에 연산의 수 \(Q\)가 주어진다.
이어서 \(Q\)개의 줄에 위 형식의 연산이 한 줄에 하나씩 주어진다.
각 1 연산에 대해 답을 한 줄에 하나씩 출력한다.
5
1 2
2 3
2 4
4 5
8
1 1
0 5
1 1
1 4
0 3
1 1
0 5
1 1
-1
3
1
2
2트리는 1-2-3, 2-4-5 모양이다. 처음엔 흰색이 없어 정점 1의 답은 -1이다. 정점 5를 흰색으로 칠하면 1에서 5까지 거리(1-2-4-5)는 3, 4에서 5까지는 1이다. 정점 3도 흰색으로 칠하면 1에서 가장 가까운 흰색은 3(거리 2)이다. 정점 5를 다시 검게 되돌려도 3이 흰색이므로 1의 답은 여전히 2이다.
2
1 2
6
1 1
0 2
1 1
1 2
0 2
1 2
-1
1
0
-1정점 2개. 흰색이 없으면 -1. 2를 흰색으로 칠하면 1의 답은 1, 2의 답은 0이다. 2를 다시 검게 만들면 흰색이 없어 -1이다.
riseoj 작성
출처 Original
평가 및 의견
하얀 정점 찾기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
하얀 정점 찾기