1073. 树的中心

大标 2022年3月16日23:54:11
评论
20

题目链接

1073. 树的中心

给定一棵树,树中包含 \\(n\\) 个结点(编号\\(1~n\\))和 \\(n−1\\) 条无向边,每条边都有一个权值。

请你在树中找到一个点,使得该点到树中其他结点的最远距离最近。

输入格式

第一行包含整数 \\(n\\)

接下来 \\(n−1\\) 行,每行包含三个整数 \\(a_i,b_i,c_i\\),表示点 \\(a_i\\)\\(b_i\\) 之间存在一条权值为 \\(c_i\\) 的边。

输出格式

输出一个整数,表示所求点到树中其他结点的最远距离。

数据范围

\\(1≤n≤10000,\\)
\\(1≤a_i,b_i≤n,\\)
\\(1≤c_i≤10^5\\)

输入样例:

5 
2 1 1 
3 2 1 
4 3 1 
5 1 1

输出样例:

2

解题思路

换根dp,dfs

对于一个节点来说其最长距离要么向上要么向下,对于向下好分析,向上不能经过当前节点,可以统计向下的最长距离和次长距离,以及对于一个节点来说向下最短时其指向的子节点,接着继续分析向上的情况,如果其父节点的最短指向的节点正好是自己,则用次短路径更新父节点否则用最短路径(部分代码段):

if(p[x]!=y)u[y]=max(u[x],d1[x])+w;
else
	u[y]=max(u[x],d2[x])+w;
  • 时间复杂度:\\(O(n)\\)

代码

// Problem: 树的中心
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1075/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < \'0\' || s > \'9\') { if (s == \'-\') f = -1; s = getchar(); }
    while (s <= \'9\' && s >= \'0\') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=10005,inf=0x3f3f3f3f;
int n,d1[N],d2[N],u[N],p[N];
vector<PII> adj[N];
bool is_leaf[N];
int dfs_d(int x,int fa)
{
	d1[x]=d2[x]=-inf;
	for(auto t:adj[x])
	{
		int y=t.fi,w=t.se;
		if(y==fa)continue;
		int d=dfs_d(y,x)+w;
		if(d>=d1[x])
		{
			d2[x]=d1[x];
			d1[x]=d;
			p[x]=y;
		}
		else if(d>d2[x])d2[x]=d;
	}
	if(d1[x]==-inf)
	{
		is_leaf[x]=true;
		d1[x]=d2[x]=0;
	}
	return d1[x];
}
void dfs_u(int x,int fa)
{
	for(auto t:adj[x])
	{
		int y=t.fi,w=t.se;
		if(y==fa)continue;
		if(p[x]!=y)u[y]=max(u[x],d1[x])+w;
		else
			u[y]=max(u[x],d2[x])+w;
		dfs_u(y,x);
	}
}
int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
    	int a,b,c;
    	cin>>a>>b>>c;
    	adj[a].pb({b,c});
    	adj[b].pb({a,c});
    }
    dfs_d(1,-1);
    dfs_u(1,-1);
    int res=inf;
    for(int i=1;i<=n;i++)
    	if(is_leaf[i])res=min(res,u[i]);
    	else
    		res=min(res,max(d1[i],u[i]));
    cout<<res;
    return 0;
}
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
大标
  • 本文由 发表于 2022年3月16日23:54:11
  • 转载请务必保留本文链接:https://www.tanhuibiao.com/script/qita/5401.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: