给出一颗点数为 \(n\) 的无根树,边有边权。
接着给出 \(m\) 条简单路径,一条简单路径 \(p\) 的花费 \(\sigma_p\) 被定义为其经过的所有边的边权之和。
你可以选择任意一条边,将其边权置为 \(0\)。
最小化这些路径花费的最大值,输出这个最小化的最大值。
设路径最大值为 \(w\),则 \(w\) 越大越容易满足条件,这个东西具有单调性。
于是考虑二分答案,若我们当前的二分值是 \(w\),则 \(\sigma_p\leq w\) 的路径 \(p\) 都可以不考虑。
而所有 \(\sigma_p>w\) 的路径 \(p\) 都是不满足条件的,所以我们需要将它们全部减小。
但是我们仅可以修改一条边为 \(0\),所以修改的位置必定是所有路径的一个交边。若这些路径的并非交于至少一边,那么条件就无法满足,直接返回。
那如果我们运气较好,这些路径都交于了至少一边,那么设 \(\max\{\sigma_p\}\) 为 \(t\),遍历所有交边,若有一边 \(e\) 满足 \(t-val_e\leq w\),那么条件就可以被满足。
而判断这些路径是否有交边,我们可以将 \(k\) 个路径上的所有边 \(+1\),最后若有一边 \(e\) 的值等于 \(k\),则 \(e\) 是这 \(k\) 个路径的一条交边。
这个操作可以用树上差分来完成。注意到每次树上差分都要求 LCA,于是我们可以先将每条路径的 LCA 预处理出来,这样就省掉了一个 \(\log\),单次时间复杂度为 \(O(n)\)。
加上二分答案,总时间复杂度就是 \(O(n\log n)\)。
注意卡常,可以先将树的 DFS 序存下来,每次树上差分直接在 DFS 序上跑而不是 DFS。
# include <cstdio>
# include <iostream>
# include <utility>
namespace IO{
inline int read(){
int ret = 0 , ti = 1;
char u = getchar();
while( ! isdigit( u ) ){ if( u == '-' ) ti = -1; u = getchar(); }
while( isdigit( u ) ) ret = ret * 10 + u - '0' , u = getchar();
return ret * ti;
}
}
using namespace std;
const int N = 3e5 + 225;
struct Edge{
int nxt , to , val;
}edge[ N << 1 ];
# define forE( u , i ) for( i = head[ u ] ; i ; i = edge[ i ] . nxt )
int head[ N ] , eg;
int n , m , t;
pair< int , int > r[ N ];
# define _u first
# define _v second
int dis[ N ] , tp[ N ] , siz[ N ] , dep[ N ] , fa[ N ] , ch[ N ] , s[ N ] , dfsr[ N ] , df;
int lca[ N ] , d[ N ] , q[ N ] , cnt;
int f[ N ];
void dfs1( int u , int f ){
dep[ u ] = dep[ f ] + 1 , fa[ u ] = f , siz[ u ] = 1 , dfsr[ ++ df ] = u;
int i;
forE( u , i ){
int v = edge[ i ] . to , w = edge[ i ] . val;
if( v == f ) continue;
dis[ v ] = dis[ u ] + w , s[ v ] = w;
dfs1( v , u );
siz[ u ] += siz[ v ];
if( siz[ v ] > siz[ ch[ u ] ] ) ch[ u ] = v;
}
}
void dfs2( int u , int top ){
tp[ u ] = top;
int i;
if( ch[ u ] ) dfs2( ch[ u ] , top );
forE( u , i ){
int v = edge[ i ] . to;
if( v == fa[ u ] || v == ch[ u ] ) continue;
dfs2( v , v );
}
}
int LCA( int u , int v ){
while( tp[ u ] != tp[ v ] ){
if( dep[ tp[ u ] ] < dep[ tp[ v ] ] ) swap( u , v );
u = fa[ tp[ u ] ];
}
return dep[ u ] > dep[ v ] ? v : u;
}
void add_edge( int u , int v , int w , int op ){
edge[ ++ eg ] = { head[ u ] , v , w };
head[ u ] = eg;
if( op ){
edge[ ++ eg ] = { head[ v ] , u , w };
head[ v ] = eg;
}
}
bool check( int x ){
for( int i = 1 ; i <= n ; i ++ ) f[ i ] = 0;
cnt = 0;
for( int i = 1 ; i <= m ; i ++ )
if( d[ i ] > x ) ++ cnt , ++ f[ r[ i ] . _u ] , ++ f[ r[ i ] . _v ] , f[ lca[ i ] ] -= 2;
for( int i = n ; i >= 1 ; i -- ) f[ fa[ dfsr[ i ] ] ] += f[ dfsr[ i ] ];
for( int i = 1 ; i <= n ; i ++ ) if( f[ i ] == cnt && t - s[ i ] <= x ) return 1;
return 0;
}
void solve(){
for( int i = 1 ; i <= m ; i ++ ){
lca[ i ] = LCA( r[ i ] . _u , r[ i ] . _v );
d[ i ] = dis[ r[ i ] . _u ] + dis[ r[ i ]. _v ] - ( dis[ lca[ i ] ] << 1 );
t = max( t , d[ i ] );
}
int l = 0 , r = t , ans = 0;
while( l <= r ){
int mid = l + r >> 1;
if( check( mid ) ) r = mid - 1;
else l = mid + 1 , ans = l;
}
printf( "%d\n" , ans );
}
void input(){
n = IO :: read() , m = IO :: read();
for( int i = 1 ; i <= n - 1 ; i ++ ){
int u = IO :: read() , v = IO :: read() , w = IO :: read();
add_edge( u , v , w , 1 );
}
for( int i = 1 ; i <= m ; i ++ ){
int u = IO :: read() , v = IO :: read();
r[ i ] = make_pair( u , v );
}
}
int main(){
input();
dfs1( 1 , 0 );
dfs2( 1 , 1 );
solve();
return 0;
}