题目描述

珂朵莉给你一个有根树，求有多少个子树满足其内部节点编号在值域上连续

一些数在值域上连续的意思即其在值域上构成一个连续的区间

输入描述:

第一行有一个整数n，表示树的节点数。 接下来n–1行，每行两个整数x,y,表示存在一条从x到y的有向边。 输入保证是一棵有根树。

输出描述:

输出一个数表示答案

示例1

输入

52 32 12 44 5

输出

5

说明

节点1子树中编号为1，值域连续 节点3子树中编号为3，值域连续 节点5子树中编号为5，值域连续 节点4子树中编号为4,5，值域连续 节点2子树中编号为1,2,3,4,5，值域连续

备注:

对于100%的数据，有n <=100000

题解

$dfs$。

只需要统计每个子树的节点数量、最小值以及最大值即可。

#include 
      
       using namespace std;const int maxn = 200000 + 10;int n;int h[maxn], to[maxn], nx[maxn], cnt;int mn[maxn], mx[maxn], sz[maxn], in[maxn];void add(int u, int v) {  to[cnt] = v;  nx[cnt] = h[u];  h[u] = cnt ++;}void dfs(int x) {  sz[x] = 1;  mn[x] = x;  mx[x] = x;  for(int i = h[x]; i != -1; i = nx[i]) {    dfs(to[i]);    sz[x] += sz[to[i]];    mn[x] = min(mn[x], mn[to[i]]);    mx[x] = max(mx[x], mx[to[i]]);  }}int main() {  scanf("%d", &n);  for(int i = 1; i <= n; i ++) {    h[i] = -1;    in[i] = 0;  }  cnt = 0;  for(int i = 1; i < n; i ++) {    int u, v;    scanf("%d%d", &u, &v);    add(u, v);    in[v] ++;  }  for(int i = 1; i <= n; i ++) {    if(in[i] == 0) {      dfs(i);    }  }  int ans = 0;  for(int i = 1; i <= n; i ++) {    if(mx[i] - mn[i] + 1 == sz[i]) ans ++;  }  printf("%d\n", ans);  return 0;}