专栏文章

题解 P11294 【NOISG2022-Qualification Tree Cutting】

破破壁人罗辑
P11294题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miqsu5zq
此快照首次捕获于
2025/12/04 10:10
3 个月前
此快照最后确认于
2025/12/04 10:10
3 个月前
查看原文
题目传送门：P11294 [NOISG2022 Qualification] Tree Cutting

题目大意

在一棵树上删除一条边并增加一条边，问新生成的树的最大直径。

解题思路

删除一条边之后，一棵树会变成两棵树，显然此时最好情况是将两棵树的直径相连。枚举每一条边计算即可。
可以使用 dfs，对于每个节点除去和它的每个子节点，计算该节点除去这个子节点后所在的树的直径和这个子节点的子树直径，相加再加一，取最大值即为答案。
可以在第一次 dfs 中计算计算每个节点的子树直径、子树最远节点距离、子树非严格次远节点距离、子树非严格第三远节点距离，在第二次 dfs 中计算非子树最远节点距离，然后由这些值计算出直径即可。时间复杂度 O(n)O(n)，可通过此题。

AC 代码

CPP
#include<bits/stdc++.h>
using namespace std;
vector<int>to[300001];
bool vis[300001];int dep[300001],maxdep[300001][4],maxlen[300001],ans;
void dfs0(int i){
	dep[i]=1;vis[i]=1;
	for(auto j:to[i])if(!vis[j]){
		dfs0(j);dep[i]=max(dep[i],dep[j]+1);
		if(dep[j]>=maxdep[i][0]){
			maxdep[i][2]=maxdep[i][1];maxdep[i][1]=maxdep[i][0];maxdep[i][0]=dep[j];
		}
		else if(dep[j]>=maxdep[i][1]){
			maxdep[i][2]=maxdep[i][1];maxdep[i][1]=dep[j];
		}
		else if(dep[j]>=maxdep[i][2])maxdep[i][2]=dep[j];
		maxlen[i]=max(maxlen[i],maxlen[j]);
	}
	vis[i]=0;maxlen[i]=max(maxlen[i],maxdep[i][0]+maxdep[i][1]);
}
void dfs1(int i){
	vis[i]=1;
	for(auto j:to[i])if(!vis[j]){
		maxdep[j][3]=max(maxdep[i][0]==dep[j]?maxdep[i][1]:maxdep[i][0],maxdep[i][3])+1;
		dfs1(j);
		ans=max(ans,
			(maxdep[i][0]==dep[j]?maxdep[i][1]+max(maxdep[i][2],maxdep[i][3]):
			maxdep[i][1]==dep[j]?maxdep[i][0]+max(maxdep[i][2],maxdep[i][3]):
			maxdep[i][0]+max(maxdep[i][1],maxdep[i][3]))
			+maxlen[j]+1);
	}
}
int main(){
	int n;scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v;scanf("%d%d",&u,&v);to[u].push_back(v);to[v].push_back(u);
	}
	dfs0(1);dfs1(1);
	printf("%d",ans);
    return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...