bzoj1509

树的直径

我先开始以为是个图，想想并不知道什么求图的直径的方法，结果是棵树

那么直觉告诉我们是在直径上面，实际上就是直径+min(i->u,i->v)，扫一遍就行了

#include<bits/stdc++.h>

using namespace std;

const int N = ;

namespace IO

{

    const int Maxlen = N;

    char buf[Maxlen], *C = buf;

    int Len;

    inline void read_in()

    {

        Len = fread(C, , Maxlen, stdin);

        buf[Len] = '\0';

    }

    inline void fread(int &x)

    {

        x = ;

        int f = ;

        while (*C < '' || '' < *C) { if(*C == '-') f = -; ++C; }

        while ('' <= *C && *C <= '') x = (x << ) + (x << ) + *C - '', ++C;

        x *= f;

    }

    inline void read(int &x)

    {

        x = ;

        int f = ; char c = getchar();

        while(c < '' || c > '') { if(c == '-') f = -; c = getchar(); }

        while(c >= '' && c <= '') { x = (x << ) + (x << ) + c - ''; c = getchar(); }

        x *= f;

    }

    inline void read(long long &x)

    {

        x = ;

        long long f = ; char c = getchar();

        while(c < '' || c > '') { if(c == '-') f = -; c = getchar(); }

        while(c >= '' && c <= '') { x = (x << 1ll) + (x << 3ll) + c - ''; c = getchar(); }

        x *= f;

    }

} using namespace IO;

struct edge {

    int to;

    long long w;

    edge(int to = , long long w = ) : to(to), w(w) {}

};

int n, m, root;

long long ans;

vector<edge> G[N];

long long f[N], g[N], d[N];

void dfs(int u, int last, long long d[])

{

    if(d[u] > d[root]) root = u;

    for(int i = ; i < G[u].size(); ++i)

    {

        edge e = G[u][i];

        if(e.to == last) continue;

        d[e.to] = d[u] + e.w;

        dfs(e.to, u, d);

    }

}

int main()

{

    read(n);

    read(m);

    for(int i = ; i <= m; ++i)

    {

        int u, v;

        long long w;

        read(u);

        read(v);

        read(w);

        G[u].push_back(edge(v, w));

        G[v].push_back(edge(u, w));

    }

    dfs(, , f);

    int u = root;

    root = ;

    dfs(u, , g);

    long long dis = g[root];

    u = root;

    root = ;

    dfs(u, , d);

    for(int i = ; i <= n; ++i) ans = max(ans, dis + min(d[i], g[i]));

    printf("%lld\n", ans);

    return ;

}