P1024 · OFFICIAL SOLUTION

P1024 万山舆共渡官方题解

Gioush OJ · P1024 万山舆共渡

万山舆共渡

【题目简述】

给定一棵带权树和 $m$ 条运输路径。可以选择一条边使其边权变为 $0$ ，求所有路径长度最大值的最小可能值。

【数据点 1∼81\sim81∼8】

【一条运输计划】

当 $m=1$ 时，直接找出这条路径，设长度为 $L$ 、其中最大边权为 $W_{\max}$ 。显然清零最大边最优，答案为 $L-W_{\max}$ 。当 $n,m$ 均不大时，枚举清零哪条边，再重新计算所有路径并取最大值。

【数据点 9∼149\sim149∼14】

【链上的判定】

二分答案 $t$ 。原长度不超过 $t$ 的运输计划无需处理；其余所有超时路径都必须经过同一条被清零的道路。

【解法】

对所有超时区间做差分。设超时路径有 $c$ 条，若某条道路被覆盖了 $c$ 次，它便同时属于全部超时路径。所有这种道路中取权值最大的 $w$ ；设原最大路径长为 $L_{\max}$ ，当且仅当 $L_{\max}-w\le t$ 时当前 $t$ 合法。

【正解】

【树上差分】

对每条超时路径 $(u,v)$ ，令 $z=\operatorname{LCA}(u,v)$ ，作

\begin{cases} \operatorname{Diff}(u)\leftarrow\operatorname{Diff}(u)+1,\\ \operatorname{Diff}(v)\leftarrow\operatorname{Diff}(v)+1,\\ \operatorname{Diff}(z)\leftarrow\operatorname{Diff}(z)-2. \end{cases}

【解法】

回溯时将儿子的差分和加到父亲。把道路 $(u,\operatorname{Fa}(u))$ 看作结点 $u$ 派生的道路，则回溯后的 $\operatorname{Diff}(u)$ 正是这条道路被多少条超时路径覆盖。

若存在道路满足 $\operatorname{Diff}(u)=c$ 且边权 $w\ge L_{\max}-t$ ，清零它后所有超时路径都不超过 $t$ ；反之，任何可行道路都必须同时满足这两个条件。

【复杂度分析】

LCA 预处理为 $\mathcal{O}(n\log n)$ ；一次判定为 $\mathcal{O}(n+m)$ ，总复杂度为 $\mathcal{O}(n\log n+(n+m)\log V)$ 。

【参考代码】

1#include <cstdio>2#include <cstring>3#include <algorithm>4#define MAXN 3000105using namespace std;6int Total=0,Head[MAXN],Depth[MAXN],Count[MAXN],Fa[MAXN][22],D[MAXN],Diff[MAXN];7struct edge{8    int Ed,Next,Val;9}Edge[MAXN<<1];10void Edge_Add(int St,int Ed,int Val){11    Edge[++Total]={Ed,Head[St],Val};12    Head[St]=Total;13}14struct Plan{15    int u,v,Val,lca;16}p[MAXN];17bool cmp(Plan a,Plan b) {return a.Val<b.Val;}18void DFS(int Now,int From){19    for(int i=1;i<=21;i++){20        Fa[Now][i]=Fa[Fa[Now][i-1]][i-1];21    }22    for(int i=Head[Now];i;i=Edge[i].Next){23        int To=Edge[i].Ed;24        if(To==From) continue;25        D[To]=D[Now]+1;26        Depth[To]=Depth[Now]+Edge[i].Val;27        Fa[To][0]=Now;28        DFS(To,Now);29    }30    return;31}32inline int LCA(int x,int y){33    if(D[x]<D[y]) swap(x,y);34    for(int i=21;i>=0;i--){35        if(D[Fa[x][i]]>=D[y]) x=Fa[x][i];36    }37    if(x==y) return x;38    for(int i=21;i>=0;i--){39        if(Fa[x][i]!=Fa[y][i]){40            x=Fa[x][i];y=Fa[y][i];41        }42    }43    return Fa[x][0];44}45int n,m,In1,In2,In3;46bool Tag=0;47inline int Run(int Now,int From,int cnt,int t){48    int Sum=0,tmp=0;49    for(int i=Head[Now];i;i=Edge[i].Next){50        int To=Edge[i].Ed;51        if(To==From)continue;52        tmp=Run(To,Now,cnt,t);53        Sum+=tmp;54        if(tmp==cnt&&Edge[i].Val>=t){Tag=1;}55    }56    return Sum+Diff[Now];57}58bool Judge(int t){59    int cnt=0;60    Tag=0;61    memset(Diff,0,sizeof(Diff));62    for(int i=1;i<=m;i++){63        if(p[i].Val<=t) continue;64        Diff[p[i].u]++;Diff[p[i].v]++;65        Diff[p[i].lca]-=2;66        cnt++;67    }68    Run(1,1,cnt,p[m].Val-t);69    if(Tag) return 1;70    else return 0;71}72int main(){73    memset(Depth,0,sizeof(Depth));74    memset(Head,0,sizeof(Head));75    memset(D,0,sizeof(D));76    scanf("%d%d",&n,&m);77    for(int i=1;i<=n-1;i++){78        scanf("%d%d%d",&In1,&In2,&In3);79        Edge_Add(In1,In2,In3); Edge_Add(In2,In1,In3);80    }81    D[1]=1;82    DFS(1,1);83    for(int i=1;i<=m;i++){84        scanf("%d%d",&p[i].u,&p[i].v);85        p[i].lca=LCA(p[i].u,p[i].v);86        p[i].Val=Depth[p[i].u]+Depth[p[i].v]-2*Depth[p[i].lca];87    }88    sort(p+1,p+m+1,cmp);89    int l=0,r=p[m].Val;90    while(l<r){91        int Mid=(l+r)>>1;92        if(Judge(Mid)) r=Mid;93        else l=Mid+1;94    }95    printf("%d",l);96    return 0;97}