算法

BFS+枚举 即可

时间复杂度 O(n)

此题我看了一下午二分算法解释然而并没有看懂 在研究为什么任意一条直径的最小偏心距是一样的时候突然发现这是一个树网!!!
然后在仔细一想 好像o(n)算法会比二分更好写

只要发现如下性质 这题就会变得很简单
1. 每一个点到另一个点的路径唯一(树网)
2. 所有直径等效
3. 研究其性质可以发现 如果直径<S 那么我们只能一段一段的取 每一段的最远距离的点 是两边的端点 我们只要依次枚举就行了
4. (贪心)多加一个点会更好 解释:多加一个点会让前一点到端点的距离减小一个边长
5. 如果直径<=S 根据4意味着我们最小偏心距只能从直径的分支上取 我们只需要标记直径上的点 然后对每个直径的点bfs(因为这是一个树网)

然后就有了我非常难看的代码

C++ 代码

#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 500010
int n,s,ans=0x3f3f3f3f;
int v[N],d[N],pre[N];
int head[N],e[N<<1],w[N<<1],nex[N<<1],tot;

void add(int x,int y,int z){
    e[++tot]=y,w[tot]=z,nex[tot]=head[x],head[x]=tot;
}

void bfs(int x){
    d[x]=0;
    queue<int>que;
    que.push(x);
    while(que.size()){
        int t=que.front();
        que.pop();
        for(int i=head[t];i;i=nex[i]){
            if(v[e[i]]) continue;
            int j=e[i];
            if(d[j]>d[t]+w[i]){
                pre[j]=t;
                d[j]=d[t]+w[i];
                que.push(j);
            }
        }
    }
}

int get(){
    int p=1;
    for(int i=1;i<=n;i++){
        if(d[i]>d[p])
            p=i;
    }
    return p;
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>s;
    for(int i=1;i<n;i++){
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    //求直径
    memset(d,0x3f,sizeof d);
    bfs(1);
    int p=get();

    memset(d,0x3f,sizeof d);
    memset(pre,0,sizeof pre);
    bfs(p);
    int q=get();

    if(d[q]>s)
        for (int i = q, j = q; i; i = pre[i]) {
            while (d[j] - d[i] > s) j = pre[j];
            ans = min(ans, max(d[q] - d[j], d[i]));
        }

    else{
        ans=0;
        for (int i = q; i; i = pre[i]) v[i] = 1;
        for (int i = q; i; i = pre[i])
            bfs(i);
        for (int i = 1; i <= n; i++)
            ans = max(ans, d[i]);
    }

    cout<<ans<<endl;
    return 0;
}