树的遍历~

本文主要是介绍树的遍历~，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

https://www.luogu.com.cn/problem/P3000

最多删除k条边使得树的直径最小

二分答案,dfs的时候考虑结点u,now记录u的已经遍历的儿子的最大深度,len[j]表示j的最大深度,如果now + len[j] >= mid,把now那条边和j边 长的切断,更新now,最后在这一层,更新len[u] = now +1;

inline int rd() {
	char c;
	int x;
	for (; (c=getchar())<'0'||c>'9';);
	for (x=c-48; (c=getchar())>='0'&&c<='9';) x=x*10+c-48;
	return x;
}

const int N = 2e5 + 50;

int n,k;
int h[N],e[N],ne[N],idx;

void add(int a,int b) {
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int mid,cnt;
int len[N];

void dfs(int u,int fa) {
	int now =0 ;
	for(int i=h[u]; ~i; i=ne[i]) {
		int j = e[i];
		if(j == fa)continue;
		dfs(j,u);
		if(now+len[j] > mid) {
			cnt++;
			now = min(now,len[j]);
		} else {
			now = max(now,len[j]);
		}
	}
	len[u] = now + 1;
}


bool ok() {
	cnt=0;
	dfs(1,-1);
	return cnt <= k;
}

void work() {
	n=rd(),k=rd();
	memset(h,-1,sizeof(h));
	for(int i=1; i<n; i++) {
		int u=rd(),v=rd();
		add(u,v);
		add(v,u);
	}
	int l=1,r=n;
	while(l<r) {
		mid = (l+r)>>1;
		if(ok())r=mid;
		else l=mid+1;
	}
	printf("%d\n",r);
}

这篇关于树的遍历~的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！