一道很好的树上差分练习题。

不加fread勉强a过bzoj和luogu的数据，加了fread才能在uoj里卡过去。

可以发现，答案则是运输计划里花费的最大值，最大值最小，便是二分答案的标志。

那么该怎么check呢...

我们得找出所有超过限制的计划，这个过程可以在LCA倍增的过程中预处理出来。

然后再找出一些被这些计划都覆盖的边，找到最大的那条边，如果最大的计划花费减去最大的那条边小于x，那么x就是可行的。

但是该怎么找到那些被计划都覆盖的边呢...

我们知道，在一棵树上，两个不在同一条链上的点的最短路一定会经过他们的\(LCA\)。

那么就可以划分为\(X\)点到\(LCA\)，和\(Y\)点到\(LCA\)。

现在就是两条链了，如果要将某一条链中的边都加上1，就很容易想到差分。（但其实这个过程直接树剖也可以拿到\(95pts\)...）

我们也知道，在一棵树上，每一个非根节点到他的父节点只有一条边，我们先称这条边为“父边”。

那么我们就设\(A_i\)为\(i\)点的父边被覆盖的次数。

然后差分数组\(C_i\)为\(A_i-\sum A_j\) \(j\)点为\(i\)点的儿子。

然后修改的时候就只需要修改\(C_x , C_y , C_{LCA}\)的值了。

然后也很容易证出来\(A_i=C_i+\sum A_j\) \(j\)点为\(i\)点的所有的儿子节点。

这个过程只需要递归计算就可以了。

然后我们就找出了那些被所有计划所覆盖的边了。

你可以树剖来求\(LCA\)，然后差分求和过程按照\(dfn\)来递推，这样子常数会非常的小 我的代码是快了10倍。。。玄学的卡常底层优化

#include 
    
     const int max_n=3e5+5;int N,M,cnt,l,r,mid,Ans;int X[max_n],Y[max_n],lca[max_n],len[max_n],dis[max_n],lg2[max_n],depth[max_n],father[20][max_n],dist[max_n],first_edge[max_n],C[max_n];struct Edge{    int to,w,next_edge;}edge[max_n<<1];inline int read(){    register int x=0;    register char ch=getchar();    while(!isdigit(ch))        ch=getchar();    while(isdigit(ch))    {        x=(x<<1)+(x<<3)+ch-'0';        ch=getchar();    }    return x;}inline void add_edge(int x,int y,int z){    edge[++cnt].to=y;    edge[cnt].w=z;    edge[cnt].next_edge=first_edge[x];    first_edge[x]=cnt;    return;}inline void LCA_init(int cur,int fa){    depth[cur]=depth[fa]+1;    father[0][cur]=fa;    for(register int i=1;i<=lg2[depth[cur]];++i)        father[i][cur]=father[i-1][father[i-1][cur]];    for(register int k=first_edge[cur];k;k=edge[k].next_edge)    {        if(!depth[edge[k].to])        {            dis[edge[k].to]=dis[cur]+edge[k].w;            dist[edge[k].to]=edge[k].w;            LCA_init(edge[k].to,cur);        }    }    return;}inline int LCA(int x,int y){    if(depth[x]
     
      depth[y])        x=father[lg2[depth[x]-depth[y]]][x];    if(x==y) return x;    for(register int i=lg2[depth[x]];i>=0;--i)        if(father[i][x]!=father[i][y]) x=father[i][x],y=father[i][y];    return father[0][x];}inline void dfs(int x){    for(register int k=first_edge[x];k;k=edge[k].next_edge)    {        if(edge[k].to!=father[0][x])        {            dfs(edge[k].to);            C[x]+=C[edge[k].to];        }    }    return;}inline int check(int x){    memset(C,0,sizeof(C));    int tot=0,maxx=0,maxy=0;    for(register int i=1;i<=M;++i)    {        if(len[i]>x)        {            ++tot;            maxx=std::max(maxx,len[i]);            ++C[X[i]],++C[Y[i]],C[lca[i]]-=2;        }    }    dfs(1);    for(register int i=2;i<=N;++i)        if(C[i]==tot) maxy=std::max(maxy,dist[i]);    return maxx-maxy<=x;}int main(){    int x,y,z;    lg2[0]=-1;    N=read(),M=read();    for(register int i=1;i
      
       >1]+1;    }    lg2[N]=lg2[N>>1]+1;    LCA_init(1,0);    for(register int i=1;i<=M;++i)    {        X[i]=read(),Y[i]=read();        lca[i]=LCA(X[i],Y[i]);        len[i]=dis[X[i]]+dis[Y[i]]-(dis[lca[i]]<<1);        r=std::max(r,len[i]);    }    while(l<=r)    {        mid=l+r>>1;        if(check(mid))        {            r=mid-1;            Ans=mid;        }        else l=mid+1;    }    printf("%d\n",Ans);    return 0;}