题目：运输计划
思路：
嗯首先一条路径(x,y)可以拆分成(x,lca)和(lca,y)两条。
所以在处理前先计算出每个询问(x,y)的lca，然后处理出路径长。
二分最少时间mid，保留那些大于mid的路径。
然后进行树上差分，即使cnt[lca]-=2，cnt[x]++，cnt[y]++。
然后根据dfs序跑差分就好。
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 300000
#define read(x) scanf("%d",&x)struct Edge{
int x,y,z;Edge(int xx,int yy,int zz) {
x=xx,y=yy,z=zz;}Edge() {
}
};int n,m;
vector<Edge> tr[maxn+5];
int anc[maxn+5][25];
int d[maxn+5];
int v[maxn+5];
int cnt[maxn+5];
int num[maxn+5],nn;void readin() {
read(n),read(m);for(int i=1;i<n;i++) {
int x,y,z;read(x),read(y),read(z);tr[x].push_back(Edge(x,y,z));tr[y].push_back(Edge(y,x,z));}
}void dfs(int x,int fa) {
num[++nn]=x;d[x]=d[fa]+1;anc[x][0]=fa;for(int i=1;i<=20;i++) {
anc[x][i]=anc[anc[x][i-1]][i-1];}for(int i=0;i<tr[x].size();i++) {
int y=tr[x][i].y;if(y!=fa) v[y]=v[x]+tr[x][i].z,dfs(y,x);}
}int findLCA(int x,int y) {
if(d[x]<d[y]) swap(x,y);for(int i=20;i>=0;i--) {
if(d[anc[x][i]]>=d[y]) x=anc[x][i];}if(x==y) return x;for(int i=20;i>=0;i--) {
if(anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];}return anc[x][0];
}int X[maxn+5],Y[maxn+5],lca[maxn+5];
int w[maxn+5];bool judge(int x) {
memset(cnt,0,sizeof(cnt));int ans=0,cc=0;for(int i=1;i<=m;i++) {
if(w[i]>x) {
cnt[lca[i]]-=2;cnt[X[i]]++,cnt[Y[i]]++;ans=max(ans,w[i]-x);cc++;}}if(cc==0) return true;for(int i=n;i>=1;i--) {
cnt[anc[num[i]][0]]+=cnt[num[i]];}for(int i=2;i<=n;i++) {
if(cnt[i]==cc&&v[i]-v[anc[i][0]]>=ans) return true;}return false;
}int main() {
readin();dfs(1,0);for(int i=1;i<=m;i++) {
int x,y;read(x),read(y);lca[i]=findLCA(x,y);X[i]=x,Y[i]=y;w[i]=v[x]+v[y]-2*v[lca[i]];}int L=0,R=1e9;while(L<R) {
int mid=L+(R-L)/2;if(judge(mid)) R=mid;else L=mid+1;}if(!judge(L)) L++;else if(judge(L-1)) L--;printf("%d",L);return 0;
}