给出一棵树和m条路线,树上每条边都有长度.现在可以把一条边的长度置为0,求在置为0后,这m条路线的最大长度最小是多少.

链接

LOJ

COGS

BZOJ

题解

首先有个显然的结论是置为0的边一定位于初始时的最长路线上.故可以二分答案,把所有长度大于二分值的路线上的所有边打上一次标记.然后检查最长路线上的所有边,当且仅当这条边被标记的次数恰好是长度大于二分值的路线的数量,以及把这条边置为0后可以保证最长路线的长度小于等于二分值,则该答案合法.标记路径可以使用树上差分解决.时间复杂度为

O(nlogn)

P.S.这道题最后一个点卡常QAQ偷偷开了O3才勉强卡过去.经过事后的测试,树剖求LCA比倍增求LCA大约可以节省10~20%的时间.所以正确的卡常姿势应该是拿树剖去写.

代码

#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 300010
#define LL long long
using namespace std;

int n,m,i,x,y,Z,lsum=1,L,Ans;
int head[N],d[N],fa[N][20],l[N][20],v[N],z[N];

struct Edge{
    int t,next,l;
}e[N*2];

struct Data{
    int x,y,l,lca;
}a[N];

inline void Swap(int &a,int &b){a^=b^=a^=b;}


const int MAXSIZE =1<<20;
char buf[MAXSIZE],*p1,*p2;
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1==p2)?EOF:*p1++)
inline int rd(){
    register int x=0;
    char c=gc();
    while (!isdigit(c)) c=gc();
    while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=gc();
    return x;
}

inline bool cmp(const Data &a,const Data &b){return (a.l<b.l);}

inline void Add(int s,int t,int l){
    e[lsum].t=t;    e[lsum].l=l;    e[lsum].next=head[s];   head[s]=lsum++;
}

inline void Maketree(int x,int f){
    register int i=0,j=0,p=0;
    for (i=head[x];i;i=e[i].next){
        if (e[i].t==f)  continue;
        p=e[i].t;
        fa[p][0]=x; l[p][0]=e[i].l;
        d[p]=d[x]+1;
        for (j=1;j<=19;j++){
            if (!fa[p][j-1])    break;
            fa[p][j]=fa[fa[p][j-1]][j-1];
            l[p][j]=l[fa[p][j-1]][j-1]+l[p][j-1];
        }
        Maketree(p,x);
    }
}

inline int LCA(int x,int y){
    register int sum=0,dis=0,i=0;
    (d[x]<d[y])?Swap(x,y):void(0);
    dis=d[x]-d[y];
    for (i=0;i<=19&&dis>=(1<<i);++i)
        (dis&(1<<i))?sum+=l[x][i],x=fa[x][i]:0;
    if (x==y){
        L=x;    return sum;
    }
    for (i=19;i>=0;--i)
        if (fa[x][i]!=fa[y][i]){
            sum+=l[x][i]+l[y][i];
            x=fa[x][i]; y=fa[y][i];
        }
    L=fa[x][0];
    return sum+l[x][0]+l[y][0];
}

inline void Dfs(int x,int f){
    for (register int i=head[x];i;i=e[i].next)
        if (e[i].t!=f)
            Dfs(e[i].t,x),v[x]+=v[e[i].t];
}

inline bool Check(int s){
    register int i=0,sum=0,x=0,p=a[m].lca,q=a[m].l-s;
    memset(v,0,sizeof(v));
    for (i=m;i;--i){
        if (a[i].l<=s)  break;
        ++sum;  ++v[a[i].x];    ++v[a[i].y];
        v[a[i].lca]-=2;
    }
    Dfs(1,0);
    for (i=1;i<=z[0];++i)
        if (l[z[i]][0]>=q&&v[z[i]]>=sum)    return 1;
    return 0;
}

inline void Work(){
    register int low=0,high=a[m].l,mid=0,x=0,p=a[m].lca;
    x=a[m].x;
    while (x!=p){
        z[++z[0]]=x;    x=fa[x][0];
    }
    x=a[m].y;
    while (x!=p){
        z[++z[0]]=x;    x=fa[x][0];
    }
    while (low<=high){
        mid=(low+high)>>1;
        (Check(mid))?Ans=mid,high=mid-1:low=mid+1;
    }
    printf("%d\n",Ans);
}

int main(){
    #ifdef __Marvolo
    freopen("transport20.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=rd(); m=rd();
    for (i=1;i<n;i++){
        x=rd(); y=rd(); Z=rd();
        Add(x,y,Z); Add(y,x,Z);
    }
    Maketree(1,0);
    for (i=1;i<=m;i++){
        a[i].x=rd();    a[i].y=rd();
        a[i].l=LCA(a[i].x,a[i].y);
        a[i].lca=L;
    }
    sort(a+1,a+1+m,cmp);
    Work();
    return 0;
}