rt，树剖 LCA+树上差分，5pts record link

仅限今天（1.19）回答的给 2 关。（因为明天进阶计划答疑就开始了）

#include<bits/stdc++.h>
using namespace std;
const int maxn=6e5+10;
const int inf=1e9+10;
int pre[maxn],fw[maxn],len[maxn],l[maxn],r[maxn],cnt,n,m,c[maxn],lc[maxn],dep[maxn],f[maxn],sz[maxn],hson[maxn],tp[maxn],head[maxn];//fw:记录从父亲过来的那条边权值。
struct edge{
	int to,nxt,w;
}e[maxn];
void add_edge(int u,int v,int w){
	e[++cnt]={v,head[u],w};
	head[u]=cnt;
}
void init(){
	for(int i=1;i<=n;i++){
		sz[i]=1;
		tp[i]=i;
	}
}
void dfs1(int x){
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==f[x]) continue;
		f[v]=x;
		dep[v]=dep[x]+1;
		fw[v]=e[i].w;
		pre[v]=pre[x]+e[i].w;
		dfs1(v);
		sz[x]+=sz[v];
		if(sz[v]>sz[hson[x]]) hson[x]=v;
	}
}
void dfs2(int x){
	if(hson[x]){
		tp[hson[x]]=tp[x];
		dfs2(hson[x]);
	}
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==f[x] || v==hson[x]) continue;
		dfs2(v);
	}
}
void dfs3(int x){
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==f[x]) continue;
		dfs3(v);
		c[i]+=c[v];
	}
}
int LCA(int x,int y){
	while(tp[x]!=tp[y]){
		if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
		x=f[tp[x]];
	}
	return dep[x]<dep[y] ? x : y;
}
bool chk(int x){
	int tot=0;
	for(int i=1;i<=m;i++){
		if(len[i]>x){
			tot++;
			c[l[i]]++;c[r[i]]++;
			c[lc[i]]-=2;
		}
	}
	dfs3(1);
	int mx=0;
	for(int i=1;i<=n;i++){
		if(c[i]==tot) mx=max(mx,fw[i]);
	}
	for(int i=1;i<=m;i++){
		if(len[i]>x){
			tot--;
			c[l[i]]--;c[r[i]]--;
			c[lc[i]]+=2;
		}
	}
	for(int i=1;i<=m;i++){
		if(len[i]-mx>x) return false;
	}
	return true;
}
int main(){
	cin>>n>>m;
	init();
	for(int i=1;i<n;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
	dfs1(1);
	dfs2(1);
	for(int i=1;i<=m;i++){
		cin>>l[i]>>r[i];
		lc[i]=LCA(l[i],r[i]);
		len[i]=pre[l[i]]+pre[r[i]]-2*pre[lc[i]];
	}
	int ll=0,rr=inf,ans=inf;
	while(ll<=rr){
		int mid=ll+rr>>1;
		if(chk(mid)){
			rr=mid-1;
			ans=min(ans,mid);
		}
		else ll=mid+1;
	}
	cout<<ans<<"\n";
	return 0;
}