本文共 1569 字，大约阅读时间需要 5 分钟。

1900: 985的“树”难题

Description

985给你一棵“树”以及它的根节点，要求你先判定它是否是一棵树，其次他想知道每个节点的“太子”数目以及它的父亲（root的话输出自己）。

“太子判定条件”： 一、若x是y的孩子节点，那么x是y的“太子”； 二、若x是y的“太子”且y是z的“太子”，那么x是z的“太子”。 Input

第一行输入一个整数t，代表有t组测试数据。

每组数据第一行输入两个整数n，root分别代表树的节点数目以及根节点的编号。 接下来n-1行，每行输出两个整数u，v代表u节点和v节点之间有一条树边。 注：1 <= t <= 20，1 <= n <= 1e4，1 <= root <= n，1 <= u，v <= n。 Output

对每一组数据，若给定的“树”不合法输出NO即可，反之输出YES，接下来输出占两行：

第一行输出n个整数代表每个节点的“太子”数目， 第二行输出n个整数代表每个节点的父亲节点编号。 输出顺序从1到n，每两个数之间有一个空格，最后一个数后面没有空格。 Sample Input

2

3 1 1 2 2 3 2 1 1 1 Sample Output

YES

2 1 0 1 1 2 NO HINT

Source

hpu

树裸题~~

#include
   
    #include
    
     #include
     
      using namespace std;struct node{    int from,to,next;}st[20022];int pa[10011],ma[10011],na[10011],vis[10011];int head[20022],num;bool kl; void add(int x,int y){    st[num].from=x;    st[num].to=y;    st[num].next=head[x];    head[x]=num++;}int find(int p){    while(p!=pa[p])        p=pa[p];    return p;}void DV(int x,int y){    int fx=find(x);    int fy=find(y);    if(fx!=fy)//判断是否有环         pa[fy]=fx;    else kl=true;}void DFS(int pl){    int i;    vis[pl]=1;    for(i=head[pl];i!=-1;i=st[i].next)    {        int v=st[i].to;        if(!vis[v])        {        DFS(v);        ma[pl]+=ma[v];//算出每个节点的太子数目         na[v]=pl;//记录每个节点的父亲节点         }    }}int main(){    int T,N,M,i,a,b,ans;    scanf("%d",&T);    while(T--)    {        num=0;kl=false;        memset(head,-1,sizeof(head));        for(i=1;i<=10011;i++)//初始化         {            pa[i]=i;            ma[i]=1;            na[i]=i;            vis[i]=0;        }        scanf("%d%d",&N,&M);        for(i=1;i
     
    
   

转载地址：https://blog.csdn.net/WYK1823376647/article/details/52472266 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！