题意:
在树上选一条点个数小于等于k的简单路径,使路径外的点到路径的距离的最大值最小。
求出最小的最大值
题解:
- 可以反证得出 这条简单路径一定在树的直径上
- 树的直径的两个端点可以很简单的用两边dfs求出 那要如何求出这条链的信息呢 ? 可以在一个端点设置标记 如何利用回溯的性质 跑出这条链!!!
- 并且在回溯的过程中可以维护直径上的每个节点的子树的最长链
- 处理完这些信息就可以用二分很方便地解决了
#include<bits/stdc++.h> using namespace std; const int N=2e5+6; int n,m,dis[N],pos,head[N],k,L,R,maxx,flag,maxdis[N],v[N],deep,id[N]; struct Edge{int to,nex,v;}edge[N<<1]; void add(int a,int b,int c){edge[++pos]=(Edge){b,head[a],c};head[a]=pos;} void dfs(int x,int fa) { for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(v==fa)continue; dis[v]=dis[x]+edge[i].v; if(dis[v]>maxx)maxx=dis[v],flag=v; dfs(v,x); } } void dfs2(int x,int fa,int d) { maxdis[x]=0; for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to;if(v==fa)continue; dfs2(v,x,d+1); ::v[x]|=::v[v]; if(!::v[v])maxdis[x]=max(maxdis[x],maxdis[v]+edge[i].v); } if(v[x])id[d]=x,deep=max(deep,d); } bool check(int x) { int pos=1,maxx=0; for(int i=deep;i>=1;i--) { if( dis[id[deep] ]-dis[id[i]]>x ) { pos=i+1;break; } } for(int i=pos;i>=max(pos-k+1,1);i--) maxx=max(maxx,maxdis[id[i]]); return max(maxx,dis[id[max(pos-k+1,1)]]-dis[id[1]])<=x; } int main() { cin>>n>>k;int x,y,z; for(int i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z); dfs(1,0); L=flag; maxx=0; dis[L]=0; dfs(L,0); R=flag; v[R]=1; dfs2(L,0,1); int l=0,r=1e9,ans=0; while(l<=r) { int mid=l+r>>1; if(check(mid))ans=mid,r=mid-1;else l=mid+1; } cout<<ans; return 0; }View Code