最新消息:380元/半年,推荐全网最具性价比的一站式编程学习平台码丁实验室

信息学奥赛题库- 独特的树叶

C++ 少儿编程 1091浏览 0评论

友情提示:380元/半年,儿童学编程,就上码丁实验室

【题目描述】

JYY有两棵树$A$和$B$:树$A$有$N$个点,编号为$1$到$N$;树$B$有$N+1$个节点,编号为$1$到$N+1$。

JYY知道树$B$恰好是由树$A$加上一个叶节点,然后将节点的编号打乱后得到的。他想知道,这个多余的叶子到底是树B中的哪一个叶节点呢?

【输入】

输入一行包含一个正整数$N$。

接下来$N-1$行,描述树$A$,每行包含两个整数表示树$A$中的一条边;

接下来$N$行,描述树$B$,每行包含两个整数表示树$B$中的一条边。

【输出】

输出一行一个整数,表示树$B$中相比树$A$多余的那个叶子的编号。如果有多个符合要求的叶子,输出$B$中编号最小的那一个的编号。

【输入样例】

5
1 2
2 3
1 4
1 5
1 2
2 3
3 4
4 5
3 6

【输出样例】

1

【提示】

【数据规模】

对于所有数据,$1≤n≤10^5$。

您必须 登录 才能发表评论!