[中山市赛 2023] 树的改造

Luogu

IDLGB4339

Time3000ms

Memory512MB

DifficultyP4

2023广东最近公共祖先 LCA差分科创活动小学活动

空白这一次的来到了森精种的家园，精灵都喜欢贴近大自然，~~喜欢住在树洞里~~，所以他们的家园是一棵神树！他们非常喜欢艺术，就是说喜欢改造他们所居住的神树！他们现在居住的树的形态可以描述成一颗有 $n$ 个树洞的树 $A$，一共有 $n-1$ 条边连接，使得树洞两两可以到达，且树洞根据编号是可区分的。现在菲尔带来了下一代神树的设计图，假设为树 $B$，现在她想考一考空白，如果根据如下规则调整神树，至少需要调整多少次才可以将 $A$ 树变成 $B$ 树。一次调整可以选择一个节点 $x$，然后将 $x$ 以及和 $x$ 相邻的节点（也就是有边直接相连的节点）打上魔法标记，然后断开 $x$ 的所有邻边，然后再在所有打上魔法标记的点直接添加若干条新边，形成一棵新的树，同时魔法标记消失。 ## Input 第一行一个正整数 $n$，表示树的大小。接下来 $n-1$ 行，每行两个整数 $u,v$，表示 $A$ 树上的边 $(u,v)$。然后还有 $n-1$ 行，每行两个整数 $u,v$，表示 $B$ 树上的边 $(u,v)$。 ## Output 一行一个整数表示最少调整次数。 [samples] ## Note ### 样例解释 1 可以选择 $x=3$ 进行调整，这时候 $1,3,4,5$ 都被打上了魔法标记。删去了边 $(3, 1)$，$(3, 4)$，$(3, 5)$，添加边 $(1, 4)$，$(4, 3)$，$(3, 5)$。 ### 数据范围对于 $20\%$ 的数据，$n \le 8$。对于 $60\%$ 的数据，$n \le 5000$。对于 $100\%$ 的数据，$n \le 10^6$。

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[中山市赛 2023] 树的改造",
    "description": {
      "content": "空白这一次的来到了森精种的家园，精灵都喜欢贴近大自然，~~喜欢住在树洞里~~，所以他们的家园是一棵神树！他们非常喜欢艺术，就是说喜欢改造他们所居住的神树！ 他们现在居住的树的形态可以描述成一颗有 $n$ 个树洞的树 $A$，一共有 $n-1$ 条边连接，使得树洞两两可以到达，且树洞根据编号是可区分的。 现在菲尔带来了下一代神树的设计图，假设为树 $B$，现在她想考一考空白，如果根据如下规则调整",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4339"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "空白这一次的来到了森精种的家园，精灵都喜欢贴近大自然，~~喜欢住在树洞里~~，所以他们的家园是一棵神树！他们非常喜欢艺术，就是说喜欢改造他们所居住的神树！\n\n他们现在居住的树的形态可以描述成一颗有 $n$ 个树洞的树 $A$，一共有 $n-1$ 条边连接，使得树洞两两可以到达，且树洞根据编号是可区分的。\n\n现在菲尔带来了下一代神树的设计图，假设为树 $B$，现在她想考一考空白，如果根据如下规则调整...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments