本文共 3396 字，大约阅读时间需要 11 分钟。

题目背景

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

题目描述

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

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

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

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

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

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

输入格式

第一行包括两个正整数 n, mn,m，表示 L 国中星球的数量及小 P 公司预接的运输计划的数量，星球从 11 到 nn 编号。

接下来 n-1n−1 行描述航道的建设情况，其中第 ii 行包含三个整数 a_i, b_ia

i ​ ,b i ​ 和 t_it i ​ ，表示第 ii 条双向航道修建在 a_ia i ​ 与 b_ib i ​ 两个星球之间，任意飞船驶过它所花费的时间为 t_it i ​ 。数据保证 1 \leq a_i,b_i \leq n1≤a i ​ ,b i ​ ≤n 且 0 \leq t_i \leq 10000≤t i ​ ≤1000。

接下来 mm 行描述运输计划的情况，其中第 jj 行包含两个正整数 u_ju

j ​ 和 v_jv j ​ ，表示第 jj 个运输计划是从 u_ju j ​ 号星球飞往 v_jv j ​ 号星球。数据保证 1 \leq u_i,v_i \leq n1≤u i ​ ,v i ​ ≤n

输出格式

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

输入输出样例

输入 #1 复制 6 3 1 2 3 1 6 4 3 1 7 4 3 6 3 5 5 3 6 2 5 4 5 输出 #1 复制 11 说明/提示 所有测试数据的范围和特点如下表所示 求所有边最大值的最小化。这种题一看就是二分。 关于边的差分（如找被所有路径共同覆盖的边 首先我们除了一般的grand，depth等数组以外，多开两个数组：tmp和prev。

tmp用来记录点的出现次数（具体点说实际上记录的是点到其父亲的边的出现次数），prev记录每个点到其父亲的那条边。对于一条起点s，终点t的路径。我们这样处理：

tmp[s]++,tmp[t]++,tmp[LCA(s,t)]-=2。（记住：最后要从所有叶结点把权值向上累加。）以一次操作为例，我们来看看效果（可以画一张图）。首先tmp[s]++，一直推上去到根，这时候s到root的路径访问次数都+1，tmp[t]++后，t到lca路径加了1，s到lca路径加了1，而lca到根的路径加了2。

这时，我们只需要tmp[LCA(s,t)]-=2，推到根，就能把那些多余的路径减掉，达到想要的目的。而这是一次操作，对于很多次操作的话，我们只需要维护tmp，而不必每次更新到根，维护好tmp最后Dfs一遍即可。这时如果tmp[i]==次数的话，说明i到其父亲的边是被所有路径覆盖的。如图

代码如下：

#include
   
    #define ll long longusing namespace std;const int maxx=3e5+100;struct node{
   	int x,y,lca;}b[maxx];struct edge{
   	int to,next,val;}e[maxx<<1];int head[maxx<<1],temp[maxx],deep[maxx],dp[maxx][26],pre[maxx];ll dis[maxx];int n,m,tot,flag;/*--------------事前准备----------------*/inline void add(int u,int v,int w){
   	e[tot].to=v,e[tot].next=head[u],e[tot].val=w,head[u]=tot++;}inline void init(){
   	for(int i=0;i<=n;i++)	{
   		for(int j=0;j<=25;j++) dp[i][j]=0;	}	memset(head,-1,sizeof(head));	tot=0;}/*-----------dfs-----------*/inline void dfs(int u,int f){
   	deep[u]=deep[f]+1;	dp[u][0]=f;	for(int i=1;i<=25;i++)	{
   		if(dp[u][i-1]) dp[u][i]=dp[dp[u][i-1]][i-1];		else break;	}	for(int i=head[u];i!=-1;i=e[i].next)	{
   		int to=e[i].to,w=e[i].val;		if(to==f) continue;		dis[to]=dis[u]+w;		pre[to]=w;		dfs(to,u);	}}inline int dfs2(int u,int f,int cnt,ll maxn){
   	int num=temp[u];	for(int i=head[u];i!=-1;i=e[i].next)	{
   		int to=e[i].to;		if(to==f) continue;		num+=dfs2(to,u,cnt,maxn);	}	if(num>=cnt&&pre[u]>=maxn) flag=1;	return num;}/*-----------lca------------*/inline int get_lca(int x,int y){
   	if(deep[x]
    
     =0;i--)	{
   		if(dp[x][i]!=dp[y][i])		{
   			x=dp[x][i];			y=dp[y][i];		}	}	return dp[x][0];}/*--------------二分-------------*/inline int check(ll x)//二分找出大于这个值的边的条数和最大差值{
   	ll sum;int cnt=0;ll maxn=0;	memset(temp,0,sizeof(temp));	for(int i=1;i<=m;i++)	{
   		sum=dis[b[i].x]+dis[b[i].y]-2*dis[b[i].lca];		if(sum>x)		{
   			cnt++;			temp[b[i].x]++,temp[b[i].y]++,temp[b[i].lca]-=2;			maxn=max(maxn,sum-x);		}	}	if(cnt==0) return 1;	flag=0;	dfs2(1,0,cnt,maxn);	return flag;}int main(){
   	int x,y,w;ll sum,mid;		scanf("%d%d",&n,&m);		sum=0;		init();		for(int i=1;i
     
      >1;			if(check(mid))			{
   				ans=mid;				r=mid-1;			}			else l=mid+1; 		}		printf("%lld\n",ans);	return 0;}
     
    
   

努力加油a啊，(^o)/~

转载地址：http://mztvi.baihongyu.com/