题解

题目描述

小红需要将树 $a$ 的结构转换为树 $b$ 的结构，每次操作可以断开一个非根节点与其父节点的边，并将其连接到另一个节点，要求树的结构保持正确。求最少操作次数。

思路

这道题要求通过最少的操作次数将树A转换为与树B结构相同的树，每次操作可以断开一个非根节点与其父节点的连接并重新连接到另一个节点。关键在于认识到每个节点的父节点在目标树B中必须与当前树A一致，因此我们只需要比较两棵树中每个非根节点的父节点，统计不同的数量即为所需的最小操作次数。

1. 问题分析：每个节点的父子关系必须与目标树 $b$ 完全一致。每次操作仅改变一个节点的父节点。

题目内容

小红获得了两棵结点总数均为$n$，且均以$1$号结点为根结点的树，记为树$a$和树$b$。目两棵树的结点编号均为$1,2,...,n$。小红希望通过对树$a$施加一系列操作，使其完全变成树$b$的形状，更具体地说，两棵树满足:

对于任意一对结点$u$和$v$，其父子关系在两棵树中完全一致

树的整体结构(即树形)与结点编号对应。

在每一轮操作中，小红可以依次执行如下步骤:

第一步:切边。在树$a$中选择一个非根结点$x$，将其与其父节点的边断开;

第二步:连边。在树$a$中选择一个结点$y$，新建一条树边连接结点$x$和$y$，但是注意，你需要保证连接后树a仍然是一整棵树(不能出现环、且树上仍有$n$个结点)。

请你帮助小红计算，最少需要执行多少次操作，才能将树$a$的结构变换为树$b$的结构。

输入描述

第一行一个整数$n(1≤n≤ 2×10^5)$，表示树$a$和树$b$的结点总数。

接下来$n - 1$行，每行两个整数$u,v(1≤u,v≤n;u≠v)$表示树$a$中的一条边。

接下来$n - 1$行，每行两个整数$u,v(1≤u,v≤n;u≠v),$表示树$b$中的一条边。

输出描述

一个整数，表示小红最少需要执行的操作次数。

样例1

输入

3
1 2
2 3
1 3
1 2

输出

1