树网的核 NOIP 2007 luogu P1099

AC传送门

看到这个N值，直接就想到暴力。

直接O(N³)的暴力即可。

PS：  先找到树的直径，并记录直径上的点（直接搜索时记录所有的点的father即可）。然后枚举符合要求的直径上的段落，直接DFS暴搜。

虽然思路简单，但细节和代码实现还是要有一点操作（特别是程序设计上）

代码：

#include <bits/stdc++.h>
using namespace std;
#define N 100010
#define isdigit(c) ((c)>='0'&&(c)<='9')

int read(){
    int x = 0, s = 1;
    char c = getchar();
    while(!isdigit(c)){
        if(c == '-')s = -1;
        c = getchar();
    }
    while(isdigit(c)){
        x = (x << 1) + (x << 3) + (c ^ '0');
        c = getchar();
    }
    return x * s;
}

struct node{
    int v, w, next;
} t[N << 1];
int f[N];
int n, s;
int fa[N], next_dis[N];
int dis[N], dist[N];
bool vis[N];
int ans2 = -66666, ans = (int)8e9;  /*don't forget the original value*/

int bian = 0;
inline void add(int u, int v, int w){
    t[++bian] = (node){v, w, f[u]}, f[u] = bian; /*both dire need to be added*/
    t[++bian] = (node){u, w, f[v]}, f[v] = bian;
    return ;
}

int max_dis = -233333, cur, s1, s2;
void dfs1(int now, int father, int dis){
    if(dis > max_dis){
        cur = now;
        max_dis = dis;
    }
    for(int i = f[now]; i; i = t[i].next){
        int v = t[i].v, w = t[i].w;
        if(v != father && !vis[v]){
            fa[v] = now;
            dist[v] = dist[now] + w;  /*dist is the distance of the two points*/
            dfs1(v, now, dis + w);    
        }
    }
    return ;
}

inline void search(int x, int& s){ /*find the farthest point of x, and record it as s*/
    max_dis = -23333;
    dist[x] = 0;
    dfs1(x, x, 0);
    s = cur;
    return ;
}

void dfs2(int now, int father){
    for(int i = f[now]; i; i = t[i].next){
        int v = t[i].v, w = t[i].w;
        if(v != father && !vis[v]){
            vis[v] = 1;
            dis[v] = dis[now] + w;
            ans2 = max(ans2, dis[v]); /*record the max distance */
            dfs2(v, now);
        }
    }
    return ;
}

int main(){
//    freopen("hh.txt", "r", stdin);s
    n = read(), s = read();
    for(int i = 1;i < n; i++){
        int x = read(), y = read(), w = read();
        add(x, y, w);
    }
    search(1, s1);
    memset(fa, 0, sizeof(fa)); /*remember to clean the fa, as this time it is wrong*/
    search(s1, s2);
    for(int i = s2; i; i = fa[i]){
        for(int j = i; j; j = fa[j]){
            if(dist[i] - dist[j] <= s){
                memset(vis, 0, sizeof(vis));
                ans2 = -666;
                for(int k = i; k != j; k = fa[k])
                    vis[k] = 1;
                vis[j] = 1;  /*don't miss j!*/
                for(int k = i;k != j; k = fa[k]){
                    dis[k] = 0;
                    dfs2(k, k);
                }
                dis[j] = 0;
                dfs2(j, j); 
                ans = min(ans, ans2);
            }
            else break;
        }
    }
    printf("%d
", ans);
    return 0;
}