[数据结构与算法]P1099 [NOIP2007 提高组] 树网的核——树的直径

Link
方法蛮多的一道题，主要是在书上看的，这里不想写了，贴个代码保存一下。

代码

//
//
#include <bits/stdc++.h>
using namespace std;
//#define mp make_pair
#define pii pair<int,int>
#define pb push_back
#define ll long long
#define LL long long
#define ld long double
#define endl '\n'
#define RE0 return 0
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)

//#define int long long
#define db double
const int maxn = 1e3 + 10;
const int maxm = 1e3 + 10;
const int P = (1<<31)-1;    //998244353
const int INF = 0x3f3f3f3f;
const double eps=1e-7;
struct Edge {
    int to, dis, next;
}edge[maxm];
int n, m;
int head[maxn], dis[maxn], cnt;
bool vis[maxn];
void add_edge(int u, int v, int w) {
    cnt++;
    edge[cnt].to = v;
    edge[cnt].dis = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}
int k;
int s;
int fa[maxn];
int now;
void dfs(int cur) {    //now表示目前的最大深度
    vis[cur] = 1;
    for(int i = head[cur]; i; i = edge[i].next) {
        int v = edge[i].to;
        if(vis[v]) continue;
        dis[v] = dis[cur] + edge[i].dis;
        if(dis[v] > dis[now]) {
            now = v;
        }
        fa[v] = cur;
        dfs(v);
    }
    vis[cur] = 0;
}
vector<int> q;
int diam(int s = 1) {
    now = s;
    dfs(s);
    memset(dis, 0, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(fa, 0, sizeof(fa));
    dfs(now);
    return dis[now];
}
int maxx = 0;
void dfs2(int cur) {
    vis[cur] = 1;
    for(int i = head[cur]; i; i = edge[i].next) {
        int v = edge[i].to;
        int w = edge[i].dis;
        if(vis[v]) continue;
        dis[v] = dis[cur] + w;
        maxx = max(maxx, dis[v]);
        dfs2(v);
    }
}
void solve() {
    cin >> n >> s;
    for(int i =  1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    diam();
    memset(vis, 0, sizeof(vis));
    while(now) {
        vis[now] = 1;
        q.push_back(now);
        now = fa[now];
    }
    for(int i : q) {
        int tmp = dis[i];
        dis[i] = 0;
        dfs2(i);
        dis[i] = tmp;
    }
    int r = 0;
    int ans = INF;
    for(int i = 0; i < q.size(); i++) {
        while(abs(dis[q[i]]-dis[q[r+1]]) <= s) {
            r++;
            if(r + 1 == q.size()) break;
        }
        int now;
        now = max(maxx, abs(dis[q[i]]-dis[q[0]]));
        now = max(now, abs(dis[q[q.size()-1]]-dis[q[r]]));
        ans = min(ans, now);
        if(r == q.size()-1) break;
    }
    cout << ans << endl;
    
}