Case 1
暴力枚举每条边边权为$0$,每次查询询问中的最长路径取$\min$。
复杂度$O(nm\log\ n)$
Case 2
令最长链最小,其显然具有单调性,考虑二分。
转化为判定问题:
是否存在一种方案,满足所有询问中的链长均不超过$x$。
考虑如何判定:
如果在原树中有若条所询问的链长大于$x$,那么显然我们要令边权为$0$的边一定在这些链的公共边上。
那么我们贪心地令这些链的公共边中边权最大的边边权(记作$w$)为$0$后判一下是否满足所有的链长均小于等于$x$。
显然,原来链长小于等于$x$的依然小于等于$x$,而对于原来链长大于$x$的链而言,如果原来的链长为$L$,那么修改后的链长即$L-w$。
那么,如果$x\ge \max(L-w)$即$x$合法。
复杂度$O((n+m)\log L)$
在处理询问时预处理出所有的$lca$以及$dfn$重编号直接从$n$向前递推子树和减少常数(。
#include <iostream>
#include <cstring>
#include <cstdio>
namespace wxy{
const int N = 3e5 + 5;
int head[N],fail[N << 1],edge[N << 1],w[N << 1],tot;
int dep[N],dis[N],fa[N][35],ds[N],dfn[N],wi[N],tlca[N],p;
typedef std::pair<int,int> PII;
#define x first
#define y second
PII ask[N];
int t[N],n,m,cnt;
inline void add(int x,int y,int we){
edge[++tot] = y;
w[tot] = we;
fail[tot] = head[x];
head[x] = tot;
}
void dfs(int x){
dfn[++cnt] = x;
for (int i = 1;i < 20; i++)
fa[x][i] = fa[fa[x][i-1]][i-1];
for (int i = head[x];i;i = fail[i]){
int v = edge[i];
if (v == fa[x][0]) continue;
dep[v] = dep[x] + 1;
dis[v] = dis[x] + w[i];
wi[v] = w[i];
fa[v][0] = x;
dfs(v);
}
}
inline int lca(int x,int y){
if (dep[x] < dep[y]) std::swap(x,y);
int d = dep[x] - dep[y];
for (int j = 0; j < 20; j++)
if (d >> j & 1) x = fa[x][j];
if (x == y) return x;
for (int j = 19; j >= 0; j--){
if (fa[x][j] != fa[y][j]){
x = fa[x][j];y = fa[y][j];
}
}
return fa[x][0];
}
inline bool check(int x){
memset(t,0,sizeof t);
int maxd = 0;
cnt = 0;
for (int i = 1; i <= m; i++){
int a = ask[i].x;
int b = ask[i].y;
int lc = tlca[i];
int dist = dis[a] + dis[b] - (dis[lc] << 1);
if (dist > x){
cnt++;t[a]++;t[b]++;
t[lc] -= 2;
maxd = std::max(maxd,dist);
}
}
if (cnt == 0) return true;
for (int i = n; i >= 1; i--)
t[fa[dfn[i]][0]] += t[dfn[i]];
for (int i = 1; i <= n; i++)
if (t[i] == cnt && maxd - wi[i] <= x) return true;
return false;
}
void main(){
cnt = tot = 0;
scanf("%d%d",&n,&m);
for (int i = 1; i < n; i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
memset(dep,-1,sizeof dep);
dep[1] = 0;
dfs(1);
for (int i = 1; i <= m; i++){
scanf("%d%d",&ask[i].x,&ask[i].y);
tlca[i] = lca(ask[i].x,ask[i].y);
}
int l = 0,r = 1e9;
while (l < r){
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d",l);
}
}signed main(){
wxy::main();
return 0;
}