5364 : B65 - 승진으로의 길 (Hard)
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$명의 사원이 있는 회사에서 각 사원의 "계급"을 구하십시오. 사장 $T$를 제외한 모든 사원은 누군가의 부하이며, 부하가 없는 사원의 계급은 $0$, 부하가 있는 사원의 계급은 직속 부하들의 계급 중 최댓값에 $1$을 더한 값입니다.
[제약 조건]
• $2 \le N \le 100000$
• $1 \le T \le N$
• $1 \le A_i \lt B_i \le N\ (1\le i\le N-1)$
• $i \neq j \implies (A_i,B_i) \neq (A_j,B_j)$
• 주어진 조건을모두만족하는 직속 상사-부하 관계가 반드시 존재합니다.
• 입력되는 모든 값은 정수입니다.
[제약 조건]
• $2 \le N \le 100000$
• $1 \le T \le N$
• $1 \le A_i \lt B_i \le N\ (1\le i\le N-1)$
• $i \neq j \implies (A_i,B_i) \neq (A_j,B_j)$
• 주어진 조건을모두만족하는 직속 상사-부하 관계가 반드시 존재합니다.
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 정수 $N$ 과 사장의 번호 $T$ 가 공백으로 구분되어 주어집니다.
다음 $N-1$ 개 줄에 각 상사-부하 관계를 나타내는 정수 $A_i, B_i$ 가 공백으로 구분되어 주어집니다.
다음 $N-1$ 개 줄에 각 상사-부하 관계를 나타내는 정수 $A_i, B_i$ 가 공백으로 구분되어 주어집니다.
출력 설명
$1$번 사원부터 $N$번 사원까지의 계급을 공백으로 구분하여 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
7 1
1 2
1 3
3 4
2 5
4 6
4 7
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3 1 2 1 0 0 0도움
부여되는 그래프는 다음과 같습니다.