【题意】n个点的树，m条链，求将一条边的权值置为0使得最大链长最小。

【算法】二分+树上差分

【题解】

最大值最小化问题，先考虑二分最大链长。

对所有链长>mid的链整体+1（树上差分）。

然后扫一遍，对[在所有不满足链上]的边取最大值并check。

 

具体做法：对于二分的最大链长，将所有链长>mid的链取最大值（链的数量记为num），然后用树上差分整体+1。

树上差分：a+1,b+1,lca(a,b)-2。dfs的时候判断子节点的连边（若子节点权=num则连边参与比较），然后再把子节点权加进来。

最后看最大边权是否>=最大链长和最长链的差值。

复杂度O(n log n)。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=300010;int read(){    char c;int s=0,t=1;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}int n,m,first[maxn],f[maxn][30],deep[maxn],dis[maxn],sum,num,mx,a[maxn],b[maxn],c[maxn],d[maxn],tot=0,s[maxn];struct edge{
    int v,w,from;}e[maxn*2];void insert(int u,int v,int w){tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;}void dfs(int x,int fa){    for(int j=1;(1<
          
           <=deep[x];j++)f[x][j]=f[f[x][j-1]][j-1];    for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){        deep[e[i].v]=deep[x]+1;        dis[e[i].v]=dis[x]+e[i].w;        f[e[i].v][0]=x;        dfs(e[i].v,x);    }}int lca(int x,int y){    if(deep[x]
           
            =0;i--)if((1<
            
             <=deep[x]&&f[x][i]!=f[y][i]){ x=f[x][i];y=f[y][i]; } return f[x][0];}void DFS(int x,int fa){ for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){ DFS(e[i].v,x);//zhi xing shun xu if(s[e[i].v]>=num)mx=max(mx,e[i].w); s[x]+=s[e[i].v]; }}bool check(int l){ int cha=0;num=0; memset(s,0,sizeof(s)); for(int i=1;i<=m;i++)if(d[i]>l){ cha=max(cha,d[i]-l); s[c[i]]-=2;s[a[i]]++;s[b[i]]++; num++; } mx=0;sum=0; DFS(1,0); if(mx>=cha)return 1;else return 0;} int main(){ n=read();m=read(); for(int i=1;i
             
              >1; if(check(mid))r=mid; else l=mid+1; } printf("%d",l); return 0;}
             
            
           
          
         
        
       
      

dfs的时候注意操作顺序。