51nod-1273: 旅行计划

【传送门：51nod-1273】

---

简要题意：

　　给出一棵树，点数为n，现在你有一个旅行计划，从k城市出发，每天前往一个没去过的城市，并且旅途中经过的没有去过的城市尽可能的多（如果有2条路线，经过的没有去过的城市同样多，优先考虑编号最小的城市），直到所有城市都去过

　　求出每天旅行到达的城市的编号

---

题解：

　　首先，我们先把k作为根，求出每个点的深度

　　我们可以确定每天到达的城市一定是叶子节点，但我们并不能直接根据深度来确定到达城市的编号，因为两个叶子节点之间的路径上的点可能已经走过了，会有重复

　　我们发现每次走都相当于是一条链，我们可以将每个叶子节点的占据一条链（这条链为合理情况下，能够往上走最长的链）

　　对于两个深度相同的叶子节点，我们取编号小的点来占据它自己到公共祖先的路径，编号大的占据它自己到公共祖先的儿子这条路径，维护每个叶子节点占据的点数

　　然后按照点数从大到小，编号从小到大排序输出就可以了

---

参考代码：

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

using namespace std;

struct node

{

    int x,y,next;

}a[];int len,last[];

void ins(int x,int y)

{

    len++;

    a[len].x=x;a[len].y=y;

    a[len].next=last[x];last[x]=len;

}

int dep[];

struct leaf

{

    int x,d;

}p[];int tot;

bool cmp(leaf n1,leaf n2)

{

    if(n1.d==n2.d) return n1.x<n2.x;

    else return n1.d>n2.d;

}

int belong[],K;

void dfs(int x,int fa)

{

    bool bk=false;

    int t=;

    for(int k=last[x];k;k=a[k].next)

    {

        int y=a[k].y;

        if(y==fa) continue;

        bk=true;dep[y]=dep[x]+;

        dfs(y,x);

        if(dep[p[belong[t]].x]<dep[p[belong[y]].x]||(dep[p[belong[y]].x]==dep[p[belong[t]].x]&&p[belong[t]].x>p[belong[y]].x)) t=y;

    }

    if(x==K) return ;

    if(bk==false) belong[x]=++tot,p[tot]=(leaf){x,};

    else belong[x]=belong[t],p[belong[x]].d++;

}

int main()

{

    int n;

    scanf("%d%d",&n,&K);K++;

    len=;memset(last,,sizeof(last));

    for(int i=;i<=n;i++)

    {

        int x;

        scanf("%d",&x);x++;

        ins(x,i);ins(i,x);

    }

    dep[K]=;tot=;dfs(K,);

    sort(p+,p+tot+,cmp);

    printf("%d\n",K-);

    for(int i=;i<=tot;i++) printf("%d\n",p[i].x-);

    return ;

}