当前位置：首页 > article >正文

P4408 [NOI2003] 逃学的小孩

article 2024/11/28 19:03:13

Chris 家的电话铃响起了，里面传出了 Chris 的老师焦急的声音：“喂，是 Chris 的家长吗？你们的孩子又没来上课，不想参加考试了吗？”一听说要考试，Chris 的父母就心急如焚，他们决定在尽量短的时间内找到 Chris。他们告诉 Chris 的老师：“根据以往的经验，Chris 现在必然躲在朋友 Shermie 或 Yashiro 家里偷玩《拳皇》游戏。现在，我们就从家出发去找 Chris，一旦找到，我们立刻给您打电话。”说完砰的一声把电话挂了。

Chris 居住的城市由 �N 个居住点和若干条连接居住点的双向街道组成，经过街道 �x 需花费 ��Tx 分钟。可以保证，任两个居住点间有且仅有一条通路。Chris 家在点 �C，Shermie 和 Yashiro 分别住在点 �A 和点 �B。Chris 的老师和 Chris 的父母都有城市地图，但 Chris 的父母知道点 �A、�B、�C 的具体位置而 Chris 的老师不知。

为了尽快找到 Chris，Chris 的父母会遵守以下两条规则：

如果 �A 距离 �C 比 �B 距离 �C 近，那么 Chris 的父母先去 Shermie 家寻找 Chris，如果找不到，Chris 的父母再去 Yashiro 家；反之亦然。
Chris 的父母总沿着两点间唯一的通路行走。

显然，Chris 的老师知道 Chris 的父母在寻找 Chris 的过程中会遵守以上两条规则，但由于他并不知道 �A、�B、�C 的具体位置，所以现在他希望你告诉他，最坏情况下 Chris的父母要耗费多长时间才能找到 Chris？

输入格式

输入文件第一行是两个整数 �N 和 �M，分别表示居住点总数和街道总数。

以下 �M 行，每行给出一条街道的信息。第 �+1i+1 行包含整数 ��Ui、��Vi、��Ti，表示街道 �i 连接居住点 ��Ui 和 ��Vi，并且经过街道 �i 需花费 ��Ti 分钟。街道信息不会重复给出。

输出格式

输出文件仅包含整数 �T，即最坏情况下 Chris 的父母需要花费 �T 分钟才能找到 Chris。

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

对于 100%100% 的数据，3≤�≤2×1053≤N≤2×105，1≤��,��≤�1≤Ui,Vi≤N，1≤��≤1091≤Ti≤109。

题意

Description

有n个点，由m条边连接，第i条边的边权是wi。这些点和边构成了一棵树.

对于树来说，我们都知道其最远的两个点之间的距离称为直径

现在树上每个节点上都有一个人，他必须先跑到离他较近的直径的某个端点，再跑到直径的另一个端点

现在问你，在这N个人中，跑得最远的那个人，他跑了多远的路。

Format

Input

第一行给出n,m

接下来m行描述边,边权<=1000000000

N<=2e5

Output

如题

Samples

输入数据 1

Copy

输出数据 1

思路

显然最优解需要从C先跑到A再跑到B.或者从C先跑到B再跑到A。

假设我们已经确定A,B点，那么AB是必走的，CA,CB会选取其中小的一段走，所以我们的C点要满足min(CA,CB)最大，这样就可以使答案最大。
如何确定A,B点？既然AB是必走的，那当然越长越好，所以就是树的直径了。由于这里只需要求树直径的端点和总长而不用求具体路线，我就选择了DFS来求。
如果不会求树的直径的方法，可以看看求树的直径(史上最详细,匠心之作)_树的直径存在负边权-CSDN博客
记得开long long

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,n,k,deep[1000001],zj,zjj,lzj,deep_2[1000001];
struct ff
{
  int id,len;
};
vector<ff> vec[1000001];
void dfs(int x,int fa,int d,int p)
{
  if(p == 1) deep[x] = d;
  else deep_2[x] = d;
  for(int i = 0;i < vec[x].size();i++)
    if(vec[x][i].id != fa)
      dfs(vec[x][i].id,x,d + vec[x][i].len,p);
}
void qzj()
{
  dfs(1,0,0,1);
  int t = 0;
  for(int i = 1;i <= n;i++)
    if(t < deep[i])
    {
      t = deep[i];
      zj = i;
    }
  dfs(zj,0,0,1);
  t = 0;
  for(int i = 1;i <= n;i++)
    if(t < deep[i])
    {
      t = deep[i];
      zjj = i;
    }
  lzj = t;
}
signed main()
{
  cin>>n>>k;
  for(int i = 1;i < n;i++)
  {
    int c;
    cin>>a>>b>>c;
    vec[a].push_back({b,c});
    vec[b].push_back({a,c});
  }
  qzj();
  dfs(zj,0,0,1);
  dfs(zjj,0,0,2);
  int tt = 0;
  for(int i = 1;i <= n;i++) tt = max(tt,min(deep[i],deep_2[i]));
  cout<<tt + lzj;
  return 0;
}