/*
sum[x] + sum[y] - sum[lca] - sum[f[lca]]

sum[x] + sum[y] - 2*sum[lca]

*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5, mod = 1e9+7;
int a[N], n, m;
int f[N][20], dep[N], sum[N];
struct node {
	int y, w;
};
vector<int> g[N];

void dfs(int x, int _fa) {
	dep[x] = dep[_fa] + 1;
	f[x][0] = _fa;
	for(int i = 1; i < 20; i++) {
		f[x][i] = f[f[x][i-1]][i-1];
	}
	for(int i = 0; i <g[x].size(); i++) {
		int y = g[x][i];
		if(y == _fa) continue;
		dfs(y, x);
	}
}
int lca(int x, int y) {
	if(dep[x] < dep[y]) swap(x, y);
	int d = dep[x] - dep[y];
	for(int i = 19; i >= 0; i--)
		if((1<<i) & d) x = f[x][i];
	if(x == y) return x;
	for(int i = 19; i >= 0; i--)
		if(f[x][i] != f[y][i])
			x = f[x][i], y = f[y][i];
	return f[x][0];
}
int ans = 0;
void dfs1(int x, int _fa){
	for(int i = 0; i < g[x].size(); i++){
		int y = g[x][i];
		if(y == _fa) continue;
		dfs1(y, x);
		sum[x] += sum[y];
	}
	
}
signed main() {
	cin >> n >> m;
	for(int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1, 0);
	for(int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		sum[x] += 1;
		sum[y] += 1;
		int l = lca(x, y);
		sum[l] -= 2;
	}
	dfs1(1, 0);
	for(int i = 2; i <= n; i++) {
		if(sum[i] == 0) ans+=m;
		if(sum[i] == 1) ans+=1;
	}
	
//	cout << "\n";
	cout << ans;
	return 0;
}


1 条评论

  • 1