2018 블 루 브리지 컵 시 뮬 레이 션 · 청 출어 람 이 DFS 서 + 트 리 배열 보다 낫다

무당 파 는 모두 nnn 명 으로 문 파 내 nnn 명 은 무공 의 높 고 낮 음 에 따라 순 위 를 매 겼 고 무공 이 가장 높 은 사람 은 111 위, 높 은 사람 은 222 위, 무공 이 가장 낮은 사람 은 nnn 위 를 차지 했다.지금 우 리 는 무공 의 순위 로 모든 사람 에 게 표 시 를 한다. 조상 을 제외 하고 모든 사람 에 게 스승 이 한 명 있 고 모든 사람 에 게 여러 명의 제자 가 있 을 수 있다.
우 리 는 무당 파 의 인재 가 배출 되 어 조상님 의 무공 도 ppp 에 오 를 수 밖 에 없다 는 것 을 안다.즉, 제자 들 의 무공 은 스승 을 능가 할 수 있 으 며, 이른바 청 출어 람 이 람 보다 낫다.
모든 사람의 모든 자제 (제자의 제자, 제자의 제자 포함...) 중 몇 명의 무공 이 그 자신 을 앞 질 렀 는 지 계산 해 주세요.
입력 형식
첫 번 째 줄 의 정수 n, p (1 ≤ n ≤ 100000, 1 ≤ p ≤ n) n, p (1 \ \ le n \ \ le 100000, 1 \ le p \ le n) n, p (1 ≤ n ≤ 100000, 1 ≤ p ≤ n) 를 입력 하 십시오.
다음 n - 1n - 1n - 1 줄 은 각 줄 에 두 개의 정수 u, v (1 ≤ u, v ≤ n) u, v (1 \ \ le u, v \ l n) u, v (1 ≤ u, v ≤ n) 를 입력 하여 uuu 와 vvv 사이 에 사제 관계 가 있 음 을 나타 낸다.
출력 형식
한 줄 의 nnn 개 정 수 를 출력 하고, iii 의 정 수 는 무공 서열 이 iii 인 사람의 자제 가 그 를 얼마나 앞 질 렀 는 지 를 나타 낸다.
줄 끝 에 남 은 빈 칸 을 출력 하지 마 십시오.
샘플 입력

10 5
5 3
5 8
3 4
3 1
2 1
6 7
8 7
9 8
8 10

샘플 출력

0 0 2 0 4 0 1 2 0 0

제목 은 나무 하 나 를 주 고 점 마다 달라 고 하 는 거 예요. 그래서 모든 아이들 의 노드 가 자기 보다 작은 노드 의 수량 이 얼마나 되 는 지.
dfs 에서 모든 노드 의 부모 노드 를 찾 은 다음 에 모든 점 에서 부모 노드 를 계속 위로 찾 을 수 있 습 니 다.
시간 을 초과 하지 않 기 위해
우 리 는 전체 나무의 DFS 순 서 를 만 든 다음 에 임의의 노드 의 순서 와 뒤의 순서 사이 의 차 이 는 바로 이 점 의 아이 노드 의 개수 이다.
하지만 우리 가 찾 아야 할 것 은 아이의 노드 중 그 보다 작은 노드 이다.
그러면 우 리 는 dfs 순서 와 나무 모양 배열 을 결합 하여 dfs 순서 로 나무 모양 문 제 를 구간 상의 문제 로 바 꿀 수 있다.
우 리 는 이 점 의 순서 와 뒷 순 위 를 알 고 있다. 그러면 그 보다 작은 노드 가 이 노드 의 순서 와 뒷 순 서 를 옮 겨 다 닌 다 면
그럼 꼭 맞 는 점 이 겠 네요.
그래서 우 리 는 어 렸 을 때 부터 처리 점 까지 모든 점 에 대해 선 순서 후 순서 위치 에서 트 리 배열 의 저장 차 이 를 조회 할 수 있 습 니 다.
그리고 현재 노드 의 우선 순 서 를 삽입 합 니 다.  이런 장점 은 레이 블 이 작은 노드 를 먼저 옮 겨 다 니 고 작은 노드 의 선 서 를 트 리 배열 에 꽂 는 것 이다.
트 리 배열 이 유지 하 는 것 은 현재 노드 가 먼저 삽입 할 때의 순서 입 니 다. 왜냐하면 우 리 는 앞 순서 와 뒷 순서 가 조건 에 부합 되 는 포 인 트 를 통 해 해결 하기 때 문 입 니 다.

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Vector;

public class Main {
	final static int maxn = 100010; 
	public static int [] tre = new int[maxn];
	public static ArrayList[] gra = new ArrayList[maxn];//  
	public static boolean[] bok = new boolean[maxn];
	public static boolean[] vis = new boolean[maxn];
	public static int[] l = new int[maxn];//    
	public static int[] r = new int[maxn];//             
	public static int time =0 ;
	static void DFS(int now) {
		l[now] = ++time;
		for(int i=0;i();
				gra[s].add(e);
			}
			else gra[s].add(e);
			if(bok[e]==false) {
				bok[e] = true;
				gra[e] = new ArrayList();
				gra[e].add(s);
			}
			else gra[e].add(s);
		}
		vis[p]=true;
		DFS(p);
		for(int i=1;i<=n;i++) {
			System.out.print(sum(r[i])-sum(l[i]));
			add(l[i]);
			if(i==n)System.out.println();
			else System.out.print(" ");
		}
	}
}