题目背景
公元 2044 年,人类进入了宇宙纪元。 题目描述
L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。
小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物
流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道 是需要时间的,对于航道
j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之 间不会产生任何干扰。为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小 P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。
在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后, 这 m 个运输计划会同时开始,所有飞船一起出发。当这 m
个运输计划都完成时,小 P 的 物流公司的阶段性工作就完成了。如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段 性工作所需要的最短时间是多少?
首先可以二分答案，对于每一个时间，找到所有用时超过他的【也就是需要使用虫洞的】路径，然后只要检查是否有一条边被这些所有路径都覆盖且长度不小于需要的长度【需要的长度即为最长路径减去二分的时间】。
检查的另一个做法见【这里】。
找到这些路径中最低的【深度最深的】LCA记为x，然后检查是否所有路径都至少有一个端点在x的子树里，如果有一条路径没有，那么这条路径和以x为LCA的这条路径一定没有公共边。否则的话，按只有一个端点在和两个端点都在【这样的话他的LCA就是x】分类记录。对于只有一个端点在的路径只有一种取法，两个端点都在的路径可以验证一下取哪个端点会使新LCA 尽可能低。求出这些所有端点的LCA记为y，那么所有路径的重叠部分就是y->x。再求路径上最长边即可。如果没有只有一个端点在子树里的路径，只需要枚举第一个路径取哪个点，后面照常。
检查每个询问是否有端点在子树里和求这些点的LCA都是O(mlogn)的，所以总的时间复杂度是O(mlog(nl)logn)。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mx=20;
int n,m,p[300010][2],fir[300010],to[600010],len[600010],ne[600010],anc[300010][23],
dis[300010][23],maxlen[300010][23],ans[300010],anslca[300010],dep[300010],
g[300010][2],f[300010];
bool flag[300010];
int rd()
{int x=0;char c=getchar();while (c<'0'||c>'9') c=getchar();while (c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x;
}
void add(int num,int u,int v,int l)
{ne[num]=fir[u];fir[u]=num;to[num]=v;len[num]=l;
}
void init()
{int i,x,y,z;n=rd();m=rd();for (i=1;i<n;i++){x=rd();y=rd();z=rd();add(i*2,x,y,z);add(i*2+1,y,x,z);}for (i=1;i<=m;i++){p[i][0]=rd();p[i][1]=rd();}
}
void dfs(int u,int fa)
{int i,v;for (i=fir[u];i;i=ne[i])if ((v=to[i])!=fa){dep[v]=dep[u]+1;anc[v][0]=u;dis[v][0]=maxlen[v][0]=len[i];dfs(v,u);}
}
void pre()
{int i,j,k,u,v;dep[1]=1;dfs(1,-1);for (k=1;k<=mx;k++)for (i=1;i<=n;i++){anc[i][k]=anc[anc[i][k-1]][k-1];dis[i][k]=dis[i][k-1]+dis[anc[i][k-1]][k-1];maxlen[i][k]=max(maxlen[i][k-1],maxlen[anc[i][k-1]][k-1]);}for (i=1;i<=m;i++){u=p[i][0];v=p[i][1];if (dep[u]<dep[v]) swap(u,v);for (k=mx;k>=0;k--)if (dep[u]-(1<<k)>=dep[v]){ans[i]+=dis[u][k];u=anc[u][k];}if (u==v){anslca[i]=u;continue;}for (k=mx;k>=0;k--)if (anc[u][k]!=anc[v][k]){ans[i]+=dis[u][k]+dis[v][k];u=anc[u][k];v=anc[v][k];}ans[i]+=dis[u][0]+dis[v][0];anslca[i]=anc[u][0];}
}
int lca(int u,int v)
{int k,i;if (dep[u]<dep[v]) swap(u,v);for (k=mx;k>=0;k--)if (dep[u]-(1<<k)>=dep[v])u=anc[u][k];if (u==v) return u;for (k=mx;k>=0;k--)if (anc[u][k]!=anc[v][k]){u=anc[u][k];v=anc[v][k];}return anc[u][0];
}
bool ok(int x)
{int i,j,k,u,v,totf=0,totg=0,lowest=-1,lca1,temp,need=0;for (i=1;i<=m;i++)if (ans[i]>x){need=max(need,ans[i]-x);flag[i]=1;if (lowest==-1||dep[anslca[i]]>dep[lowest])lowest=anslca[i];}else flag[i]=0;for (i=1;i<=m;i++)if (flag[i]){if (anslca[i]==lowest){totg++;g[totg][0]=p[i][0];g[totg][1]=p[i][1];}else{if (lca(lowest,p[i][0])==lowest) f[++totf]=p[i][0];else{if (lca(lowest,p[i][1])==lowest) f[++totf]=p[i][1];else return 0;}}}if (totf){lca1=f[1];for (i=2;i<=totf;i++)lca1=lca(lca1,f[i]);for (i=1;i<=totg;i++){u=lca(lca1,g[i][0]);v=lca(lca1,g[i][1]);if (dep[u]<dep[v]) lca1=v;else lca1=u;}temp=0;for (k=mx;k>=0;k--)if (dep[lca1]-(1<<k)>=dep[lowest]){temp=max(temp,maxlen[lca1][k]);lca1=anc[lca1][k];}return temp>=need;}else{lca1=g[1][0];for (i=2;i<=totg;i++){u=lca(lca1,g[i][0]);v=lca(lca1,g[i][1]);if (dep[u]<dep[v]) lca1=v;else lca1=u;}temp=0;for (k=mx;k>=0;k--)if (dep[lca1]-(1<<k)>=dep[lowest]){temp=max(temp,maxlen[lca1][k]);lca1=anc[lca1][k];}if (temp>=need) return 1;lca1=g[1][1];for (i=2;i<=totg;i++){u=lca(lca1,g[i][0]);v=lca(lca1,g[i][1]);if (dep[u]<dep[v]) lca1=v;else lca1=u;}temp=0;for (k=mx;k>=0;k--)if (dep[lca1]-(1<<k)>=dep[lowest]){temp=max(temp,maxlen[lca1][k]);lca1=anc[lca1][k];}if (temp>=need) return 1;}return 0;
}
void solve()
{int i,temp,l,r,mid;temp=0;for (i=1;i<=m;i++)temp=max(temp,ans[i]);l=0;r=temp;while (l<r){mid=(l+r)/2;if (ok(mid)) r=mid;else l=mid+1;}printf("%d\n",l);
}
int main()
{init();pre();solve();
}