题解 luoguP2680 【运输计划】

思路：二分+LCA

看到这道题目的第一眼，就想到了LCA，但是维护了LCA后该如何求答案呢？这时便可以考虑二分。

我们可以先预处理所有任务所需的时间，以及起点和终点的LCA，然后二分任务需要的最大时间。

预处理时间和LCA都很简单，主要是check怎么写。

很容易可以想到如果时间大于mid的任务所走的路径都覆盖过某一条边，且这条边消失都可以让任务时间小于mid，那么这个mid肯定是合法的。

那么我们就可以预处理一个 up 数组，up i 表示节点 i 到他父亲的距离。在check的时候枚举每一个时间大于 mid 的任务，遍历一遍他的路径，在每条消失就可以使时间小于等于 mid 的边打上一个标记，如果有一条边上的标记等于时间大于 mid 的任务数，则返回 true。

bool check(int len)
{
    if(plan[m].dist<=len)return true;
    for(int i=1;i<=n;i++)used[i]=0;
    int x=0,maxn=0;
    //x是大于 mid 的任务数，在循环中统计，maxn是边上标记个数的最大值
    for(int i=m;i>=1;i--)
    {
        if(plan[i].dist<=len)break;
        x++;
        int u=plan[i].st,v=plan[i].ed,luv=plan[i].lca,c=plan[i].dist-len;
        while(u!=luv)
        {
            if(up[u]>=c)
            {
                used[u]++;
                maxn=maxn<used[u]?used[u]:maxn;
            }
            u=f[u][0];
        }
        while(v!=luv)
        {
            if(up[v]>=c)
            {
                used[v]++;
                maxn=maxn<used[v]?used[v]:maxn;
            }
            v=f[v][0];
        }//因为时限是2s，所以只需要暴力枚举端点到LCA的每一条边就可以了
        if(maxn<x)return false;
    }
    return true;
}

完整代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 300000 + 10;

inline int read()
{
    int res=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+ch-'0',ch=getchar();
    return res;
}

struct edge{
    int next,to,w;
}r[N<<1];

int head[N],tot;

void add(int u,int v,int w)
{
    r[++tot]=(edge){head[u],v,w};
    head[u]=tot;
}

int dep[N],f[N][22],sum[N],up[N];

void dfs(int u,int father,int deep)
{
    dep[u]=deep;
    f[u][0]=father;
    for(int e=head[u];e;e=r[e].next)
    {
        int v=r[e].to;
        if(v==father)continue;
        sum[v]=sum[u]+r[e].w;
        //处理从根节点（我这里将根节点设为1）到u的距离
        up[v]=r[e].w;
        //处理自己到父亲的距离，其实不要也可以，直接用sum求就可以
        dfs(v,u,deep+1);
    }
}

int LCA(int u,int v)
{
    if(dep[u]<dep[v])swap(u,v);
    for(int i=19;i>=0;i--)
        if(dep[f[u][i]]>=dep[v])
            u=f[u][i];
    if(u==v)return u;
    for(int i=19;i>=0;i--)
        if(f[u][i]!=f[v][i])
            u=f[u][i],v=f[v][i];
    return f[u][0];
}//基本操作

struct node{
    int st,ed,dist,lca;
    bool operator <(const node x)
    {
        return dist<x.dist;
    }
}plan[N];

int n,m,ans;

int used[N];

bool check(int len)
{
    if(plan[m].dist<=len)return true;
    for(int i=1;i<=n;i++)used[i]=0;
    int x=0,maxn=0;
    for(int i=m;i>=1;i--)
    {
        if(plan[i].dist<=len)break;
        x++;
        int u=plan[i].st,v=plan[i].ed,luv=plan[i].lca,c=plan[i].dist-len;
        while(u!=luv)
        {
            if(up[u]>=c)
            {
                used[u]++;
                maxn=maxn<used[u]?used[u]:maxn;
            }
            u=f[u][0];
        }
        while(v!=luv)
        {
            if(up[v]>=c)
            {
                used[v]++;
                maxn=maxn<used[v]?used[v]:maxn;
            }
            v=f[v][0];
        }
        if(maxn<x)return false;
    }
    return true;
}

int main()
{
    n=read(),m=read();
    for(int i=1,u,v,w;i<n;i++)
        u=read(),v=read(),w=read(),add(u,v,w),add(v,u,w);
    dfs(1,0,1);
    for(int k=1;k<=19;k++)
        for(int i=1;i<=n;i++)
            f[i][k]=f[f[i][k-1]][k-1];
    for(int i=1,u,v;i<=m;i++)
    {
        u=read(),v=read();
        int luv=LCA(u,v);
        plan[i]=(node){u,v,sum[u]+sum[v]-(sum[luv]<<1),luv};
        //预处理每个任务的时间和两个端点的LCA
    }
    sort(plan+1,plan+m+1);
    int l=0,r=300000000;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(mid))r=mid,ans=mid;
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}

做的时候并没有看题解，但貌似题解中有个人的思路几乎和我一样？仔细看了一下他似乎并没有讲的很清楚。

丢人瞬间：

在求差的时候居然拿小的数去减了大的数，成功打破我一遍AC紫题的梦想。。

题解 luoguP2680 【运输计划】

原文：https://www.cnblogs.com/Y-inG/p/11749187.html