看到最大值最小,第一个想到二分答案。

那么我们需要改成虫洞的边必然被所有大于当前答案的路径覆盖,我们只要在这些边中找到一条时间最大的,看看删去以后能否使之前耗时最长的路径耗时小于等于答案就好了。

那么如何找到满足条件的边呢?

我们可以将每一条超出答案的路径上所有的边打上一个标记,(标记数量=超出答案的边的数量)的边即是满足条件的边。

但是暴力打标记就T了。

所以我们要树上差分。

然后就可以了。

洛谷卡常,卡了好几天过不去,直到换上了他的码风才过去(神仙的码风快我两倍以上orz)。

大致就是从

倍增LCA+vector存图+自己码风+无fread+O2=\(\color{blue}\texttt{TLE}\)

变成

树剖LCA+vector存图+自己码风+fread+无O2(开了就MLE不知为什么)=\(\color{blue}\texttt{TLE}\)

然后

树剖LCA+链式前向星存图+自己码风+fread+无O2(开了就全TLE不知为什么)=\(\color{blue}\texttt{TLE}\)

最后

树剖LCA+链式前向星存图+神仙码风+fread+无O2=\(\color{green}\texttt{AC}\)

code:

神仙码风可读性差,还是放了自己的码风,AC代码在后面

(自己的码风可读性也不高嘛...)

#include
    
     using namespace std;#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)char buf[1<<21],*p1=buf,*p2=buf;struct edge{    int t,w,nxt;}e[600010];struct Path{    int a,b,lca,len;}p[300010];int n,m,u,v,t,beg[300010],cnt,lg,vis[300010],f[300010],tp[300010],sz[300010],sum[300010],dep[300010],l,r,mid,siz,s[300010],mxe,mxl;void add(int x,int y,int val){    e[++cnt].t=y;    e[cnt].w=val;    e[cnt].nxt=beg[x];    beg[x]=cnt;}int Dfs(int x){    vis[x]=1;    sz[x]=1;    for(int i=beg[x];i;i=e[i].nxt)if(!vis[e[i].t])dep[e[i].t]=dep[x]+1,sum[e[i].t]=sum[x]+e[i].w,sz[x]+=Dfs(e[i].t);else f[x]=e[i].t;    return sz[x];}int Dfs2(int x){    int mxs=0,d=0;    for(int i=beg[x];i;i=e[i].nxt)if(e[i].t!=f[x]&&sz[e[i].t]>mxs)mxs=sz[e[i].t],d=e[i].t;    if(d)tp[d]=tp[x],Dfs2(d);    for(int i=beg[x];i;i=e[i].nxt)if(e[i].t!=f[x]&&e[i].t!=d)tp[e[i].t]=e[i].t,Dfs2(e[i].t);}int LCA(int x,int y){    while(tp[x]!=tp[y]){        if(dep[tp[x]]
     
      x)s[p[i].a]++,s[p[i].b]++,s[p[i].lca]-=2,mxl=max(mxl,p[i].len),siz++;    dfs(1);    return mxl-mxe<=x;}void scan(int &x){    x=0;    char c=getchar();    while('0'>c||c>'9')c=getchar();    while('0'<=c&&c<='9')x=x*10+c-'0',c=getchar();}int main(){    scan(n),scan(m);    for(int i=1;i
     
    

神仙码风:

code:

#include
    
     using namespace std;#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)#define add(x,y,val) (e[++cnt].t=y,e[cnt].w=val,e[cnt].nxt=beg[x],beg[x]=cnt)#define swap(x,y) (x^=y^=x^=y)char buf[1<<21],*p1=buf,*p2=buf;struct edge{    int t,w,nxt;}e[600010];struct Path{    int a,b,lca,len;}p[300010];int n,m,u,v,t,beg[300010],cnt,lg,vis[300010],f[300010],tp[300010],sz[300010],sum[300010],dep[300010],l,r,mid,siz,s[300010],mxe,mxl;int Dfs(int x){    vis[x]=1,sz[x]=1;    for(register int i=beg[x];i;i=e[i].nxt) vis[e[i].t]?(f[x]=e[i].t):(dep[e[i].t]=dep[x]+1,sum[e[i].t]=sum[x]+e[i].w,sz[x]+=Dfs(e[i].t));    return sz[x];}void Dfs2(int x){    register int i,mxs=0,d=0;    for(i=beg[x];i;i=e[i].nxt) e[i].t^f[x]&&sz[e[i].t]>mxs&&(mxs=sz[e[i].t],d=e[i].t);    for(d&&(tp[d]=tp[x],Dfs2(d),0),i=beg[x];i;i=e[i].nxt) e[i].t^f[x]&&e[i].t^d&&(tp[e[i].t]=e[i].t,Dfs2(e[i].t),0);}inline int LCA(int x,int y){    while(tp[x]^tp[y]) dep[tp[x]]
     
      x&&(++s[p[i].a],++s[p[i].b],s[p[i].lca]-=2,mxl=max(mxl,p[i].len),++siz);    return dfs(1),mxl-mxe<=x;}inline void scan(int &x){    x=0;    register char c=getchar();    while(!isdigit(c))c=getchar();    while(isdigit(c))x=(x<<3)+(x<<1)+(c&15),c=getchar();}int main(){    register int i;    for(scan(n),scan(m),i=1;i
      
       >1)?r=mid:l=mid+1;    return printf("%d",l),0;}