洛谷2680 运输计划

Luogu

分析

显然可以二分答案。那么我们只需要判断是否存在一条边,满足它被所有长度 $>mid$ 的运输计划覆盖,而且这些运输计划长度减掉它的长度后 $\leq mid$。

显然我们会选所有满足「被所有长度 $>mid$ 的运输计划覆盖」的边中长度最大的那个,因此我们只需要想一想怎么求出一条边被覆盖的次数。

这个直接树上差分即可,当然也可以像我一样写树剖+线段树(但是不吸氧可能会 T)

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=300000+10;

int n,m;

struct edge { int v,w,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}

struct query { int u,v;; } q[N];

int dep[N],dis[N],fa[N],sz[N],hson[N],top[N],w[N];
int dfn[N],tim=0;
inline void dfs1(int u,int f) {
    fa[u]=f,dep[u]=dep[f]+1,dis[u]=dis[f]+w[u],sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        w[v]=e[i].w; dfs1(v,u); sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
inline void dfs2(int u,int anc) {
    top[u]=anc,dfn[u]=++tim;
    if (hson[u]) dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
}
inline int getlca(int u,int v) {
    while (top[u]!=top[v]) {
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}
inline int getdis(int u,int v) {
    int t=getlca(u,v);
    return dis[u]+dis[v]-(dis[t]<<1);
}

#define ls (o<<1)
#define rs (o<<1|1)
int sumv[N<<2],addv[N<<2];
inline void pushup(int o) { sumv[o]=sumv[ls]+sumv[rs]; }
inline void pushdown(int o,int l,int r) {
    if (addv[o]) { int mid=(l+r)>>1;
        addv[ls]+=addv[o],sumv[ls]+=(mid-l+1)*addv[o];
        addv[rs]+=addv[o],sumv[rs]+=(r-mid)*addv[o];
        addv[o]=0;
    }
}
inline void build(int o,int l,int r) {
    sumv[o]=addv[o]=0;
    if (l==r) return;
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
}
inline void modify(int o,int l,int r,int ql,int qr,int w) {
    if (ql<=l&&r<=qr) { addv[o]+=w,sumv[o]+=w*(r-l+1); return; }
    int mid=(l+r)>>1; pushdown(o,l,r);
    if (ql<=mid) modify(ls,l,mid,ql,qr,w);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
    pushup(o);
}
inline int query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return sumv[o];
    int mid=(l+r)>>1,res=0; pushdown(o,l,r);
    if (ql<=mid) res+=query(ls,l,mid,ql,qr);
    if (qr>mid) res+=query(rs,mid+1,r,ql,qr);
    pushup(o); return res;
}
#undef ls
#undef rs

inline void chain_modify(int u,int v) {
    while (top[u]!=top[v]) {
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        modify(1,1,n,dfn[top[u]],dfn[u],1);
        u=fa[top[u]];
    }
    if (dep[u]<dep[v]) swap(u,v);
    modify(1,1,n,dfn[v]+1,dfn[u],1);
}

inline int check(int mid) {
    build(1,1,n); int mx=0,cnt=0;
    for (re int i=1;i<=m;++i) {
        int u=q[i].u,v=q[i].v;
        if (getdis(u,v)>mid)
            ++cnt,mx=max(mx,getdis(u,v)),chain_modify(u,v);
    }
    for (re int i=2;i<=n;++i)
        if (query(1,1,n,dfn[i],dfn[i])==cnt&&mx-w[i]<=mid) return 1;
    return 0;
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read(),w=read();
        addEdge(u,v,w),addEdge(v,u,w);
    }
    dfs1(1,0),dfs2(1,1);
    for (re int i=1;i<=m;++i) q[i].u=read(),q[i].v=read();
    int L=0,R=3e8;
    while (L<R) {
        int mid=(L+R)>>1;
        if (check(mid)) R=mid;
        else L=mid+1;
    }
    printf("%d\n",L);
    return 0;
}
最后修改:2019 年 11 月 04 日 04 : 54 PM

发表评论