題目描述
資料範圍
算法思路
這一題我們可以先二分出一個答案，即改造蟲洞了之後起點到終點的最大距離的最小值。
然後進行差分，最後在周遊一遍每條邊，隻要删掉随便一條邊最大值在在答案之内，這個答案就成立。
優化算法
1、我們可以存一個Dfs序，這樣在計算差分是就可以直接按照Dfs序從後往前計算，這樣可以不用再寫一個Dfs，可以加快一點時間，使你的程式順利卡過測試點
2、求Lca的時候最好用Tajan的離線或樹剖（比Tajan快很多，但本人是蒟蒻不會樹剖）否則會被T掉。
時間分析
Tajan算法為Θ(n)，二分時間複雜度是Θ(log(maxfar))（maxfar為題目詢問的兩點距離的最大值），判斷時間複雜度是Θ(n+m)的
代碼
#include<bits/stdc++.h>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
inline int read()
{
int ans=0,y=1;char c=getchar();
while((c<'0'||c>'9')&&(c!='-'))c=getchar();
if(c=='-')y=-1,c=getchar();
else ans=c-'0',c=getchar();
while(c>='0'&&c<='9')ans=ans*10+c-'0',c=getchar();
return ans*y;
}
struct node{int Next,to,val;}edge[600005],ed[600005];
int Head[300005],head[300005],dep[300005],dis[300005],cnt=0,cnt1=0;
int cf[300005],tofa[300005],dfn[300005],dfncnt,fa[300005];
bool vis[300005];
int find(int x)
{
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
void add(int u,int v,int val)
{
++cnt;
edge[cnt].Next=Head[u];
edge[cnt].to=v;
edge[cnt].val=val;
Head[u]=cnt;
}
void Add(int u,int v,int num)
{
ed[++cnt1].to=v;
ed[cnt1].Next=head[u];
ed[cnt1].val=num;
head[u]=cnt1;
}
int n,m,x[300005],y[300005],z[300005],far[300005],father[300005];
void dfs(int x,int f)//處理出dfs序，以及樹的一些奇奇怪怪的東西，外加求Lca
{
dfn[++dfncnt]=x;dep[x]=dep[f]+1;
father[x]=f;
for(int i=Head[x];i;i=edge[i].Next)
if(edge[i].to!=f)
{
dis[edge[i].to]=dis[x]+edge[i].val;
tofa[edge[i].to]=edge[i].val;
dfs(edge[i].to,x);
}
vis[x]=true;
for(int i=head[x];i;i=ed[i].Next)
{
int v=ed[i].to;
if(vis[v])z[ed[i].val]=find(v);
}
fa[x]=f;
}
inline int check(int mid,int ax)//差分
{
memset(cf,0,sizeof(cf));
int k=0;
for(int i=1;i<=m;i++)
if(far[i]>mid)cf[x[i]]++,cf[y[i]]++,cf[z[i]]-=2,k++;
for(int i=n;i;i--)cf[father[dfn[i]]]+=cf[dfn[i]];
for(int i=1;i<=n;i++)
if(cf[i]==k&&ax-tofa[i]<=mid)return 1;
return 0;
}
int main()
{
fre(transport);
n=read(),m=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read(),val=read();
add(u,v,val),add(v,u,val);
fa[i]=i;
}fa[n]=n;
for(int i=1;i<=m;i++)
{
x[i]=read(),y[i]=read();
Add(x[i],y[i],i),Add(y[i],x[i],i);
}
dfs(1,0);int ax=0;
for(int i=1;i<=m;i++)
{
far[i]=dis[x[i]]+dis[y[i]]-2*dis[z[i]];
ax=max(ax,far[i]);
}
int l=0,r=ax,ans=0;
while(l<=r)//二分答案
{
int mid=(l+r)>>1;
if(check(mid,ax))r=mid-1,ans=mid;
else l=mid+1;
}
printf("%d",ans);
return 0;
}