【51Nod】1273 旅行计划 树上贪心

【题目】51Nod 1273 旅行计划

【题意】给定n个点的树和出发点k，要求每次选择一个目的地旅行后返回，使得路径上未访问过的点最多（相同取编号最小），旅行后路径上所有点视为访问过，求旅行方案。\(n,k \leq 5*10^4\)。

【算法】贪心

首先显然是访问所有叶子节点，先按叶子节点深度从大到小排序后依次访问，算出到达每个叶子节点路径上未访问过的点数，再按这个从大到小排序输出就是答案。

这里有个问题，就是前面的点访问后，后面的点答案会发生改变，可能会变得不优。但实际上我们考虑会干扰这个点变得不优的其它点都受到了相同的影响，所以它还是最优的。

复杂度\(O(n \ \ log \ \ n )\)。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=50010;

int n,k,tot,cnt,id[maxn],num,first[maxn],deep[maxn],fa[maxn],in[maxn];

bool vis[maxn];

struct edge{int v,from;}e[maxn*2];

void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}

void dfs(int x,int father){

	for(int i=first[x];i;i=e[i].from)if(e[i].v!=father){

		deep[e[i].v]=deep[x]+1;

		fa[e[i].v]=x;

		dfs(e[i].v,x);

	}

}

void find(int x){

	while(x!=k&&!vis[x]){

		num++;vis[x]=1;x=fa[x];

	}

	if(!vis[k])vis[k]=1,num++;

}

bool cmp(int a,int b){return deep[a]>deep[b]||(deep[a]==deep[b]&&a<b);}

int main(){

	scanf("%d%d",&n,&k);

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

		int u;scanf("%d",&u);

		insert(u,i);insert(i,u);in[i]++;in[u]++;

	}

	dfs(k,-1);

	for(int i=0;i<n;i++)if(in[i]==1&&i!=k){

		cnt++;id[cnt]=i;

	}

	sort(id+1,id+cnt+1,cmp);

	for(int i=1;i<=cnt;i++){

		num=0;

		find(id[i]);

		deep[id[i]]=num;

	}

	sort(id+1,id+cnt+1,cmp);

	printf("%d\n",k);for(int i=1;i<=cnt;i++)printf("%d\n",id[i]);

	return 0;

}