题目背景
公元 2044 年,人类进入了宇宙纪元。
题目描述
L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。
小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物
流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道 是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之 间不会产生任何干扰。
为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小 P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。
在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后, 这 m 个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的 物流公司的阶段性工作就完成了。
如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段 性工作所需要的最短时间是多少?
输入输出格式
输入格式：
输入文件名为 transport.in。
第一行包括两个正整数 n、m,表示 L 国中星球的数量及小 P 公司预接的运输计划的数量,星球从 1 到 n 编号。
接下来 n-1 行描述航道的建设情况,其中第 i 行包含三个整数 ai, bi 和 ti,表示第
i 条双向航道修建在 ai 与 bi 两个星球之间,任意飞船驶过它所花费的时间为 ti。
接下来 m 行描述运输计划的情况,其中第 j 行包含两个正整数 uj 和 vj,表示第 j个 运输计划是从 uj 号星球飞往 vj 号星球。
输出格式：
输出 共1行,包含1个整数,表示小P的物流公司完成阶段性工作所需要的最短时间。
输入输出样例
6 3
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5
11
说明
所有测试数据的范围和特点如下表所示
请注意常数因子带来的程序效率上的影响。
三模wzx大佬
解法见此大佬博客
orz wzx
orz wzx
orz wzx
#include <ctype.h>
#include <cstring>
#include <cstdio>
#define M 300005 void read(int &x)
{
x=;bool f=;
register char ch=getchar();
for(; !isdigit(ch); ch=getchar()) if(ch=='-') f=;
for(; isdigit(ch); ch=getchar()) x=(x<<)+(x<<)+ch-'';
x=f?(~x)+:x;
}
int Mcost,dis[M],cost[M],n,m,top[M],cnt,pos[M],head[M],tim,siz[M],fa[M],dep[M];
struct Edge
{
int next,to,dis;
Edge (int next=,int to=,int dis=) : next(next),to(to),dis(dis) {}
}edge[M<<];
struct P
{
int u,v,lca,cost;
P (int u=,int v=,int lca=,int cost=) : u(u),v(v),lca(lca),cost(cost) {}
}p[M<<];
void ins(int u,int v,int w)
{
edge[++cnt]=Edge(head[u],v,w);
head[u]=cnt;
}
void dfs1(int x)
{
dep[x]=dep[fa[x]]+;
siz[x]=;
for(int u=head[x];u;u=edge[u].next)
{
int v=edge[u].to;
if(fa[x]!=v)
{
dis[v]=dis[x]+edge[u].dis;
fa[v]=x;
dfs1(v);
siz[x]+=siz[v];
}
}
}
void dfs2(int x)
{
if(!top[x]) top[x]=x;
pos[x]=++tim;
int p=;
for(int u=head[x];u;u=edge[u].next)
{
int v=edge[u].to ;
if(fa[x]!=v&&siz[v]>siz[p]) p=v;
}
if(p) {top[p]=top[x];dfs2(p);}
for(int u=head[x];u;u=edge[u].next)
{
int v=edge[u].to;
if(fa[x]!=v&&v!=p) dfs2(v);
}
}
void swap(int &x,int &y)
{
int tmp=y;
y=x;
x=tmp;
}
int getlca(int x,int y)
{
for(;top[x]!=top[y];x=fa[top[x]])
if(dep[top[x]]<dep[top[y]]) swap(x,y);
return dep[x]<dep[y]?x:y;
}
int max(int a,int b) {return a>b?a:b;}
void dfs3(int x)
{
for(int u=head[x];u;u=edge[u].next)
{
int v=edge[u].to;
if(fa[x]!=v)
{
dfs3(v);
cost[x]+=cost[v];
}
}
}
bool check(int k)
{
memset(cost,,sizeof(cost));
int num=;
for(int i=;i<=m;i++)
{
if(p[i].cost>k)
{
num++;
cost[p[i].u]++;
cost[p[i].v]++;
cost[p[i].lca]-=;
}
}
dfs3();
for(int i=;i<=n;i++) if(cost[i]==num&&dis[i]-dis[fa[i]]>=Mcost-k) return true;
return false;
}
int main()
{
read(n);
read(m);
for(int x,y,z,i=;i<n;i++)
{
read(x);
read(y);
read(z);
ins(x,y,z);
ins(y,x,z);
}
dfs1();dfs2();
for(int x,y,i=;i<=m;i++)
{
read(x);read(y);
int Lca=getlca(x,y);
int cos=dis[x]+dis[y]-dis[Lca]*;
p[i]=P(x,y,Lca,cos);
Mcost=max(Mcost,cos);
}
int ans,l=,r=Mcost+;
for(;l<=r;)
{
int mid=(l+r)>>;
if(check(mid))
{
r=mid-;
ans=mid;
}
else l=mid+;
}
printf("%d\n",ans);
return ;
}