题目
题目背景
公元 $2044$ 年,人类进入了宇宙纪元。
题目描述
公元$2044$ 年，人类进入了宇宙纪元。
L 国有 $n$ 个星球，还有 $n-1$ 条双向航道，每条航道建立在两个星球之间，这 $n-1$ 条航道连通了 $L$ 国的所有星球。
小 P 掌管一家物流公司， 该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 $u_i$ 号星球沿最快的宇航路径飞行到 $v_i$ 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 $j$，任意飞船驶过它所花费的时间为 $t_j$，并且任意两艘飞船之间不会产生任何干扰。
为了鼓励科技创新， $L$ 国国王同意小 $P$ 的物流公司参与 $L$ 国的航道建设，即允许小$P$ 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。
在虫洞的建设完成前小 P 的物流公司就预接了 $m$ 个运输计划。在虫洞建设完成后，这 $m$ 个运输计划会同时开始，所有飞船一起出发。当这 $m$ 个运输计划都完成时，小 $P$ 的物流公司的阶段性工作就完成了。
如果小 $P$ 可以自由选择将哪一条航道改造成虫洞， 试求出小 $P$ 的物流公司完成阶段性工作所需要的最短时间是多少？
输入输出格式
输入格式：
第一行包括两个正整数 $n, m$，表示 L 国中星球的数量及小 P 公司预接的运输计划的数量，星球从 $1$ 到 $n$ 编号。
接下来 $n-1$ 行描述航道的建设情况，其中第 $i$ 行包含三个整数 $a_i, b_i$ 和 $t_i$，表示第 $i$ 条双向航道修建在 $a_i$ 与 $b_i$ 两个星球之间，任意飞船驶过它所花费的时间为 $t_i$。数据保证 $1 \leq a_i,b_i \leq n$ 且 $0 \leq t_i \leq 1000$
接下来 $m$ 行描述运输计划的情况，其中第 $j$ 行包含两个正整数 $u_j$ 和 $v_j$，表示第 $j$ 个运输计划是从 $u_j$ 号星球飞往 $v_j$ 号星球。数据保证 $1 \leq u_i,v_i \leq n$
输出格式：
一个整数，表示小 $P$ 的物流公司完成阶段性工作所需要的最短时间。
输入输出样例
输入样例#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
说明
所有测试数据的范围和特点如下表所示
请注意常数因子带来的程序效率上的影响。
题解
发现答案具有单调性（答案越大影响答案的路径就越少），所以可以二分答案
如果某个计划的时间大于二分的答案，说明这个计划的某一条边肯定变成虫洞
所以变成虫洞的边要满足两个条件
- 所有时间大于二分答案的计划都经过ta
- ta的长度要尽量大
用倍增处理每个计划的$LCA$，枚举每个计划，看第$i$个计划是否长度大于二分答案
如果大于，用差分的思想，$s_i,p_i$标记+1,$LCA$处标记$-2$
再求个和就可以轻松判断某个边是否被所有满足条件的计划经过了qwq
代码
# include<iostream>
# include<cstdio>
# include<cstring>
# include<queue>
# include<stack>
using namespace std;
const int MAX=3e5+1;
struct p{
int x,y,dis;
}c[MAX<<1];
int n,m,num;
int h[MAX],pu[MAX],lca[MAX],deep[MAX],s[MAX],t[MAX],sum[MAX];
int f[MAX][21];
int read()
{
int x=0,ff=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-') ff=-1;
ch=getchar();
}
while(isdigit(ch)) x=x*10+ch-48,ch=getchar();
return x*ff;
}
void add(int x,int y,int dis)
{
c[++num]=(p){h[x],y,dis},h[x]=num;
c[++num]=(p){h[y],x,dis},h[y]=num;
}
void dfs(int x,int fa)
{
f[x][0]=fa,deep[x]=deep[fa]+1;
for(int i=h[x];i;i=c[i].x)
if(c[i].y!=fa) sum[c[i].y]=sum[x]+c[i].dis,dfs(c[i].y,x);
}
void init()
{
for(int i=1;i<=20;++i)
for(int j=1;j<=n;j++)
f[j][i]=f[f[j][i-1]][i-1];
}
int LCA(int x,int y)
{
if(deep[x]>deep[y]) swap(x,y);
int ff=deep[y]-deep[x];
for(int i=0;(1<<i)<=ff;++i)
if((1<<i)&ff) y=f[y][i];
if(x!=y)
{
for(int i=20;i>=0;i--)
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
x=f[x][0];
}
return x;
}
void dfs1(int x)
{
for(int i=h[x];i;i=c[i].x)
if(c[i].y!=f[x][0])
dfs1(c[i].y),pu[x]+=pu[c[i].y];
}
bool look(int mid)
{
memset(pu,0,sizeof(pu));
int tot=0,maxn=0,maxnn=0;
for(int i=1;i<=m;++i)
if(sum[s[i]]+sum[t[i]]-sum[lca[i]]*2>mid)
{
int h=sum[s[i]]+sum[t[i]]-sum[lca[i]]*2;
++tot,maxnn=max(maxnn,h),++pu[s[i]],++pu[t[i]],pu[lca[i]]-=2;
}
dfs1(1);
for(int i=2;i<=n;++i)
if(pu[i]>=tot&&sum[i]-sum[f[i][0]]>maxn) maxn=sum[i]-sum[f[i][0]];
if(maxnn-maxn<=mid) return 1;
return 0;
}
int main()
{
n=read(),m=read();
int l=0,r=0,ans;
for(int i=1;i<n;++i)
{
int x=read(),y=read(),dis=read();
add(x,y,dis),l=max(l,dis);
}
dfs(1,0),init();
for(int i=1;i<=m;++i)
s[i]=read(),t[i]=read(),lca[i]=LCA(s[i],t[i]),r=max(r,sum[s[i]]+sum[t[i]]-2*sum[lca[i]]);
l=r-l;
while(l<=r)
{
int mid=(l+r)>>1;
if(look(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
return printf("%d",ans),0;
}
