运输计划[二分答案 LCA 树上差分]

概括一下题意

给一颗有\(n\)个点带边权的树，有\(m\)个询问，每次询问\(u,v\)两点间的权值和，你可以将树中任意一条边的边权变为\(0\)，问经过一次修改，这\(m\)个询问中最大的权值和最小可以是多少

\(\mathcal{Solution}\)

最大最小，显然二分
二分最小是多少，单调性显然

如何\(check\)
设当前二分到了\(x\)，这\(m\)个询问中有\(tot\)个权值和大于\(x\)的询问
那么我们要将一条边变为\(0\)，这条边肯定得到被这\(tot\)个询问都经过才行，否则就至少有一条权值和大于\(x\)的询问

那么在所有被这\(tot\)个询问经过的边中，去掉权值最大的那条边肯定最优
之后看一看是否满足，只需考虑原最大的询问是否已经小于等于\(x\)

看一条边是否被这\(tot\)个询问经过，可以用树上差分统计

倍增求\(LCA\)会被卡，卡了我一个下午，后来把二分枚举的上下界调了一下就过了
这告诉我们，二分答案时最好不要无脑二分

\(l\)设初值为最大的询问减去最大的边权，是负数就设为\(0\)
\(r\)设初值为最大的询问

\(\mathcal{Code}\)

为方便阅读，代码中有折叠（扒下来到vim里看吧）

\(val[i]\)是\(i\)的父亲与\(i\)相连的边的权值

/*******************************Author:Morning_GloryLANG:C  Created Time:2019年09月09日 星期一 14时53分08秒*******************************/#include <cstdio>#include <fstream>#include <algorithm>using namespace std;const int maxn = 300005;const int maxm = 600005;const int limit = 23;//{{{cinstruct IO{    template<typename T>    IO & operator>>(T&res){        res=0;        bool flag=false;        char ch;        while((ch=getchar())>'9'||ch<'0')   flag|=ch=='-';        while(ch>='0'&&ch<='9') res=(res<<1) (res<<3) (ch^'0'),ch=getchar();        if (flag)   res=~res 1;        return *this;    }}cin;//}}}int n,m,cnt,num,tot,mx,l,r;int head[maxn],nxt[maxm],to[maxm],w[maxm],dep[maxn],lg[maxn];int sum[maxn],u[maxn],v[maxn],val[maxn],len[maxn],dis[maxn],lca[maxn];int fa[maxn][limit 1];//{{{addvoid add (int u,int v,int val){    nxt[  cnt]=head[u],head[u]=cnt,to[cnt]=v,w[cnt]=val;}//}}}//{{{Dealvoid Deal (int x){    for (int i=1;i<=lg[dep[x]];  i) fa[x][i]=fa[fa[x][i-1]][i-1];    for (int e=head[x];e;e=nxt[e]){        if (to[e]==fa[x][0])    continue;        val[to[e]]=w[e];        fa[to[e]][0]=x;        dep[to[e]]=dep[x] 1;        len[to[e]]=len[x] w[e];        Deal(to[e]);    }}//}}}//{{{LCAint LCA (int x,int y){    if (dep[x]<dep[y])  swap(x,y);    for (int i=lg[dep[x]];~i;--i)        if (dep[fa[x][i]]>=dep[y])  x=fa[x][i];    if (x==y)   return y;    for (rint i=lg[dep[x]];~i;--i)        if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];    return fa[x][0];}//}}}//{{{dfsvoid dfs (int x){    for (int e=head[x];e;e=nxt[e]){        if (to[e]==fa[x][0])    continue;        dfs(to[e]);        sum[x] =sum[to[e]];        sum[to[e]]=0;        if (sum[x]==tot)    num=max(num,val[x]);    }}//}}}//{{{checkbool check (int x){    sum[1]=num=tot=0;    for (int i=1;i<=m;  i)        if (dis[i]>x){              tot;              sum[u[i]],  sum[v[i]];            sum[lca[i]]-=2;        }    dfs(1);    return mx-num<=x;}//}}}int main(){    lg[0]=-1,dep[1]=1;    for (int i=1;i<=maxn-5;  i) lg[i]=lg[i>>1] 1;    cin>>n>>m;    for (int i=2;i<=n;  i){        int x,y,wi;        cin>>x>>y>>wi;        add(x,y,wi),add(y,x,wi);        l=max(l,wi);    }    Deal(1);    for (int i=1;i<=m;  i){        cin>>u[i]>>v[i];        lca[i]=LCA(u[i],v[i]);        dis[i]=len[u[i]] len[v[i]]-2*len[lca[i]];        mx=max(mx,dis[i]);    }    r=mx,l=max(0,r-l);    while (l<r){        int mid=(l r)/2;        if (check(mid)) r=mid;        else    l=mid 1;    }    printf("%d\n",l);    return 0;}

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧

来源：https://www.icode9.com/content-4-444651.html