题解

Difficulty：5.8 6.3 / Easy+

Tag：线段树合并

首先思考暴力怎么做。显然可以枚举每一条边，然后枚举每条路径，如果路径经过这条边，则将长度减去边权；否则不变，求最大值。这样是 $O(nm\log n)$ 的。

我们可以对每条边的答案拆分成“路径上包括这条边的长度最大值”与“路径中不包括这条边的长度最大值”。可以树剖 $O(m\log^2 n)$ 完成，还是太劣了。

注意到可以记录所有的查询，然后减去包括这条边的查询就是不包括这条边的查询了。如果有这两颗线段树，可以 $O(\log m)$ 完成。

然后线段树合并就可以了。

这题特别毒瘤，我加了快读，非递归查询，离散化的方式优化到 1.3s，卡到 1s 就靠你们了（

#include <bits/stdc++.h>
using namespace std;

typedef pair <int, int> pii;
const int N = 300005;
vector <pii> v[N];
int X[N], Y[N], LCA[N], Z[N];
int lsh[N];
int root[N], ans[N];
int n, m;

namespace TS{
	int dep[N], father[N], head[N], son[N], siz[N], dep2[N];
	void dfs(int cur, int fa){
		dep[cur] = dep[fa] + 1;
		father[cur] = fa;
		siz[cur] = 1;
		for(auto i:v[cur]){
			if(i.first == fa) continue;
			dep2[i.first] = dep2[cur] + i.second;
			dfs(i.first, cur);
			siz[cur] += siz[i.first];
			if(siz[son[cur]] < siz[i.first]) son[cur] = i.first;
		}
	}
	void dfs2(int cur, int top){
		head[cur] = top;
		if(!son[cur]) return;
		dfs2(son[cur], top);
		for(auto i:v[cur]){
			if(i.first == father[cur] || i.first == son[cur]) continue;
			dfs2(i.first, i.first);
		}
	}
	int get_lca(int x, int y){
		while(head[x] != head[y]){
			if(dep[head[x]] < dep[head[y]]) y = father[head[y]];
			else x = father[head[x]];
		}
		return (dep[x] < dep[y] ? x : y);
	}
	int get_len(int x, int y){
		return dep2[x] + dep2[y] - 2 * dep2[get_lca(x, y)];
	}
}

namespace ST{
	const int L = 0, R = 300000;
	int tr[N * 80], lson[N * 80], rson[N * 80];
	int ct = 0;
	void _modify(int &u, int idx, int val, int l, int r){
		if(!u) u = (++ct);
		if(l == r){
			tr[u] += val;
			return;
		}
		int mid = (l + r) >> 1;
		if(mid >= idx) _modify(lson[u], idx, val, l, mid);
		else _modify(rson[u], idx, val, mid + 1, r);
		tr[u] = tr[lson[u]] + tr[rson[u]];
	}
	
	void _merge(int &x, int y, int l, int r){
		if(!x || !y){
			x += y;
			return;
		}
		if(l == r){
			tr[x] += tr[y];
			return;
		}
		int mid = (l + r) >> 1;
		_merge(lson[x], lson[y], l, mid);
		_merge(rson[x], rson[y], mid + 1, r);
		tr[x] = tr[lson[x]] + tr[rson[x]];
	}
	
	void modify(int &u, int idx, int val){_modify(u, idx, val, L, R);}
	int query(int u){
		int l = L, r = R;
		while(l != r){
			int mid = (l + r) >> 1;
			if(tr[rson[u]]) u = rson[u], l = mid + 1;
			else u = lson[u], r = mid;
		}
		return l;
	}
	int query2(int x, int y){
		int l = L, r = R;
		while(l != r){
			int mid = (l + r) >> 1;
			if(tr[rson[x]] > tr[rson[y]]) x = rson[x], y = rson[y], l = mid + 1;
			else x = lson[x], y = lson[y], r = mid;
		}
		return l;
	}
	void merge(int &x, int y){_merge(x, y, L, R);}
}

void dfs(int cur, int fa, int val, int all){
	for(auto i:v[cur]){
		if(i.first == fa) continue;
		dfs(i.first, cur, i.second, all);
		ST::merge(root[cur], root[i.first]);
	}
	// cout << cur << ' ' << ST::query(root[cur]) - val << ' ' << ST::query2(all, root[cur]) << '\n';
	if(cur != 1) ans[cur] = max(lsh[ST::query(root[cur])] - val, lsh[ST::query2(all, root[cur])]);
}

int read(){
	int x = 0;
	char c = getchar();
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)){
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x;
}

int main(){
	n = read(), m = read();
	for(int i = 1; i < n; i++){
		int x, y, z;
		x = read(), y = read(), z = read();
		v[x].push_back({y, z}), v[y].push_back({x, z});
	}
	TS::dfs(1, 0);
	TS::dfs2(1, 0);
	int all = 0;
	for(int i = 1; i <= m; i++){
		int x = read(), y = read();
		X[i] = x, Y[i] = y;
		if(x == y) continue;
		int lca = TS::get_lca(x, y);
		int z = TS::get_len(x, y);
		LCA[i] = lca, Z[i] = z;
		lsh[i] = z;
	}
	std::sort(lsh + 1, lsh + m + 1);
	for(int i = 1; i <= m; i++){
		int z = lower_bound(lsh + 1, lsh + m + 1, Z[i]) - lsh;
		ST::modify(root[X[i]], z, 1);
		ST::modify(root[Y[i]], z, 1);
		ST::modify(root[LCA[i]], z, -2);
		ST::modify(all, z, 1);
	}
	dfs(1, 0, 0, all);
	cout << *min_element(ans + 2, ans + n + 1);
}

$O(m\log m)$。