코 도리 의 당직 구역 연속 구간

시간 제한: C / C + + 1 초, 기타 언어 2 초
공간 제한: C / C + + 131072 K, 기타 언어 262144 K
64bit IO Format: %lld
제목 설명 
코 돌 리 는 몇 개의 키 나무 가 그 내부 노드 번 호 를 만족 시 키 기 위해 당직 구역 에서 연속 되 는 지 알려 주 었 다.
일부 수 는 당직 구역 에서 연속 적 인 뜻 으로 당직 구역 에서 연속 적 인 구간 을 구성 한 다 는 것 이다.
입력 설명:

        n，       。
   n–1 ，      x,y,       x y    。
          。

출력 설명:

예시 1
입력

5
2 3
2 1
2 4
4 5

출력

5

설명 하 다.

  1      1，    
  3      3，    
  5      5，    
  4      4,5，    
  2      1,2,3,4,5，    

비고:

  100%   ， n <=100000

  ：

dfs  ，        stack queue，    ，            

   k    ，         dfs    

 
   
    ：
  
#include  #include  #include  #include  #include  using namespace std; const int inf = 1e5 + 10; struct node{     int Max;     int Min;     int num;     bool fou = false; }th[inf]; vectors[inf]; int ans; void dfs(int st) {    if(s[st].size() == 0){         th[st].Max = st;         th[st].Min = st;         th[st].num = 1;         ans ++;         //직접 return 은 중복 을 방지 하기 위해 서 입 니 다.        return ;    }    for(int i = 0; i < s[st].size(); i ++){         dfs(s[st][i]);         //최대 값 의 최소 값 을 구 한 노드 와 비교 하여 st 노드 의 최대 최소 값 과 num 을 업데이트 합 니 다.        th[st].Max = max(th[s[st][i]].Max, th[st].Max);         th[st].Min = min(th[s[st][i]].Min, th[st].Min);         th[st].num += th[s[st][i]].num;    }     //루트 노드 의 노드 서비스 가 아 닌 것 을 위해 제목 요구 에 부합 되 는 지 판단 합 니 다.   if(th[st].Max - th[st].Min + 1 == th[st].num){         ans ++;    } } bool root[inf]; int main() {     int n;     scanf("%d", &n);     int k;     for(int i = 1; i <= n; i ++){         root[i] = true;     }     for(int i = 0; i < n - 1; i ++){         int st, ed;         scanf("%d %d", &st, &ed);         root[ed] = false;         s[st].push_back(ed);         th[i + 1].Max = i + 1;         th[i + 1].Min = i + 1;         th[i + 1].num = 1;     }     th[n].Max = n;     th[n].Min = n;     th[n].num = 1;     for(int i = 1; i <= n; i ++){         if(root[i]){             k = i;             break;         }     }     //cout << k;     //k 는 루트 노드    dfs(k);     cout << ans << endl;     return 0; }