LG5536 「XR-3」核心城市树的直径

问题描述

题解

两次 \(\mathrm{dfs}\) 求树的直径。

然后找到树的直径的中点。

然后按照子树中最深的点深度-自己深度排序，贪心选取前 \(k\) 个。

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

template <typename Tp>

void read(Tp &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();

	if(ch=='-') ch=getchar(),fh=-1;

	else fh=1;

	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	x*=fh;

}

const int maxn=1000007;

const int maxm=2000007;

int n,k;

int Head[maxn],to[maxm],Next[maxm],tot;

void add(int x,int y){

	to[++tot]=y,Next[tot]=Head[x],Head[x]=tot;

}

int dep[maxn],dis[maxn],fa[maxn];

int pos;

void dfs1(int x,int f,int dp){

	dep[x]=dp,fa[x]=f;

	for(int i=Head[x];i;i=Next[i]){

		int y=to[i];

		if(y==f) continue;

		dfs1(y,x,dp+1);

	}

}

struct node{

	int id,val;

}ff[maxn];

bool comp(node a,node b){

	return a.val>b.val;

}

void dfs2(int x,int f,int dp){

	fa[x]=f,dep[x]=dp,dis[x]=dep[x];

	for(int i=Head[x];i;i=Next[i]){

		int y=to[i];

		if(y==f) continue;

		dfs2(y,x,dp+1);

		dis[x]=max(dis[x],dis[y]);

	}

//	ff[x].id=x,ff[x].val=dis[x]-dep[x];

}

bool vis[maxn];

int val[maxn];

int main(){

	read(n);read(k);

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

		read(x);read(y);

		add(x,y);add(y,x);

	}

	dfs1(1,0,1);int mx=-1;

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

		if(dep[i]>mx) mx=dep[i],pos=i;

	}

	memset(fa,0,sizeof(fa));

	dfs1(pos,0,1);mx=-1;

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

		if(dep[i]>mx) mx=dep[i],pos=i;

	}

	int pla=pos;

	for(int i=1;i<=(dep[pos]-1)/2;i++) pla=fa[pla];

	memset(fa,0,sizeof(fa));

	dfs2(pla,0,1);

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

		ff[i].val=dis[i]-dep[i];

		ff[i].id=i;val[i]=ff[i].val;

	}

	sort(ff+1,ff+n+1,comp);

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

		vis[ff[i].id]=1;

	}

	int res=-1;

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

		if(!vis[i]) res=max(res,val[i]+1);

	}

	printf("%d\n",res);

	return 0;

}

巴特西

LG5536 「XR-3」核心城市树的直径

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章

巴特西

LG5536 「XR-3」核心城市 树的直径

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章

LG5536 「XR-3」核心城市树的直径