[59测试]A

题目描述

小 A 得到了一棵美丽的有根树。这棵树由 n 个节点以及 n - 1 条有向边构成，每条边都从父

亲节点指向儿子节点，保证除了根节点以外的每个节点都有一个唯一的父亲。树上的节点从1 到 n 标号。该树的一棵子树的定义为某个节点以及从该节点出发能够达到的所有节点的集合，显然这棵树共有 n 棵子树。小 A 认为一棵有根树是美丽的当且仅当这棵树内节点的标号

构成了一个连续的整数区间。现在小 A 想知道这棵树上共有多少棵美丽的子树。

输入输出格式

输入格式

第一行有一个整数 n，表示树的节点数。

接下来 n–1 行，每行两个整数 u，v，表示存在一条从 u 到 v 的有向边。

输入保证该图是一棵有根树。

输出格式

输出一个整数占一行，表示对应的答案。

输入输出样例

输入样例1

4
2 3
2 1
2 4

输出样例1

4

提示

【数据范围】

对于20%的数据，$$1 \leq n \leq 10^3$$

对于100%的数据，$$1 \leq n \leq 10^6$$

思路

dfs

记录从每个节点开始的子树的Max,Min,Sum;

成立条件：Max-Min+1=Sum;

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXNUM=100000;
int n;
struct node{int Max,Min,Sum;}Tree[MAXNUM+5];
int head[MAXNUM+5],nxt[MAXNUM+5],to[MAXNUM+5],cnt=0;
int fa[MAXNUM+5];
int ans=0;

inline void check(int x)
{
    if(!Tree[x].Sum)    Tree[x].Sum=1;
    if(!Tree[x].Max)    Tree[x].Max=Tree[x].Min=x;
}

void add_edge(int u,int v)
{

    cnt++;
    nxt[cnt]=head[u];
    to[cnt]=v;
    head[u]=cnt;
    check(u);check(v);
}

inline void Update(int To,int x)
{
    if(Tree[To].Max>Tree[x].Max)    Tree[x].Max=Tree[To].Max;
    if(Tree[To].Min<Tree[x].Min)    Tree[x].Min=Tree[To].Min;
}

void dfs(int x)
{
    for(int i=head[x];i!=-1;i=nxt[i])
    {
        int To=to[i];
        dfs(To);
        Tree[x].Sum+=Tree[To].Sum;
        Update(To,x);
    }
    if(Tree[x].Max-Tree[x].Min==Tree[x].Sum-1)
        ans++;
}

int main()
{
//    freopen("A.in","r",stdin);
//    freopen("A.out","w",stdout);
    memset(head,-1,sizeof(head));
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        add_edge(u,v);
        fa[v]=1;
    }
    for(int i=1;i<=n;i++)
    {
        if(!fa[i])
        {
            dfs(i);
            break;
        }
    }
    cout<<ans<<endl;
}