#include <bits/stdc++.h>



using namespace std;
#define mp make_pair
#define pb push_back
#define S second
#define F first
typedef long long ll;
const int N = 1e5 + 10;
ll ans[N],s[N];

int dep[N],f[N][21];
int first[N],nex[N << 1],v[N << 1],num = 0;
int n,m;
int vis[N],dfn[N],cnt = 0;
multiset<int> b[N];
multiset<int>::iterator it;
vector<pair<int,pair<int,int> > > p[N];
inline void add(int x,int y) {
	v[++num] = y;
	nex[num] = first[x];
	first[x] = num;
}
inline void Pre(int u,int h) {
	dfn[u] = ++cnt;
	dep[u] = dep[h] + 1;
	f[u][0] = h;
	for(int i = 1;i <= 20;i++) {
		f[u][i] = f[f[u][i - 1]][i - 1];
	}
	for(int i = first[u];i != -1;i = nex[i]) {
		int to = v[i];
		if(to != h) {
			Pre(to,u);
		}
	}
}
inline int Lca(int x,int y) {
	if(dep[x] < dep[y]) swap(x,y);
	for(int i = 20;i >= 0;i--) {
		if(dep[f[x][i]] >= dep[y]) {
			x = f[x][i];
		}
	}
	if(x == y)
	return x;
	for(int i = 20;i >= 0;i--) {
		if(f[x][i] != f[y][i]) {
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
inline int Ask(int x,int y) {
	return dep[x] + dep[y] - 2 * dep[Lca(x,y)];
}

inline void ADD(multiset<int> &a,int x,int u) {
	if(a.size() != 0) {
		it = a.lower_bound(dfn[x]);
		int y = *it;
		if(it == a.end()) {
			int z = *--it;
			ans[u] = ans[u] + Ask(vis[z],x);
		} else if(it == a.begin()) {
			ans[u] = ans[u] + Ask(vis[y],x);
		} else {
			int z = *--it;
			ans[u] = ans[u] - Ask(vis[y],vis[z]);
			ans[u] = ans[u] + Ask(vis[z],x) + Ask(x,vis[y]);
		}	
	}
	a.insert(dfn[x]);
	
	return ;
}
inline void Del(multiset<int> &a,int x,int u) {
	a.erase(a.find(dfn[x]));
	if(a.size() >= 1) {
		it = a.lower_bound(dfn[x]);
		int y = *it;
		if(it == a.end()) {
			ans[u] = ans[u] - Ask(vis[*(--it)],x);
		} else if(it == a.begin()) {
			ans[u] = ans[u] - Ask(vis[*it],x);
		} else {
			int z = *--it;
			ans[u] = ans[u] + Ask(vis[y],vis[z]);
			ans[u] = ans[u] - Ask(vis[z],x) - Ask(x,vis[y]);
		}
	} 
	return ;
} 
inline void Merge(multiset<int> &A,multiset<int> B,int u,int to) {
	if(B.empty() == true) return ;
	if(A.size() < B.size()) swap(A,B),ans[u] = ans[to];
	for(multiset<int>::iterator iter = B.begin();iter != B.end();) {
		ADD(A,vis[*iter],u);
		iter = B.erase(iter);
	}
	
	return ;
}
inline void dfs(int u,int h) {

	for(int i = first[u];i != -1;i = nex[i]) {
		int to = v[i];
		if(to != h) {
			dfs(to,u);
		 	Merge(b[u],b[to],u,to);
		}
	}	
	if(p[u].size()) {
		for(auto &i : p[u]) {
			if(i.F == 1) {
 				ADD(b[u],i.S.F,u);
				ADD(b[u],i.S.S,u);
			}
		}
	}
	if(p[u].size()) {
		for(auto &i : p[u]) {
			if(i.F == -1) {
 				Del(b[u],i.S.F,u);
				Del(b[u],i.S.S,u);
			}
		}
	}
	if(b[u].size() > 1) s[u] = (ans[u] + Ask(vis[*b[u].begin()],vis[*--b[u].end()])) / 2;
}
int main() {
	memset(first,-1,sizeof first);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >> n >> m;
	
	for(int i = 1;i < n;i++) {
		int x,y;
		cin >> x >> y;
		add(x,y);
		add(y,x);
	}
	Pre(1,0);
	for(int i = 1;i <= n;i++) vis[dfn[i]] = i;
	for(int i = 1;i <= m;i++) {
		int x,y;
		cin >> x >> y;
		p[x].pb(mp(1,mp(x,y)));
		p[y].pb(mp(1,mp(x,y)));
		p[f[Lca(x,y)][0]].pb(mp(-1,mp(x,y)));
		p[Lca(x,y)].pb(mp(-1,mp(x,y)));
	}
	dfs(1,0);
	ll Rel = 0;
	for(int i = 1;i <= n;i++) Rel += s[i];
	cout << Rel / 2 << '\n';
	return 0;
}

每次合并回收了内存了的