洛谷4408 [NOI2003]逃学的小孩

题意

给出一个 $n(\le 2\times 10^5)$ 点的树。从 $C$ 出发，先到 $A$ 和 $B$ 中较近的点，然后到另一个点。求可能的路径最大值。

题解

$A\rightarrow B$ 这段路径是肯定要走的，然后还有一段 $\max_c (\min (AC,BC))$ 。显然 $AB$ 是直径，然后从 $A,B$ 出发分别 $\text{dfs}$ 一次求出距离即可。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=200005;
struct Edge {
    int next,to,w;
} edge[N<<1];
int cnt,head[N],n,m,a,b,c,mxi,fa[N];
ll mx,ans,d[N];

inline void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x,int f,ll dis)
{
    fa[x]=f;
    if (dis>mx) mx=dis,mxi=x;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        dfs(y,x,dis+edge[i].w);
    }
}

void dfs2(int x,int f,ll dis)
{
    d[x]=min(d[x],dis);
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        dfs2(y,x,dis+edge[i].w);
    }
}

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read(); c=read();
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,0,0);
    int rt=mxi; mx=0;
    dfs(rt,0,0);
    ans+=mx; //A->B
    memset(d,0x3f,sizeof(d));
    dfs2(rt,0,0);
    dfs2(mxi,0,0);
    ll mx=0;
    for (int i=1;i<=n;i++) mx=max(mx,d[i]);
    return !printf("%lld",ans+=mx);
}