记录编号	610076	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]运输计划	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	2.413 s
提交时间	2025-12-11 20:06:30	内存使用	12.23 MiB

#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 8 * 1e5 + 5;
const int LOG = 19;

int n, m;

struct node{
	int to, nxt, len;
}e[MAXN];
int tot = 0, h[MAXN], dep[MAXN];
int d[MAXN], f[MAXN][LOG];
int sum[MAXN];
struct N{
	int u, v, val, lca;
}p[MAXN];
void add(int x, int y, int len){
	e[++ tot] = {y, h[x], len};
	h[x] = tot;
}

void dfs(int u, int fa){
	dep[u] = dep[fa] + 1;
	f[u][0] = fa;
	for(int i = h[u];i;i = e[i].nxt){
		int v = e[i].to;
		if(v == fa) continue;
		sum[v] = sum[u] + e[i].len;
		dfs(v, u);
	}
}

void I_nt(){
	for(int k = 1;k < LOG;k ++){
		for(int i = 1;i <= n;i ++){
			f[i][k] = f[f[i][k - 1]][k - 1];
		}
	}
}

int LCA(int u, int v){
	if(dep[u] < dep[v]) swap(u, v);
	for(int k = LOG - 1;k >= 0;k --){
		if(dep[f[u][k]] >= dep[v]){
			u = f[u][k];
		}
	}
	if(u == v) return u;
	for(int k = LOG - 1;k >= 0;k --){
		if(f[u][k] != f[v][k]){
			u = f[u][k];
			v = f[v][k];
		}
	}
	return f[u][0];
}

int tmp, ans;

void dfs2(int u, int fa){
	for(int i = h[u];i;i = e[i].nxt){
		int v = e[i].to;
		if(v == fa) continue;
		dfs2(v, u);
		d[u] += d[v];
	}
	if(d[u] == tmp){
		ans = max(ans, sum[u] - sum[f[u][0]]);
	}
}

bool check(int mid){
	for(int i = 1;i <= n;i ++) d[i] = 0;
	tmp = 0;
	for(int i = 1;i <= m;i ++){
		if(p[i].val > mid){
			tmp ++;
			d[p[i].u] ++;
			d[p[i].v] ++;
			d[p[i].lca] -= 2;
		}
		else break;
	}
    if(!tmp) return 1;
	ans = -1e9;
	dfs2(1, 0);
	if(p[1].val - ans > mid){
		return false;
	}
	return true;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

	cin >> n >> m;

	for(int i = 1;i < n;i ++){
		int u, v, w; cin >> u >> v >> w;
		add(u, v, w), add(v, u, w);
	}

	dfs(1, 0);I_nt();
	int l = 0, r = 0;
	for(int i = 1;i <= m;i ++){
		cin >> p[i].u >> p[i].v;
		p[i].lca = LCA(p[i].u, p[i].v);
		p[i].val = (sum[p[i].u] + sum[p[i].v] - 2 * sum[p[i].lca]);
		r = max(r, p[i].val);
	}
	sort(p + 1, p + m + 1, [](N a, N b){
		return a.val > b.val;
	});
	while(l < r){
		int mid = (l+r)>>1;
		if(check(mid)){
			//mid is ok
			r = mid ;
		}
		else{
			l = mid + 1;
		}
	}
	cout << r << '\n';
	return 0;
}