luogu P2680 運輸計劃

題面傳送門

代碼難度稍大，思路其實不難。

題目求最大最小，那麼就是二分。

那麼怎麼驗證呢。

首先預處理出所有航線的時間，然後跑出大于 m i d mid mid的航線，在樹上差分。

隻有每一條航線都經過的路徑才可能滿足要求，是以先找出這樣的路徑。

對于每一條邊，我們都把權值放在下面的節點上，這樣的話就可以直接跑一遍驗證有沒有符合要求的答案。

但是這道題要卡常。

首先用 u n s i g n e d unsigned unsigned i n t int int别用 l o n g long long l o n g long long，這樣會快一倍。

然後縮小一下二分邊界。

上界肯定是最長的路徑減去權值最小的邊。

下界肯定是最長的路徑減去權值最大的邊。

這樣常數降了 3 3 3倍。

時間複雜度 O ( n l o g t ) O(nlogt) 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);
}