首先题目要求最大的最小，我们二分答案，对于每个答案，我们筛出比它长的路径，找到它们最长的公共边，删掉后验证正确性即可。找公共边可以用树上差分来做，时间复杂度 \(O(m\log n\log V)\)，其中 \(V\) 是二分区间大小。
你会发现你挂了一堆点，让我们来卡常：
- 首先预处理出所有节点的 \(dfn\)，每一次找公共边的时候按照 \(dfn\) 从大到小向父亲加上差分数组；
- 其次对于二分边界的 \(l\) 不会超出没有虫洞时的 \(1000\)。
- 最后可以提前算出来每一个运输计划没有虫洞时的距离，这样可以省下很多常数。
点击查看代码
#include<bits/stdc++.h>
#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define inn(i,n,a) For(i,1,n) a[i]=read();
#define ll long long
#define i128 __int128
using namespace std;
inline int read() {
int xx= 0;int f= 1;
char c = getchar();
while(c<'0'||c>'9') {
if(c=='-') f= -1;
c= getchar();
}
while(c>='0'&&c<='9') {
xx= (xx<<1)+(xx<<3)+(c^48);
c= getchar();
}
return xx*f;
}
#define maxn 300050
int n,m;
struct node {
int u,w;
};
vector<node>G[maxn];
struct noddde{
int st,ed,d;
}qwq[maxn];
int dis[maxn];
int fa[maxn][26],dep[maxn];
int lg2(int x) {
int res=0;
if(x&0xffff0000) res+=16,x>>=16;
if(x&0x0000ff00) res+=8,x>>=8;
if(x&0x000000f0) res+=4,x>>=4;
if(x&0x0000000c) res+=2,x>>=2;
if(x&0x00000002) res+=1,x>>=1;
return res;
}
int dfn[maxn],todfn[maxn],dfncnt;
void dfs1(int u,int fath) {
dep[u]=dep[fath]+1;
fa[u][0]=fath;
dfn[u]=++dfncnt;
todfn[dfncnt]=u;
int k=lg2(dep[u]);
For(i,1,k) fa[u][i]=fa[fa[u][i-1]][i-1];
for(auto [v,d]:G[u]) if(v!=fath) dis[v]=dis[u]+d,dfs1(v,u);
}
int lca(int x,int y) {
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) x=fa[x][(int)lg2(dep[x]-dep[y])];
if(x==y) return x;
int k=lg2(dep[x]);
Rep(i,k,0) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int cnt[maxn];
int cal_dis(int x,int y){ return dis[x]+dis[y]-2*dis[lca(x,y)]; }
bool check(int x) {
For(i,1,n) cnt[i]=0;
int xx=0;
For(i,1,m) {
if(qwq[i].d>x) {
cnt[qwq[i].st]++;
cnt[qwq[i].ed]++;
cnt[lca(qwq[i].st,qwq[i].ed)]-=2;
xx+=1;
}
}
Rep(i,n,1) cnt[fa[todfn[i]][0]]+=cnt[todfn[i]];
int res=0;
For(u,1,n) for(auto [v,d]:G[u]) if(cnt[v]==xx&&fa[v][0]==u) res=max(res,d);
For(i,1,m) {
if(qwq[i].d-res>x)
return 0;
}
return 1;
};
signed main() {
in2(n,m);
For(i,1,n-1) {
int u,v,d;
in3(u,v,d);
G[u].push_back({v,d});
G[v].push_back({u,d});
}
dfs1(1,0);
For(i,1,m) in2(qwq[i].st,qwq[i].ed),qwq[i].d=cal_dis(qwq[i].st,qwq[i].ed);
int T=0;
For(i,1,m) T=max(T,qwq[i].d);
int l=max(0,T-1000),r=T;
while(l<r) {
// cout<<l<<' '<<r<<'\n';
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l<<'\n';
}