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

印度阿三17 2019-09-09

展开全文

概括一下题意

给一颗有\(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_Glory
LANG: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;
//{{{cin
struct 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];
//{{{add
void add (int u,int v,int val)
{
    nxt[  cnt]=head[u],head[u]=cnt,to[cnt]=v,w[cnt]=val;
}
//}}}
//{{{Deal
void 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]);
    }
}
//}}}
//{{{LCA
int 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];
}
//}}}
//{{{dfs
void 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]);
    }
}
//}}}
//{{{check
bool 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;
}