想一下可以发现随便枚举一条直径做就可以了。
核越长越好。于是枚举核的过程可以做到O(n)
然后就是统计答案。
对于每个核最大偏心距肯定是核上面每个点不走核内的点所能走到的最远点的最值。
而且对于核的两端点，距离最远的点肯定是本条直径的端点。
于是我们可以用树形dp，处理出每个直径上的点不走本直径，所能走到的最远点的距离，记为f[]。
然后核每+1，就把当前点f[]塞到单调队列里面。每-1，就把队头弹出。
总共是O(N)。
#include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <deque> const int N = 300 + 9; struct edge{int next,link,w;}es[N*2]; std::deque<int>q; int dis[N],d_len,len[N],pre[N],p[N],f[N],max_dis[N],ec,son[N],n,s,ans = 0x7fffffff; bool mark[N]; inline void addedge(const int x,const int y,const int z) { es[++ec].next = son[x]; son[x] = ec; es[ec].link = y; es[ec].w = z; } inline void Addedge(const int x,const int y,const int z){addedge(x,y,z);addedge(y,x,z);} int bfs(const int s) { memset(dis,0,sizeof dis); memset(pre,0,sizeof pre); static std::queue<int>q; for (q.push(s); !q.empty(); ) { const int u = q.front(); q.pop(); for (int i = son[u]; i; i = es[i].next) { const int v = es[i].link; if (v == s || dis[v]) continue; dis[v] = dis[u] + es[i].w; pre[v] = u; q.push(v); } } int res = 1; for (int i = 1; i <= n; ++i) if (dis[i] > dis[res]) res = i; return res; } void find_diameter() { int t,s; d_len = dis[t = bfs(s = bfs(1))]; while (t) { mark[t] = true; p[++p[0]] = t; len[p[0]] = dis[t] - dis[pre[t]]; t = pre[t]; } } void dp(const int u,const int fa) { for (int i = son[u]; i; i = es[i].next) { if (mark[es[i].link] || es[i].link == fa) continue; dp(es[i].link,u); f[u] = std::max(f[es[i].link] + es[i].w,f[u]); } } int calc_dis(const int u) { memset(f,0,sizeof f); dp(u,0); return f[u]; } int main() { #ifndef ONLINE_JUDGE freopen("core.in","r",stdin); freopen("core.out","w",stdout); #endif scanf("%d%d",&n,&s); for (int i = 1,x,y,z; i < n; ++i) { scanf("%d%d%d",&x,&y,&z); Addedge(x,y,z); } find_diameter(); for (int i = 1; i <= p[0]; ++i) { max_dis[i] = calc_dis(p[i]); //printf("%d\n",max_dis[i]); } for (int i = 1,head = 1,sum = 0,front_dis = 0,tail_dis = 0; i <= p[0]; ++i) { sum += len[i - 1]; tail_dis += len[i - 1]; while (sum > s) { front_dis += len[head]; sum -= len[head++]; } while (q.size() && q.front() < head) q.pop_front(); while (q.size() && max_dis[q.back()] <= max_dis[i]) q.pop_back(); q.push_back(i); if (q.size()) ans = std::min(ans,std::max(max_dis[q.front()],std::max(d_len - tail_dis,front_dis))); } printf("%d\n",ans); }
转载于:https://www.cnblogs.com/lazycal/p/noip2007-t4.html
