记录编号	329075	评测结果	AAAAAAAAA
题目名称	暗之链锁	最终得分	100
用户昵称	Tiny	是否通过	通过
代码语言	C++	运行时间	0.851 s
提交时间	2016-10-24 20:32:27	内存使用	93.22 MiB

#include <stdio.h>
 
const int MAXS = 100 * 1024 * 1024;
int buf_cnt = 0;
char read_buf[MAXS];
 
template <typename T> inline void Read_buf(T &num) {
	num = 0; bool minus = false;
	while (read_buf[buf_cnt] < '-' || read_buf[buf_cnt] > '9') ++buf_cnt;
	if (read_buf[buf_cnt] == '-') { minus = true; ++buf_cnt; }
	while (read_buf[buf_cnt] >= '0' && read_buf[buf_cnt] <= '9')
		num = num * 10 + read_buf[buf_cnt++] - '0';
	if (minus) num = -num;
}
 
template <typename T> inline void Read(T &num) {
	num = 0; char ch; bool minus = false;
	while (ch = getchar(), ch < '-' || ch > '9');
	if (ch == '-') { minus = true; ch = getchar(); }
	while (num = num * 10 + ch - '0', ch = getchar(), ch >= '0' && ch <= '9');
	if (minus) num = -num;
}
 
const size_t MAXN = 100000 + 10;
 
int n, m;
struct Edge { int v, ne; } E[MAXN << 1];
int head[MAXN], tot_e = 0;
struct Node { int fa, ch, sz, dep, dfn, top; } N[MAXN];
int s[MAXN];
 
inline void Insert(const int &u, const int &v) {
	E[++tot_e] = (Edge){v, head[u]}; head[u] = tot_e;
}
 
inline void DFS(const int &rt) {
	N[rt].sz = 1; N[rt].ch = 0;
	for (int i = head[rt], v; i; i = E[i].ne) {
		v = E[i].v;
		if (N[v].dep) continue;
		N[v].fa = rt;
		N[v].dep = N[rt].dep + 1;
		DFS(v);
		N[rt].sz += N[v].sz;
		if (N[rt].sz > N[N[rt].ch].sz) N[rt].ch = v;
	}
}
 
inline void DFS(const int &rt, const int &t) {
	static int dfs_time;
	N[rt].top = t; N[rt].dfn = ++dfs_time;
	if (N[rt].ch) DFS(N[rt].ch, t);
	for (int i = head[rt], v; i; i = E[i].ne) {
		v = E[i].v;
		if (v != N[rt].fa && v != N[rt].ch) DFS(v, v);
	}
}
 
inline void Set_Mark(int a, int b) {
	while (N[a].top != N[b].top) {
		if (N[N[a].top].dep < N[N[b].top].dep)
			a ^= b ^= a ^= b;
		++s[N[N[a].top].dfn]; --s[N[a].dfn + 1];
		a = N[N[a].top].fa;
	}
	if (a == b) return;
	if (N[a].dep > N[b].dep) a ^= b ^= a ^= b;
	++s[N[N[a].ch].dfn]; --s[N[b].dfn + 1];
}
 
int main() {
 #define SUBMIT
 #ifdef SUBMIT
	freopen("yam.in", "r", stdin);
	freopen("yam.out", "w", stdout);
	fread(read_buf, 1, MAXS, stdin);
 #endif
 
	Read_buf(n); Read_buf(m);
	int u, v;
	for (int i = 1; i < n; ++i) {
		Read_buf(u); Read_buf(v);
		Insert(u, v); Insert(v, u);
	}
	N[1].dep = 1; DFS(1); DFS(1, 1);
	for (int i = 1; i <= m; ++i) {
		Read_buf(u); Read_buf(v);
		Set_Mark(u, v);
	}
	int ans = 0;
	for (int i = 2; i <= n; ++i) {
		s[i] += s[i - 1];
		if (s[i] == 0) ans += m;
		else if (s[i] == 1) ++ans;
	}
	printf("%d\n", ans);
 
 #ifndef SUBMIT
	puts("\n--------------------");
	getchar(); getchar();
 #else
	fclose(stdin); fclose(stdout);
 #endif
	return 0;
}