运输计划

公元20442044 年，人类进入了宇宙纪元。

L 国有 nn 个星球，还有 n-1n−1 条双向航道，每条航道建立在两个星球之间，这 n-1n−1 条航道连通了 LL 国的所有星球。

小 P 掌管一家物流公司， 该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 u_iui 号星球沿最快的宇航路径飞行到 v_ivi 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 jj，任意飞船驶过它所花费的时间为 t_jtj，并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新， LL 国国王同意小 PP 的物流公司参与 LL 国的航道建设，即允许小PP 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 mm 个运输计划。在虫洞建设完成后，这 mm 个运输计划会同时开始，所有飞船一起出发。当这 mm 个运输计划都完成时，小 PP 的物流公司的阶段性工作就完成了。

如果小 PP 可以自由选择将哪一条航道改造成虫洞， 试求出小 PP 的物流公司完成阶段性工作所需要的最短时间是多少？

有n个点，n-1条边的连通图，这必然是一棵树。

注意到所有运输计划是同时开始的，这意味着我们需要使这些运输计划需要的时间的最大值最小。看到这个问题的形式，容易联想到二分答案。

明显的，这个问题具有单调性，满足二分条件。因为如果时间可以是t，那么一定可以是大于t，如果时间不能是t，一定不能是小于t。

再来考虑判断函数的设计。我们需要判断时间为t时，所有运输计划是否可以完成。最朴素的方法是枚举每条航道通过的所有边，删掉之后再跑一次所有航道，看是否可行。

但是有一个明显的优化，即考虑删掉一条边对我们的收益，明显的，它被覆盖的次数越多，以及它越长，那么把它删掉我们的收益越大。但是不能直接贪心，因为这样只能让和最小，而不能让最大值最小。此时二分的优势就体现出来了，我们只用判断可不可行，而不用得到最优解。所以我们可以把路径长度大于t的单独拿出来考虑。

如果不存在路径长度大于t的路径，则一定可行。

如果所有路径长度大于t的路径没有一个公共边，则一定不可行。因为我们只能删掉一条边。如果它们没有一个公共边，则删完之后一定还存在长度大于t的路径。

如果存在公共边，我们取这些边中长度最大的，删掉。（前面讨论过，这种删法对我们最有利）。再考虑大于t的路径中长度最大的再删完这条边后是否合法，若合法，则方案合法，若不合法，则方案不合法。

算法大致已经设计完成，我们来看看其中具体的实现细节。

对于路径求交，我们可以使用树上差分来实现。

对于路径求长度，可以使用LCA来实现。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 300050;
int n,m;
int sumw;
int x,y,c;

struct edge{
	int v,w;
	edge(int a=0,int b=0){
		v=a;w=b;
	}
};
int dep[maxn];
int f[maxn][24];
vector <edge> g[maxn];
int d[maxn];
int cf[maxn];
int num[maxn];
int numm;
int dr[maxn];
int le,ri;
struct lian{
	int u,v;
	int dis,root;
	lian(int a=0,int b=0,int c=0,int d=0){
		u=a;v=b;dis=d;root=c;
	}
};
lian l[maxn];

void dfs(int u,int fa){
	//这里求一下dfs序 
	numm++;
	num[numm]=u;  //这里 
	//这里求一下深度 
	dep[u] = dep[fa] + 1;
	//以下为标准lca预处理 
	for (int i=0;i<=22;i++){
		f[u][i+1] = f[f[u][i]][i];
	}
	for (int i=0;i<g[u].size();i++){
		if(fa==g[u][i].v)continue;
		//这里一行代码求到根距离 
		dr[g[u][i].v]=dr[u]+g[u][i].w;
		f[g[u][i].v][0] = u;
		dfs(g[u][i].v,u);
	}
}

int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for (int i=23;i>=0;i--){
		if(dep[f[x][i]]>=dep[y])x = f[x][i];
		if(x==y)return x;
	}
	for (int i=23;i>=0;i--){
		if(f[x][i]!=f[y][i]){
	        x = f[x][i];y = f[y][i];
		}
	}
	return f[x][0];
}


bool jg(int t){
	int cnt=0;int ans=0;
	memset(cf,0,sizeof(cf));
	for (int i=1;i<=m;i++){
	    if(l[i].dis>t){
	 		cf[l[i].u]+=1;
	 		cf[l[i].v]+=1;
	 		cf[l[i].root]-=2;
	 		cnt++;
	 		ans = max(ans,l[i].dis-t);
		}
	}
	if(cnt==0)return true;
	for (int i=n;i>=1;i--)
	cf[f[num[i]][0]]+=cf[num[i]];
	//注意这里是2
	for (int i=2;i<=n;i++)
	if(cf[i]==cnt&&dr[i]-dr[f[i][0]]>=ans)return true;
	return false;
}

int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n-1;i++){
		scanf("%d%d%d",&x,&y,&c);
		g[x].push_back(edge(y,c));
		g[y].push_back(edge(x,c));
		sumw += c;
	}
	dfs(1,0);
    for (int i=1;i<=m;i++){
    	scanf("%d%d",&x,&y);
    	l[i] = lian(x,y,lca(x,y),dr[x]+dr[y]-2*dr[lca(x,y)]);
	}
	
	le=0;ri=sumw+1;
	while (le<ri){
		int mid = (le+ri)>>1;
		if(jg(mid))ri=mid;
		else le=mid+1;
	}
	printf("%d",le);
	
	return 0;
}