[luogu2680] 运输计划 (lca+二分+树上差分)

传送门

Description

Input

Output

一个整数，表示小 P 的物流公司完成阶段性工作所需要的最短时间。

Sample Input

6 3

1 2 3

1 6 4

3 1 7

4 3 6

3 5 5

3 6

2 5

4 5

Sample Output

HINT

Solution

很显然第一步是求出lca然后求出每个运输计划的长度

题目要求一个时间最大值的最小值很明显要二分

二分一个运输时间，统计所有超过这个时间的运输计划经过的路径

找出其中被所有超时计划包括的最大路径直接判断就行

lca和长度我用的tarjan

统计每条路径的经过次数那就树上差分喽(￣▽￣)／

Code

//By Menteur_Hxy

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define M(a,b) memset(a,(b),sizeof(a))

#define F(i,a,b) for(register int i=(a);i<=(b);i++)

#define E(i,u) for(register int i=head[u];i;i=nxt[i])

using namespace std;

int read() {

	int x=0,f=1; char c=getchar();

	while(!isdigit(c)) {if(c=='-')f=-f; c=getchar();}

	while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();

	return x*f;

}

const int N=300010;

bool vis[N];

int n,m,ecnt,maxlen,res,num;

int nxt[N<<1],to[N<<1],w[N<<1],head[N],ln[N],rn[N],len[N],lca[N],dis[N],fa[N],sum[N],cnt[N];

vector <int> V[N];

int getf(int x) {return fa[x]==x?x:fa[x]=getf(fa[x]);}

void tarjan(int u,int pre) {

	E(i,u) { int v=to[i];

		if(v==pre) continue;

		dis[v]=dis[u]+w[i];

		tarjan(v,u);

		cnt[v]=w[i];//差分时用

	}

	int siz=V[u].size();

	F(i,0,siz-1) {

		int id=V[u][i],v=ln[id]==u?rn[id]:ln[id];

		if(!vis[v]) continue;

		lca[id]=getf(v);

		len[id]=dis[v]+dis[u]-2*dis[lca[id]];

		maxlen=max(len[id],maxlen);

	}

	vis[u]=1;fa[u]=pre;

}

void dfs(int u,int pre) {

	E(i,u) { int v=to[i];

		if(v==pre) continue;

		dfs(v,u);

		sum[u]+=sum[v];

	}

	if(sum[u]==num&&cnt[u]>res) res=cnt[u];

}

bool jud(int t) {

	num=res=0;

	M(sum,0);

	F(i,1,m) if(len[i]>t) sum[ln[i]]++,sum[rn[i]]++,sum[lca[i]]-=2,num++;

	if(num==0) return 1;

	dfs(1,0);

	return maxlen-res<=t;

}

#define add(a,b,c) nxt[++ecnt]=head[a],to[ecnt]=b,head[a]=ecnt,w[ecnt]=c

#define ins(a,b,c) add(a,b,c),add(b,a,c)

int main() {

	n=read(),m=read();

	F(i,1,n) fa[i]=i;

	F(i,1,n-1) {

		int a=read(),b=read(),c=read();

		ins(a,b,c);

	}

	F(i,1,m) {

		int a=read(),b=read();

		ln[i]=a,rn[i]=b;

		V[a].push_back(i);

		V[b].push_back(i);

	}

	tarjan(1,0);

//	F(i,1,m) cout<<lca[i]<<" "<<len[i]<<endl;

	int l=0,r=maxlen;

	int ans=0x3f3f3f3f;

	while(l<=r) {

		int mid=(l+r)>>1;

		if(jud(mid)) ans=min(ans,mid),r=mid-1;

		else l=mid+1;

	}

	printf("%d",ans);

	return 0;

}

巴特西