luogu P2680 运输计划

题面传送门 代码难度稍大，思路其实不难。 题目求最大最小，那么就是二分。 那么怎么验证呢。 首先预处理出所有航线的时间，然后跑出大于$mid$的航线，在树上差分。 只有每一条航线都经过的路径才可能满足要求，所以先找出这样的路径。 对于每一条边，我们都把权值放在下面的节点上，这样的话就可以直接跑一遍验证有没有符合要求的答案。 但是这道题要卡常。 首先用$unsigned$ $int$别用$long$ $long$，这样会快一倍。 然后缩小一下二分边界。 上界肯定是最长的路径减去权值最小的边。 下界肯定是最长的路径减去权值最大的边。 这样常数降了$3$倍。 时间复杂度$O(nlogt)$ 代码实现:

#include<cstdio> #include<cstring> #include<algorithm> #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) using namespace std; unsigned int ans,flag,n,m,k,l,r,mid,x,y,z,f[300039],q[300039],maxn,minn,w[300039]; unsigned int d[300039],top[300039],siz[300039],fa[300039],son[300039]; struct yyy{int to,w,z;}; struct ljb{ unsigned int head,h[300039]; yyy f[600039]; inline void add(unsigned int x,unsigned int y,unsigned int z){ f[++head]=(yyy){y,z,h[x]}; h[x]=head; } }s; struct sf{unsigned int l,r,lca,anss;}fs[300039]; inline bool cmp(sf x,sf y){return x.anss>y.anss;} inline void dfs1(unsigned int x,unsigned int last){ fa[x]=last; d[x]=d[last]+1; siz[x]=1; unsigned int cur=s.h[x],pus=0; yyy tmp; while(cur){ tmp=s.f[cur]; if(tmp.to!=last) { dfs1(tmp.to,x); siz[x]+=siz[tmp.to]; if(siz[tmp.to]>pus) son[x]=tmp.to,pus=siz[tmp.to]; } cur=tmp.z; } } inline void dfs2(unsigned int x,unsigned int last){ top[x]=last; unsigned int cur=s.h[x]; yyy tmp; q[x]=q[fa[x]]+w[x]; while(cur){ tmp=s.f[cur]; if(tmp.to==son[x])w[tmp.to]=tmp.w,dfs2(tmp.to,last); cur=tmp.z; } cur=s.h[x]; while(cur){ tmp=s.f[cur]; if(tmp.to!=son[x]&&tmp.to!=fa[x]) w[tmp.to]=tmp.w,dfs2(tmp.to,tmp.to); cur=tmp.z; } } inline void swap(unsigned int &x,unsigned int &y){x^=y,y^=x,x^=y;} inline unsigned int lca(unsigned int x,unsigned int y){ while(top[x]!=top[y]){ if(d[top[x]]<d[top[y]]) swap(x,y); x=fa[top[x]]; } if(d[x]>d[y]) swap(x,y); return x; } inline void dfs(unsigned int x,unsigned int last){ unsigned int cur=s.h[x]; yyy tmp; while(cur){ tmp=s.f[cur]; if(tmp.to!=last) dfs(tmp.to,x),f[x]+=f[tmp.to]; cur=tmp.z; } } int main(){ register unsigned int i; scanf("%u%u",&n,&m); for(i=1;i<n;i++) scanf("%u%u%u",&x,&y,&z),s.add(x,y,z),s.add(y,x,z),maxn=max(z,maxn); dfs1(1,0); dfs2(1,1); for(i=1;i<=m;i++){ scanf("%u%u",&fs[i].l,&fs[i].r); fs[i].lca=lca(fs[i].l,fs[i].r); fs[i].anss=q[fs[i].l]+q[fs[i].r]-2*q[fs[i].lca]; //printf("%u\n",fs[i].anss); } sort(fs+1,fs+m+1,cmp); l=fs[1].anss-maxn-1;r=fs[1].anss-minn; while(l+1<r){ mid=(l+r)>>1; ans=flag=0; memset(f,0,sizeof(f)); for(i=1;i<=n;i++){ if(fs[i].anss<=mid)break; ans=i; f[fs[i].l]++; f[fs[i].r]++; f[fs[i].lca]-=2; } dfs(1,0); for(i=1;i<=n;i++) if(f[i]==ans&&fs[1].anss-w[i]<=mid){flag=1;break;} //printf("%d %d %d\n",flag,l,r); if(flag) r=mid; else l=mid; } printf("%u\n",r); }