题解 P2680 【运输计划】

对于这道题，我们先通过倍增Lca求出每条路径所用的时间。然后进行二分答案。 对于当前二分到的最短时间k，和m条路径的时间花费进行比较，对于时间比k大的路径，我们把这条路径差分一下（树上差分见博客），并记录下比k大的路径的条数cnt和这些路径的最大值max。 接下来枚举每一条边，通过差分求出这条边被比k大的路径覆盖的次数。如果这条边被覆盖了cnt次，并且max-val<=k（val为这条边的时间花费），这就表明，去掉这条边的值，就可以让所有cnt条比k大的边都能在k的时间内完成任务。 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; inline int readn() { int x=0; char ch=getchar(); while(ch>'9'||ch<'0') ch=getchar(); while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x; } int n,m,cnt=0,Max; int head[1001000],nxt[1001000],to[1001000],val[1001000]; int d[1001000],f[25][1001000],dis[1001000],num[1001000]; int p[1001000]; struct road { int a,b,l,dis; }r[301000]; void addedge(int x,int y,int z) { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; val[cnt]=z; } void dfs(int u,int dep) { d[u]=dep,p[++cnt]=u; for(int i=head[u];i!=-1;i=nxt[i]) { int v=to[i]; if(!d[v]) f[0][v]=u,dis[v]=dis[u]+val[i],dfs(v,dep+1); } } int Lca(int x,int y) { if(d[x]<d[y]) swap(x,y); for(int i=20;i>=0;i--) if(d[f[i][x]]>=d[y]) x=f[i][x]; if(x==y) return x; for(int i=20;i>=0;i--) if(f[i][x]!=f[i][y]) { x=f[i][x]; y=f[i][y]; } return f[0][x]; } bool check(int k) { memset(num,0,sizeof(num)); cnt=0; for(int i=1;i<=m;i++) if(r[i].dis>k) num[r[i].a]++,num[r[i].b]++,num[r[i].l]-=2,cnt++; for(int i=n;i>=1;i--) { num[f[0][p[i]]]+=num[p[i]]; if(dis[p[i]]-dis[f[0][p[i]]]>=Max-k && num[p[i]]==cnt) return 1; } return 0; } int main() { memset(head,-1,sizeof(head)); n=readn(); m=readn(); for(int i=1;i<n;i++) { int x,y,z; x=readn();y=readn();z=readn(); addedge(x,y,z); addedge(y,x,z); } f[0][1]=0; cnt=0; dfs(1,1); for(int i=1;i<=23;i++) for(int j=1;j<=n;j++) f[i][j]=f[i-1][f[i-1][j]]; int L=0,R=0; for(int i=1;i<=m;i++) { r[i].a=readn();r[i].b=readn(); r[i].l=Lca(r[i].a,r[i].b); r[i].dis=dis[r[i].a]+dis[r[i].b]-2*dis[r[i].l]; R=max(R,r[i].dis); } Max=R; while(L<R) { int mid=(L+R)/2; if(check(mid)) R=mid; else L=mid+1; } printf("%d",L); return 0; } ```