HRBUST 1326 循环找父节点神术-白红宇

HRBUST 1326 循环找父节点神术

阅读量：6714 次

发布时间：2019-06-25

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

题意给出一个图给出a点到每个点的路径最后经过的除这个点本身以外的点

现在把a点改为b点让求出按上面那种方式把除b之外的点对应的点列出

...算了我描述题意得能力好差...这个锅还是给出题的吧宝宝不背

这时候就应该用到涛哥教我的循环找父节点神术对就是这个名字

因为说了首都到每个点的路径唯一明显就是一颗树

那么改了首都还是一棵树那么把一开始的首都作为根节点会发现从首都a点到b点的距离外所有的点对应的点其实还是一样的

会发现每个点的对应点在a还是首都的时候都是父节点

从b到a连线除了这条线上的点的父节点需要改变其余的还是一样

记录下来这条线上的点关键就是循环找父节点神术

#include
     
      #include
      
       #include
       
        #include
        #include
         
          using namespace std;int fa[50050];int a[50050];int tot;int n,c,k;void find(int z){    int x=z;    while(x!=c)    {        a[tot++]=x;        x=fa[x];    }    a[tot++]=c;    return ;}int main(){int t;scanf("%d",&t);while(t--){    scanf("%d%d%d",&n,&c,&k);    fa[c]=c;    for(int i=1;i<=n;i++)    {        if(i==c)            continue;        int x;        scanf("%d",&x);        fa[i]=x;    }    tot=0;    find(k);    for(int i=1;i