十五月明

用户名：dotcpp0605328

访问量：5427

签　名：

等　　级
排　　名	319
经　　验	5465
参赛次数	0
文章发表	87
年　　龄	18
在职情况	学生
学　　校	曲阜师范大学
专　　业	人工智能

　　自我简介：

Easy

TA的其他文章

信息学奥赛一本通T1346-亲戚(relation) 并查集此题有毒
浏览：7

信息学奥赛一本通T1347-格子游戏并查集
浏览：5

团伙(group) 并查集
浏览：57

你可能喜欢

C语言程序设计教程（第三版）课后习题5.5 （Java代码）

A+B for Input-Output Practice (III) （C++代码）

C语言训练-最大数问题（C语言代码）.........关于-1

AcWing 1073. 树的中心树形dp

　　作者: 十五月明　　　　发表时间：2024-11-04 20:36:21 浏览：15　|　评论：0　

#include<bits/stdc++.h>
    using namespace std;
    const int N=10010,M=2*N,INF = 0x3f3f3f3f;
    int h[N],ne[M],e[M],w[M],max1[N],max2[N],idx,up[N],dpb[N];//downpassby
    
    void add(int a,int b,int c){
    	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
    }
    int dfs_down(int u,int dad){//向下走的模板，但是因为还有向上的dfs则需要记录是从哪个点向下走的，避免等一下向上走的时候重复
    	max1[u]=max2[u]=-0x3f3f3f3f;
    	for(int i=h[u];i != -1;i=ne[i]){
    		int j=e[i];
    		if(j==dad) continue;
    		int dist=dfs_down(j,u)+w[i];
    		if(dist>=max1[u]){
    			max2[u]=max1[u];
    			max1[u]=dist;
    			dpb[u]=j;
    		}
    		else if(dist>max2[u]) max2[u]=dist;
    	}
    	if(max1[u]==-0x3f3f3f3f) max1[u]=max2[u]=0;//如果值没有更新的话表示该节点为叶子节点(末节点)
    	return max1[u];
    }
    void dfs_up(int u,int dad){
    	for(int i=h[u];i != -1;i=ne[i]){
    		int j=e[i];
    		if(j==dad) continue;
    		if(dpb[u]==j) up[j]=max(max2[u],up[u])+w[i];//如果与向下的max1路径相同，则选择max2次大路
    		else up[j]=max(max1[u],up[u])+w[i];
    		dfs_up(j,u);
    	}
    }
    int main(){
    	int n;cin>>n;
    	memset(h,-1,sizeof h);
    	for(int i=1;i<n;i++){
    		int a,b,c; cin>>a>>b>>c;
    		add(a,b,c),add(b,a,c);
    	}
    	dfs_down(1,-1);//先执行向下的
    	dfs_up(1,-1);
    	int res= INF;
    	for(int i=1;i<=n;i++){
    		res=min(res,max(up[i],max1[i]));//最远距离最小，分两部分，向下走的最远距离和向上走的最远距离
    	}
    	cout<<res;
    	return 0;
    }

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

十五月明

TA的其他文章

你可能喜欢

C语言训练-最大数问题（C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （Java代码）

交换Easy （Java代码）

A+B for Input-Output Practice (III) （C++代码）

C语言训练-最大数问题（C语言代码）.........关于-1

AcWing 1073. 树的中心树形dp

评论区

精彩推荐

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

【排队买票】（C语言代码）

三角形（C++代码）递推

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

DNA （C语言代码）

循环入门练习6 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

sizeof的大作用（C语言代码）

十五月明

TA的其他文章

你可能喜欢

C语言训练-最大数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （Java代码）

交换Easy （Java代码）

A+B for Input-Output Practice (III) （C++代码）

C语言训练-最大数问题 （C语言代码）.........关于-1

AcWing 1073. 树的中心 树形dp

评论区

精彩推荐

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

【排队买票】 （C语言代码）

三角形 （C++代码）递推

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

DNA （C语言代码）

循环入门练习6 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

sizeof的大作用 （C语言代码）

C语言训练-最大数问题（C语言代码）

C语言训练-最大数问题（C语言代码）.........关于-1

AcWing 1073. 树的中心树形dp

　　评论区

【排队买票】（C语言代码）

三角形（C++代码）递推

sizeof的大作用（C语言代码）