P2680 [NOIP2015 提高组] 运输计划 题解

· · 题解

前言

小不清新做法，没有使用树剖、二分、线段树中的任何一个。

题意

给定大小为 n，第 i 条边带权 w_i 的树，以及 m 条树上路径。现在你可以将一条边的长度改为 0，求出所有可能的情况中，m 条路径中最长路径长度的最小值。

Solution

看到这个最长链最小，我们直接二分强忍住二分的欲望，先枚举清除哪条边。

发现清除一条边之后所有路径自然划分为两个部分：穿过这条边的和不穿过这条边的。

如果我们取出这两个部分的最长路径记为 l_1,l_2，答案就应该是 max(l_1-w,l_2)。

那怎么判断是否穿过呢？

我们发现，如果一条链两点都在 u 子树里或者都不在 u 子树里，都不会穿过 (u,f_u) 这条边。

如果一个在一个不在，就穿过了。

在 dfs 序上刻画“在子树里”的条件，把两个端点的限制条件放到平面上，这是一个二维数点问题，于是秒了……

就怪了。

Solution 1

放到平面上，发现不穿过的区域形如：

周围四角直接树状数组就好了，四个边从四个方向分别扫描线然后线段树也行，中间这个 4-side 正方形求最大值没法差分。

上树套树。

时间复杂度：O(n\log^2n)。

代码：没写。

期望得分：没试过，但是最大的点肯定过不了。

Solution 2

还是回到树的结构上看吧。

中间的矩形表示路径两端点 u,v 都在子树内的情况，发现这种情况下对于给定 (u,v)，满足条件的只有它们的所有公共祖先。

于是差分一下把这个路径挂在 LCA 上，dfs 时候走到 LCA 就把这条路径丢出去，离开时候再加回来，并使用堆来维护最大值。

时间复杂度：O(n\log n)。

代码：还是没写。

期望得分：反正我觉得最大的点还是过不了，但是至少 95 吧。

Solution 3

周围四圈需要四次扫描线，显然常数爆炸。

但是注意到：我们把不穿过的路径重复计算在穿过的路径里面，对最后答案没有影响（因为只是从 l_2 变成了 max(l_2-w,l_2)）。

那么不妨把之前除了中间那个矩形之外的区域全部视作穿过，对之前那个堆的补集再开一个堆维护，就很简单了。

但是四个角还是得算在不穿过里面，所以至少还是得从两个方向扫描线并维护前后缀最大值，使用树状数组解决。

实际实现时候用懒惰删除的优先队列替代堆，LCA 和路径长度用倍增解决。

时间复杂度 O(n\log n)，我不确定需不需要卡常，因为我写出来最慢的点 983ms。

期望得分：100。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define N 314514
int t[N][2],n;
void change(int x,int v)
{
    int xx=x;
    for(;x<=n;x+=x&-x) t[x][0]=max(t[x][0],v);
    for(x=xx;x;x-=x&-x) t[x][1]=max(t[x][1],v);
}
int ask(int x,int ty)
{
    int ans=0;
    if(!ty)
        for(;x;x-=x&-x) ans=max(ans,t[x][0]);
    else
        for(;x<=n;x+=x&-x) ans=max(ans,t[x][1]);
    return ans;
}
#define fi first
#define se second
vector<pair<int,int> > e[N]; 
int sz[N],f[N][20],fd[N][20],dfn[N],df,nfd[N],d[N],dis[N],zt[N];
void dfs(int u)
{
    sz[u]=1,dfn[u]=++df,nfd[df]=u;
    for(int i=1;(1<<i)<=d[u];i++) f[u][i]=f[f[u][i-1]][i-1],fd[u][i]=fd[u][i-1]+fd[f[u][i-1]][i-1];
    for(auto v:e[u]) if(!dfn[v.fi]) d[v.fi]=d[u]+1,f[v.fi][0]=u,fd[v.fi][0]=v.se,dfs(v.fi),sz[u]+=sz[v.fi];
}
pair<int,int> lca(int x,int y)
{
    int ad=0;
    if(d[x]<d[y]) swap(x,y);
    for(int i=19;i>=0;i--) if(d[f[x][i]]>=d[y]) ad+=fd[x][i],x=f[x][i];
    if(x==y) return {x,ad};
    for(int i=19;i>=0;i--) if(f[x][i]!=f[y][i]) ad+=fd[x][i]+fd[y][i],x=f[x][i],y=f[y][i];
    ad+=fd[x][0]+fd[y][0];
    return {f[x][0],ad};
}
int u,v,w,x,y,m,nc[N],c[N],i,ans=1e9;
priority_queue<pair<int,int>> in,out;
vector<int> lc[N];
void dfs2(int u)
{
    while(in.size()&&zt[in.top().se]==1) out.push(in.top()),in.pop();
    while(out.size()&&zt[out.top().se]==0) in.push(out.top()),out.pop();
    if(in.size()) nc[u]=in.top().fi;
    if(out.size()) c[u]=out.top().fi;
    for(auto x:lc[u]) zt[x]=1;
    for(auto v:e[u]) if(d[v.fi]>d[u]) dfs2(v.fi);
    for(auto x:lc[u]) zt[x]=0;
 }
vector<pair<int,int> > q[N],uq[N],chg[N];
int main()
{
    cin.tie(0)->sync_with_stdio(0);cout.tie(0);
    cin>>n>>m;
    for(i=1;i<n;i++) cin>>u>>v>>w,e[u].push_back({v,w}),e[v].push_back({u,w});
    dfs(1);
    for(i=1;i<=m;i++)
    {
        cin>>x>>y;
        pair<int,int> l=lca(x,y);lc[l.fi].push_back(i);dis[i]=l.fi;
        in.push({l.se,i});
        chg[dfn[x]].push_back({dfn[y],l.se});
    }
    dfs2(1);
    for(i=1;i<=n;i++)
    {
        int l=dfn[i]-1,r=dfn[i]+sz[i];
        q[l].push_back({l,i}),q[l].push_back({-r,i});
        uq[r].push_back({l,i}),uq[r].push_back({-r,i});
    }
    for(i=1;i<=n;i++)
    {
        for(auto x:chg[i]) change(x.fi,x.se);
        for(auto x:q[i]) nc[x.se]=max(nc[x.se],ask(abs(x.fi),x.fi>0?0:1));
    }
    memset(t,0,sizeof(t));
    for(i=n;i>=1;i--)
    {
        for(auto x:chg[i]) change(x.fi,x.se);
        for(auto x:uq[i]) nc[x.se]=max(nc[x.se],ask(abs(x.fi),x.fi>0?0:1));
    }
    for(i=2;i<=n;i++) ans=min(ans,max(c[i]-fd[i][0],nc[i]));
    cout<<ans;
    return 0;
}

The End.