最近搞一搞树型结构……毕竟自己树的知识学的太垃圾了。
首先这道题非常明显要求树的直径。树的直径有好多好多种求法，这里我选择了一位dalao的非常简洁的dfs的方法。先看一下代码。
void dfs(int x) { for(int i = head[x];i;i = e[i].next) { if(fa[x] == e[i].to || vis[e[i].to]) continue; fa[e[i].to] = x; dis[e[i].to] = dis[x] + e[i].v; dfs(e[i].to); } }
代码非常的简短。具体的思想也很好理解，就是依次向下dfs，然后使用fa来记录在直径上都有哪些点。不过这个使用的时候要注意，就是每次要被开始进行搜索的那个点的dis赋成0.
思想就是两遍dfs。第一遍先随便搜，搜到一个与之相距最远的点（这个点必然是树的直径之一），之后再从这个点进行dfs，之后搜到一个与之距离最远的点（直径的另一个端点），这就是树的直径了。
然后怎么做？
我们可以使用直径的性质。首先来看偏心距的定义，对于一条路径F，树中与之距离最远的点到路径F的距离为F的偏心距。首先每条直径肯定会有一个最小的偏心距，所以只要求一条直径就可以啦。
之后，我们要求偏心距最小……首先我们通过直径的性质可以知道一件事，就是对于直径上一条路径的偏心距，一定是当前这条路径的两端点到直径两端点距离的最大值。这个必然成立，否则肯定存在一条比你当前求的直径还长的一条链。
那么我们就可以使用贪心的思想，每次在直径上取一条长度不大于限制条件的路径，之后每次更新最小偏心距即可。注意有一种特殊情况就是直径的总长要小于限制的长度，这时就从每个在直径上的点开始dfs，最后输出最大的值就好啦。
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<set> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 5000005; const int INF = 1000000009; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct node { int next,to,v; }e[M<<1]; int n,s,x,y,ecnt,head[M],dis[M],fa[M],r1,r2,ans = INF,k,z; bool vis[M]; void add(int x,int y,int z) { e[++ecnt].to = y; e[ecnt].v = z; e[ecnt].next = head[x]; head[x] = ecnt; } void dfs(int x) { for(int i = head[x];i;i = e[i].next) { if(fa[x] == e[i].to || vis[e[i].to]) continue; fa[e[i].to] = x; dis[e[i].to] = dis[x] + e[i].v; dfs(e[i].to); } } void solve() { ans = -1; for(int i = r2;i;i = fa[i]) vis[i] = 1; for(int i = r2;i;i = fa[i]) dis[i] = 0,dfs(i); rep(i,1,n) ans = max(ans,dis[i]); printf("%d ",ans); } int main() { n = read(),s = read(); rep(i,1,n-1) x = read(),y = read(),z = read(),add(x,y,z),add(y,x,z); dfs(1); memset(fa,0,sizeof(fa)); rep(i,1,n) if(dis[i] > dis[r1]) r1 = i;//找到第一个端点 dis[r1] = 0,dfs(r1); rep(i,1,n) if(dis[i] > dis[r2]) r2 = i;//找到第二个端点 k = r2; if(dis[k] <= s) { solve();//直径长度小于限制长度的解决 return 0; } for(int i = r2;i;i = fa[i]) { while(fa[k] && dis[i] - dis[fa[k]] <= s) k = fa[k];//贪心取链 ans = min(ans,max(dis[k],dis[r2] - dis[i]));//更新最小偏心距 } printf("%d ",ans); return 0; }