运输计划[做题笔记]

题意

概括：给定 \(n\) 个节点的树和 \(n-1\) 条边的权值，现在可以将一条边的权值改为 \(0\) 。找出一条边，使得将这条边权值赋为 \(0\) 时，\(T\) 组节点 \(u,v\) 之间的距离最大值最小，输出最小值。

思路分析

一开始想假了，天真的以为被 \(T\) 组节点 \(u,v\) 覆盖的次数最多，且权值较大的边就是要删去的边，\(38\)分，查题解才知道是二分答案。

不过确实，求最大值最小，的确是要二分的。先预处理出 \(T\) 组节点 \(u,v\) 的 \(LCA\) 和距离 \(len\) ,那么答案二分的区间就是 \([0,MAXLEN]\) 。

二分答案的精髓是什么？是check()函数
                            ----miaomiao

那么，对于当前 \(check\) 的 \(x\)，有：

• \(first\)，要使 \(x\) 合法，那么删去这条边后，所有路径长 \(<= x\)
• \(second\)，要找出这条边，首先要枚举所有的 \(len\) ，记录比\(x\)大的个数 \(sum\) ,并将这些边在树上差分。如果有一条边被上述边同时覆盖，显然这就是我们要赋\(0\)的最优边(当然可能存在多条，显然要取边权最大的 \(max\_ len\))
• \(third\)，用 \(MAXLEN-max\_ len\)，如果结果\(<=x\)，显然合法(最长边都满足，底下那些小弟就更不用说了)

弱弱地提醒句，求LCA要用tarjan，倍增过不了……(狂D不止）

\(AC \ code\)

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define N 300010
#define int long long
int n,m;int ans;
struct EDGE{
    int next,to,t;
}e[N<<1],d[N<<1];
int spx[N];
int he[N],tot;
int hd[N];
int edge[N];
int MAXLEN;
struct SOLVE{
    int u,v,lca,len;
}q[N];

inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')  f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')    x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x)
{
    if(x<0)  putchar('-'),x=-x;
    if(x>9)    write(x/10);
    putchar(x%10+'0');
    return;
}

void add(int u,int v,int t)
{
    tot++;
    e[tot].to=v;
    e[tot].next=he[u];
    he[u]=tot;
    e[tot].t=t;
    return ;
}
void add_d(int u,int v)
{
    tot++;
    d[tot].to=v;
    d[tot].next=hd[u];
    hd[u]=tot;
    return;
}
int fa[N];
int dis[N];

int find(int x)
{
    if(x==fa[x])  return x;
    return fa[x]=find(fa[x]);
}
bool f[N];
void tarjan(int x,int pre)
{
    int y;
    for(int i=he[x];i>0;i=e[i].next)
    {
        y=e[i].to;
        if(y!=pre)
        {
            edge[y]=i;
            dis[y]=dis[x]+e[i].t;
            tarjan(y,x);
            int fa_x=find(x);
            int fa_y=find(y);
            if(fa_x!=fa_y)
                fa[fa_y]=fa_x;
            f[y]=1;
        }
    }
    for(int i=hd[x];i>0;i=d[i].next)
    {
        y=d[i].to;
        if(f[y]){
            int now=(i+1)>>1;
            q[now].lca=find(y);
            q[now].len=dis[x]+dis[y]-2*dis[q[now].lca];
            MAXLEN=max(MAXLEN,q[now].len);
        }
    }
}
int sum,max_len;
void dfs_spx(int x,int pre)
{
    int y;
    for(int i=he[x];i>0;i=e[i].next)
    {
        y=e[i].to;
        if(y!=pre)
        {
            dfs_spx(y,x);
            spx[x]+=spx[y];
        }
    }
    if(spx[x]==sum)
        max_len=max(max_len,e[edge[x]].t);
}
bool judge(int x)
{
    for(int i=0;i<=n;i++)  spx[i]=0;
    sum=0;max_len=0;
    for(int i=1;i<=m;i++)
    {
        if(q[i].len>x)
        {
            sum++;
            spx[q[i].u]++;
            spx[q[i].v]++;
            spx[q[i].lca]-=2;
        }
    }
    dfs_spx(1,0);
    if(MAXLEN-max_len<=x)
        return 1;
    return 0;
}

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read();m=read();
    for(int i=1;i<n;++i)
    {
        int a,b,c;
        a=read(),b=read(),c=read();
        add(a,b,c);add(b,a,c);
    }
    tot=0;
    for(int i=1;i<=n;++i)    fa[i]=i;
    for(int i=1;i<=m;++i)
    {
        int u,v;
        u=read(),v=read();
        q[i].u=u;q[i].v=v;
        add_d(u,v);
        add_d(v,u);
    }
    tarjan(1,0);
    int st=0,ed=MAXLEN;
    while(st<ed)
    {
        int mid=(st+ed)>>1;
        if(judge(mid))    ed=ans=mid;
        else    st=mid+1;
    }
    write(ans);
    return 0;
}