P2680 题解

__vector__ · 2022-06-14 14:40:43 · 个人记录

思路

如果能在 t_1 的时间内解决，那么一定能在 t_2 (t_2 \ge t_1) 的时间内解决。
所以可以二分最短时间。
那如何写 check 呢
设 check 的任务是判断能否在 t 时间内解决，把 m 个运输计划看成树上的 m 条链。

计算出长度最大的链，将其长度设为 imax
算出有多少条链的长度大于 t，设为 sum
求树上每个边被（长度大于 t 的链）经过的次数。
计算出边权最大的（被（长度大于 t 的链）经过的次数等于 sum 的边），将其边权设为 w
判断删除（步骤 4 求出的边）之后能否在 t 时间内解决

解释：

步骤 4 中，某条边被经过次数等于 sum，意思就是说这条边被所有（长度大于 t 的链）经过，就是在找最大公共边
步骤 5 的求解方法：如果 imax - w \le t，那么可以在 t 时间内解决，否则不可以

另外，求链长可以 lca 求出，另外对于一条边，它对应它的起点 u 和终点 t 中深度大的点。

代码

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    const int maxn=300005;
    int n,m;
    int head[maxn];
    struct EDGE
    {
        int to,val,nxt;
    }edge[maxn<<1];
    int cnt;
    inline void add(int u,int to,int val)
    {
        edge[++cnt].to=to;
        edge[cnt].val=val;
        edge[cnt].nxt=head[u];
        head[u]=cnt;
    }
    int fa[20][maxn];
    int dep[maxn];//每个点的深度 
    int dis[maxn];//每个点到根节点的距离 
    int imax;//最长的链的长度 
    int node_to_edge[maxn];
    void dfs(int u,int _fa)
    {
        fa[0][u]=_fa;
        dep[u]=dep[_fa]+1;
        for(int i=1;i<=19;i++)
        {
            fa[i][u]=fa[i-1][fa[i-1][u]];
        }
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(to==_fa)continue;
            node_to_edge[to]=i;
            dis[to]=dis[u]+edge[i].val;
            dfs(to,u);
        }
    }
    inline int lca(int x,int y)
    {
        if(dep[x]<dep[y])swap(x,y);
        for(int i=19;i>=0;i--)
        {
            if(dep[fa[i][x]]>=dep[y])
            {
                x=fa[i][x];
            }
        }
        if(x==y)return x;
        for(int i=19;i>=0;i--)
        {
            if(fa[i][x]!=fa[i][y])
            {
                x=fa[i][x];
                y=fa[i][y];
            }
         } 
         return fa[0][x];
    }
    struct Question
    {
        int u,v,len;
    }q[maxn];
    int cf[maxn]; 
    inline int get_dis(int a,int b)
    {
        int _lca=lca(a,b);
        return dis[a]+dis[b]-2*dis[_lca];
    }
    int sum,w;
    void dfs2(int u,int _fa)
    {
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(to==_fa)continue;
            dfs2(to,u);
            cf[u]+=cf[to];
        }
        if(cf[u]==sum)
        {
            w=max(w,edge[node_to_edge[u]].val);
        }
    }
    inline bool check(int t)
    {
        sum=w=0;
        for(int i=1;i<=m;i++)
        {
            if(q[i].len>t)
            {
                sum++;
                cf[q[i].u]++;
                cf[q[i].v]++;
                cf[lca(q[i].u,q[i].v)]-=2;
            }
        }
        dfs2(1,0);
        for(int i=1;i<=n;i++)
        {
            cf[i]=0;
        }
        if(imax-w<=t)return 1;
        return 0;
    }
    void main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<n;i++)
        {
            int ai,bi,ti;
            scanf("%d%d%d",&ai,&bi,&ti);
            add(ai,bi,ti);
            add(bi,ai,ti);
        }
        dfs(1,0);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&q[i].u,&q[i].v);
            q[i].len=get_dis(q[i].u,q[i].v);
        }
        for(int i=1;i<=m;i++)
        {//求最大链长 
            imax=max(imax,q[i].len);
        }
        int l=0,r=imax;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(check(mid))r=mid;
            else l=mid+1;
        }
        printf("%d",l);
    }
}
int main()
{
    Main::main();
    return 0; 
}

参考博客

communist 的博客
CodyTheWolf 的博客