洛谷P2680 运输计划（NOIp2015）（BZOJ4326）

二分答案 LCA 树上差分

洛谷题目传送门

BZOJ题目传送门

题意应该很清楚，即让你把一个边的边权变为0，求完成所有计划所需最小时间。

因为求最小，那么考虑二分答案。

对于距离小于答案的计划直接忽略，对于大于的计划进行统计。最后把大于的计划所经过的共同路径上的边权最大的边变成0，判断是否可行。

于是问题就转化为找出不同路径之间的相交路径。

然后我们可以这样做：

对于一条路径s~t，在s和t上打上1，在lca处打上-2。则从lca到它的父亲节点的这段路经过的次数即为lca的子树和。

其实对应的就是差分。（区间上修改值即修改头尾端点的差值，s~t可以转化为s~lca和lca~t）。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define MAXN 300000
using namespace std;
struct route{//我用的是Tarjan，所以要离线
    int s,t,dis,lca;
};
struct edge{
    int next,to,dis;
};
int n,m,k;
int h1[MAXN+],fa[MAXN+],h2[MAXN+],dis[MAXN+],t[MAXN*+],tt[MAXN+];
edge ed[MAXN*+];
route p[MAXN+];
bool f[MAXN+];
inline char readc(){//读优
    static char buf[],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,,,stdin);
    if (l==r) return EOF; return *l++;
}
inline int _read(){
    int num=; char ch=readc();
    while (ch<'0'||ch>'9') ch=readc();
    while (ch>='0'&&ch<='9') { num=num*+ch-; ch=readc(); } return num;
}
void addedge(int x,int y,int z,int *h){
    ed[++k].next=h[x]; ed[k].to=y; ed[k].dis=z; h[x]=k;
}
int findfather(int x){//并查集
    if (fa[x]==x) return x;
    return fa[x]=findfather(fa[x]);
}
void Tarjan(int x,int father){//LCA
    fa[x]=x; f[x]=true;
    for (int i=h2[x];i;i=ed[i].next){
        int v=ed[i].to;
        if (x==p[v].s&&f[p[v].t]) p[v].lca=findfather(p[v].t);
        if (x==p[v].t&&f[p[v].s]) p[v].lca=findfather(p[v].s);
    }
    for (int i=h1[x];i;i=ed[i].next)
        if (ed[i].to!=father){
            int v=ed[i].to; dis[v]=dis[x]+(tt[v]=ed[i].dis); Tarjan(v,x); fa[v]=x;
        }
}
void srch(int x,int fa){//查询
    for (int i=h1[x];i;i=ed[i].next)
        if (ed[i].to!=fa){
            srch(ed[i].to,x); t[x]+=t[ed[i].to];
        }
}
inline bool pd(int v){//判断
    int sum=,lg=;
    memset(t,,sizeof(t));
    for (int i=;i<=m;i++)
        if (p[i].dis>v){
            t[p[i].s]++; t[p[i].t]++; t[p[i].lca]-=; sum++; lg=max(lg,p[i].dis-v);
        }
    srch(,);
    for (int i=;i<=n;i++) if (t[i]==sum&&tt[i]>=lg) return false;
    return true;
}
int main(){
    n=_read(); m=_read();
    for (int i=;i<n;i++){
        int u=_read(),v=_read(),d=_read(); addedge(u,v,d,h1); addedge(v,u,d,h1);
    }
    for (int i=;i<=m;i++){
        p[i].s=_read(); p[i].t=_read(); 
        addedge(p[i].s,i,,h2); addedge(p[i].t,i,,h2);
    }
    Tarjan(,); int sum=;
    for (int i=;i<=m;i++) sum=max(sum,p[i].dis=dis[p[i].s]+dis[p[i].t]-*dis[p[i].lca]);
    int l=,r=sum;
    while (l<=r){
        int mid=(l+r)/;
        if (pd(mid)) l=mid+; else r=mid-;
    }
    printf("%d\n",l);
    return ;
}