题解 P2491 【[SDOI2011]消防】

显然可以发现这条路径必然在树的直径上 至于证明，只需要假设路径Q不在直径上，那么假设距离最远的点不在直径上，易证不可能，因此距离这条路径Q最远的点一定在直径上。 之后再假设一个A点是不在直径上的一个点，我们假设直径上有一条路径P，如果A到P的距离大于了直径的端点到Q的距离，显然是矛盾的，因此任意的A点到P的距离一定小于直径端点到Q的距离，因此得证。 所以我们先dfs求出树的直径，从直径的端点开始单调的移动两个指针，保证两个指针的距离是不大于s得最大值，（这样的路径在左指针固定的情况下肯定是最优的），两个指针之间的路径就是候选路径。 对树的直径维护一个前缀和。 ls表示左指针到直径端点的距离。 rs表示右指针到直径端点的距离。 h表示左右指针之间的点可以扩展到的最远距离。 这三个量都是可以进行单调性维护的。 对于每一条候选路径，其他所有城市到这条路径的距离的最大值=max(ls,rs,h); 不断移动左右指针就可以得出最终答案。 ```cpp #include<iostream> #include<vector> #include<cstring> using namespace std; vector<int> a[300001],b[300001]; int last[300001],op,u,vv,dis[300001]; int l,r,s1,s2[300001][1],s3,l1,r1; bool v[300001],vs[300001]; void dfs1(int o,int p,int q) { if(p>op){op=p;u=o;} for(int i=0;i<a[o].size();i++) if((!v[a[o][i]])&&(a[o][i]!=q)) { v[a[o][i]]=true; dfs1(a[o][i],p+b[o][i],o); } } void dfs2(int o,int p,int q) { last[o]=q; dis[o]=p; if(p>op){op=p;vv=o;} for(int i=0;i<a[o].size();i++) if((!v[a[o][i]])&&(a[o][i]!=q)) { v[a[o][i]]=true; dfs2(a[o][i],p+b[o][i],o); } } int main() { int n,s; cin>>n>>s; for(int i=1;i<n;i++) { int x,y,z; cin>>x>>y>>z; a[x].push_back(y); b[x].push_back(z); a[y].push_back(x); b[y].push_back(z); } memset(v,0,sizeof(v)); op=0; dfs1(1,0,0); op=0; memset(v,0,sizeof(v)); memset(last,0,sizeof(last)); dfs2(u,0,0); memset(v,0,sizeof(v)); for(int i=vv;last[i]!=0;i=last[i]) v[i]=true; l=vv;l1=r1=s1=0; int ans=1000000000; memset(vs,0,sizeof(vs)); for(int i=vv;last[i]!=0;i=last[i]) { while((dis[l]-dis[i]>s)&&(l!=i)) { vs[l]=true; s1+=dis[l]-dis[last[l]]; if(vs[s2[l1][1]]==true) l1++; l=last[l]; } op=0; dfs1(i,0,0); int yu=op; while((s2[r1][0]<yu)&&(r1>=l1)) r1--; r1++; s2[r1][0]=yu; s2[r1][1]=i; ans=min(ans,max(max(s2[l1][0],s1),dis[i])); } cout<<ans<<endl; return 0; } ```