看心情填坑

看了一下网上好像还没有人写这个的题解。那么本蒟蒻就来献丑了。

题意就是给你一个无根树以及若干条链，可以让一条边权变为0，使得所有链的最长长度最小。

我们考虑去掉的那条边为k,那么假如说对于一条链(x_i,y_i)上有这个点对，那么他最终的权值就是dis(x_i,y_i)-w_k，否则就是dis(x_i,y_i)。

现在考虑把每一条链的距离用LCA的方法弄出来，把所有的链分到两个集合，分别是在链上存在k的集合a，以及不存在k的b，那么有ans=max(max(d_a)-k,max(d_b))，而且有一个显然的结论，就是k是在集合a中的链的交集上的最大权值边时答案最优。

那么我们求出所有的链的长度后，把链按照长度排序，那么我们从(x₁,y₁)开始处理，假如集合a中的max(d_a)即为d_1，集合b中的max(d_b)即为d₂时ans=max(d₁-k,d₂)，且k必须在(x₁,y₁)上;当集合a中的max(d_a)即为d_1，集合b中的max(d_b)即为d3时ans=max(d₁-k,d3)，且k必须在(x₁,y₁)与(x2,y₁)上。

那么我们就得到了算法，从(x₁,y₁)开始做，维护前i条树链上的交集上的最长边k，那么可得ans=min(max(d_i+1,d₁-k))

问题转化成了如何维护若干条树链的交集。我的做法是树链剖分后每次加入一条树链时在这条树链上的所有边上时间戳+1，当一段线段上时间戳=i时他就是可用的，把它的max加入到答案中。为了卡时间，我们可以维护一个标记b，表示在这个线段上是否有可能存在可用的线段，当b=false时就不用下传了，否则传到线段树底部为止（所以说说了半天这个线段树是O(n)的喽）

嗯，从理论上来讲线段树确实是可以卡到O(n)的_(:зゝ∠)_，然而实际上维护树链的时候k显然是非递增的，那么我们在处理操作的时候就可以在d_i+1<d₁-k时退出，实际效率还是很好的（自己骗自己）

下面是被lnj喷树剖长得丑的代码：

#include<cstdio>
#include<algorithm>
using namespace std;
struct work{
    int x,y,l;
}W[300005];
struct ask{
    int y,p,next;
}A[600005];
struct edge{
    int to,next,l;
}e[600005];
struct tree{
    int max,add;
    bool b;
}t[1200005];
int n,m,cnt,tcnt,ans,Ans,x,y,l,dep[300005],son[300005],w[300005],siz[300005],v[300005],a[300005],top[300005],head[300005],fa[300005],ah[300005],Fa[300005],acnt;
bool vis[300005];
inline int read(){
    int ret=0;
    char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline bool cmp(work k1,work k2){return k1.l>k2.l;}
void add(int x,int y,int l){
    cnt++;
    e[cnt].next=head[x];
    e[cnt].to=y;
    e[cnt].l=l;
    head[x]=cnt;
}
void insert(int x,int y,int p){
    acnt++;
    A[acnt].next=ah[x];
    A[acnt].y=y;
    A[acnt].p=p;
    ah[x]=acnt;
}
void dfs(int root){
    siz[root]=1;
    dep[root]=dep[fa[root]]+1;
    for(int i=head[root];i;i=e[i].next)if(e[i].to!=fa[root]){
        fa[e[i].to]=root;
        v[e[i].to]=v[root]+e[i].l;
        dfs(e[i].to);
        siz[root]+=siz[e[i].to];
        if(siz[e[i].to]>siz[son[root]])son[root]=e[i].to;
    }
}
void Dfs(int root){
    tcnt++;
    w[root]=tcnt;
    a[tcnt]=v[root]-v[fa[root]];
    if(son[root]){
        top[son[root]]=top[root];
        Dfs(son[root]);
    }
    for(int i=head[root];i;i=e[i].next)if((e[i].to!=fa[root])&&(e[i].to!=son[root])){
        top[e[i].to]=e[i].to;
        Dfs(e[i].to);
    }
}
int find(int k){
    if(Fa[k]==k)return Fa[k];
    Fa[k]=find(Fa[k]);
    return Fa[k];
}
void Tarjan(int root){
    for(int i=head[root];i;i=e[i].next)if(e[i].to!=fa[root]){
        Tarjan(e[i].to);
        Fa[e[i].to]=root;
    }
    vis[root]=true;
    for(int i=ah[root];i;i=A[i].next)if(vis[A[i].y])W[A[i].p].l=v[root]+v[A[i].y]-v[find(A[i].y)]*2;
}
#define lson index<<1
#define rson (index<<1)+1
void pushdown(int index){
    if(t[index].add){
        t[lson].add+=t[index].add;
        t[rson].add+=t[index].add;
        t[index].add=0;
    }
}
void pushup(int index){
    t[index].b=(t[lson].b&&t[rson].b);
}
void build(int l,int r,int index){
    if(l==r){
        t[index].max=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,lson);
    build(mid+1,r,rson);
    t[index].max=max(t[lson].max,t[rson].max);
}
void Add(int l,int r,int L,int R,int index,int k){
    if(t[index].b)return;
    if((l<=L)&&(r>=R)&&(L==R)){
        if(t[index].add==k){
            ans=max(ans,t[index].max);
            t[index].add++;
        }else t[index].b=true;
        return;
    }
    pushdown(index);
    int mid=(L+R)>>1;
    if(l<=mid)Add(l,r,L,mid,lson,k);
    if(r>mid)Add(l,r,mid+1,R,rson,k);
    pushup(index);
}
void change(int a,int b,int k){
    int A=top[a],B=top[b];
    ans=0;
    while(A!=B){
        if(dep[A]<dep[B])swap(a,b),swap(A,B);
        Add(w[A],w[a],1,tcnt,1,k);
        a=fa[A];A=top[a];
    }
    if(dep[a]>dep[b])Add(w[son[b]],w[a],1,tcnt,1,k);
    if(dep[a]<dep[b])Add(w[son[a]],w[b],1,tcnt,1,k);
}
int main(){
    n=read();m=read();
    for(int i=1;i<n;i++){
        x=read();y=read();l=read();
        add(x,y,l);
        add(y,x,l);
    }
    dfs(1);
    top[1]=1;
    Dfs(1);
    for(int i=1;i<=m;i++){
        W[i].x=read();W[i].y=read();
        insert(W[i].x,W[i].y,i);
        insert(W[i].y,W[i].x,i);
    }
    for(int i=1;i<=n;i++)Fa[i]=i;
    Tarjan(1);
    sort(W+1,W+1+m,cmp);
    build(1,tcnt,1);
    change(W[1].x,W[1].y,0);
    Ans=max(W[1].l-ans,W[2].l);
    for(int i=2;i<=m;i++){
        change(W[i].x,W[i].y,i-1);
        Ans=min(Ans,max(W[1].l-ans,W[i+1].l));
        if(W[1].l-ans>=W[i+1].l)break;
    }
    printf("%d\n",Ans);
}

以下是吐槽：

1、第一次写莫名其妙就写了这么长（果然是话唠吗）

2、TARJAN的LCA会比倍增和树剖快1-3s左右（BZOJ数据）

3、欢迎神犇调教_(:зゝ∠)_