0%

P2680 运输计划

题目链接

因为要知道计划中每两点的路径,所以算出$lca$求最小值。

主要是二分加树上差分就可以了。

#include<bits/stdc++.h>
using namespace std;

const int maxn=300005;
int n,m,cnt,head[maxn],c[maxn],val[maxn];
int son[maxn],fa[maxn],top[maxn],dfn[maxn],dep[maxn],siz[maxn],unk,l=0,r=0,rr=0,dis[maxn];
struct node{
    int n,v,w;
}q[maxn<<1];
struct nod{
    int x,y,lca,w;
}task[maxn];

int read() {
    int s=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0') {s=s*10+ch-'0';ch=getchar();}
    return s*f;
}
void addedge(int x,int y,int z) {
    q[++cnt].n=head[x];
    q[cnt].v=y;
    q[cnt].w=z;
    head[x]=cnt;
    q[++cnt].n=head[y];
    q[cnt].v=x;
    q[cnt].w=z;
    head[y]=cnt;
}

void dfs1(int u,int f,int d) {
    fa[u]=f,dep[u]=d,siz[u]=1;
    for(int i=head[u];i;i=q[i].n) {
        int v=q[i].v;
        if(v==f) continue;
        val[v]=q[i].w;
        dis[v]=dis[u]+q[i].w;
        dfs1(v,u,d+1);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int t) {
    top[u]=t,dfn[++unk]=u;
    if(!son[u]) return;
    dfs2(son[u],t);
    for(int i=head[u];i;i=q[i].n) {
        int v=q[i].v;
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
int lca(int u,int v) {
    while(top[u]!=top[v]) {
        if(dep[top[u]]>dep[top[v]])
            u=fa[top[u]];
        else
            v=fa[top[v]];
    }
    return dep[u]>dep[v]?v:u;
}
bool check(int x) {
    int sum=0;
    memset(c,0,sizeof(c));
    for(int i=1;i<=m;i++) {
        int xx=task[i].x,y=task[i].y;
        if(task[i].w<=x) continue;
        c[xx]++;
        c[y]++;
        c[task[i].lca]-=2;
        sum++;
    }
    for(int i=n;i>=1;i--) {
        c[fa[dfn[i]]]+=c[dfn[i]];
        if(c[dfn[i]]==sum && val[dfn[i]]>=rr-x) return 1;
    }
    return 0;
}

int main() {
//    freopen("test.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<n;i++) {int a,b,c;cin>>a>>b>>c;addedge(a,b,c);}
    dfs1(1,0,1);
    dfs2(1,1);
    for(int i=1;i<=m;i++) {
        cin>>task[i].x>>task[i].y;
        task[i].lca=lca(task[i].x,task[i].y);
        task[i].w=dis[task[i].x]+dis[task[i].y]-2*dis[task[i].lca];
        if(task[i].w>r) r=task[i].w;
//        cout<<task[i].w<<endl;
    }
    rr=r;
    while(l<r) {
        int mid=(l+r)>>1;
        if(check(mid)) {
            r=mid;
        }
        else {
            l=mid+1;
        }
    }
    cout<<r<<endl;
    return 0;
}