USACO 2018 December, Platinum 3- 트리 지우기 > 문제은행 : 정보올림피아드&알고리즘




3383 : 트리 지우기

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
2 회   
시도횟수
29 회   

문제

 

 

N개의 정점으로 이루어진 트리가 있다.

이 트리의 정점들을 하나씩 지워보려고 한다. 

그러나 트리가 둘로 쪼개지면 어수선하기 때문에, 한 정점이 없어지더라도 트리가 하나로 유지하도록 하려고 한다. 

어떤 한 정점은 다른 정점보다 먼저 없어져야 한다. 이런 우선순위 정점 관계가 총 M개 있다.

각 N개의 정점에 있어서, 그게 제일 마지막으로 지워지는 정점일 수 있는지 없는지 검사하는 프로그램을 작성하라.


입력형식

첫 줄에 N과 M이 공백을 사이에 두고 주어진다.(1 <= N <= 100,000, 1 <= M <= 100,000) 다음 N-1줄엔 x y가 입력되며, 이는 x와 y가 서로 연결되어 있다는 의미이다. 다음 M줄에 a b가 입력되며, 이는 a가 b보다 먼저 사라져야 하는 정점이라는 의미이다. 1 <= a,b,x,y <= N이다. 20%의 입력 데이터에 있어서, N,M <= 3,000임을 보장한다.

출력형식

N줄에 걸쳐서 각 줄에 해당하는 정점이 마지막으로 지워질 수 있으면 1, 없으면 0을 출력한다.

입력 예

5 1
1 2
2 3
3 4
4 5
2 4

출력 예

0
0
1
1
1


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP