记录编号	601351	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4083.猴猴的比赛	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	0.506 s
提交时间	2025-06-16 20:35:26	内存使用	3.67 MiB

#include <cstdio>
typedef long long ll;
#define isdigit(ch) ((ch) >= '0' && (ch) <= '9')

template <typename T> T read() { // 快读
	T res = 0, f = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
	for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
	return res * f;
}

template <typename T> void write(T x, char ed = '\n') { // 快写
	if (x < 0) putchar('-'), x = -x;
	static int sta[16], top = 0;
	do {
		sta[++top] = x % 10;
		x /= 10;
	} while(x);
	while (top) {
		putchar(sta[top--] ^ 48);
	}
	putchar(ed);
}

const int MAXN = 1e5 + 10;

struct GRAPH { // 图
	struct EDGE { // 链式前向星
		int v, next;
	} edge[MAXN << 1];
	
	int head[MAXN], edgeNum;
	void AddEdge(int u, int v) { // 加边
		edge[++edgeNum] = {v, head[u]};
		head[u] = edgeNum;
	}
} G1, G2;

int b[MAXN << 1], bcnt, appear[MAXN][3];
void dfs(int now, int fa) { // 生成 dfs 序
	b[++bcnt] = now;
	appear[now][1] = bcnt;
	for (int i = G1.head[now]; i; i = G1.edge[i].next) {
		int v = G1.edge[i].v;
		if (v == fa) continue;
		dfs(v, now);
	}
	b[++bcnt] = now;
	appear[now][2] = bcnt;
}

struct BITTREE { // 树状数组
	int tree[MAXN << 1], n;
	int lowbit(int x) { 
		return x & -x;
	}
	void Add(int x, int y) { // 1 - x 加
		for (; x <= n; x += lowbit(x)) tree[x] += y;
	}
	int Ask(int x) { // 1 - x 的和
		int res = 0;
		for (; x; x -= lowbit(x)) res += tree[x];
		return res;
	}
} T;

ll ans;
void DFS(int now, int fa) { // 计算答案
	ans += T.Ask(appear[now][1]);
	T.Add(appear[now][1], 1); // 标记
	T.Add(appear[now][2], -1);
	for (int i = G2.head[now]; i; i = G2.edge[i].next) {
		int v = G2.edge[i].v;
		if (v == fa) continue;
		DFS(v, now);
	}
	T.Add(appear[now][1], -1); // 回溯
	T.Add(appear[now][2], 1);
}

int n;

int main() {
	freopen("monkeyclim.in", "r", stdin);
	freopen("monkeyclim.out", "w", stdout);
	n = read<int>();
	for (int i = 1; i <= n - 1; ++i) {
		int u = read<int>(), v = read<int>();
		G1.AddEdge(u, v);
		G1.AddEdge(v, u);
	}
	for (int i = 1; i <= n - 1; ++i) {
		int u = read<int>(), v = read<int>();
		G2.AddEdge(u, v);
		G2.AddEdge(v, u);
	}
	dfs(1, 0);
	T.n = bcnt;
	DFS(1, 0);
	write(ans);
	return 0;
}