E. Anton and Tree

Codeforces

IDCF734E

Time3000ms

Memory256MB

Difficulty—

dfs and similardptrees

English · Original

Chinese · Translation

Formal · Original

Anton is growing a tree in his garden. In case you forgot, the tree is a connected acyclic undirected graph. There are _n_ vertices in the tree, each of them is painted black or white. Anton doesn't like multicolored trees, so he wants to change the tree such that all vertices have the same color (black or white). To change the colors Anton can use only operations of one type. We denote it as _paint_(_v_), where _v_ is some vertex of the tree. This operation changes the color of all vertices _u_ such that all vertices on the shortest path from _v_ to _u_ have the same color (including _v_ and _u_). For example, consider the tree <center>![image](https://espresso.codeforces.com/a61536a42589f4c98c17f33145edb9e979d29fce.png)</center>and apply operation _paint_(3) to get the following: <center>![image](https://espresso.codeforces.com/c63b72d85822234bdf1a1fd962be251afd42e3ba.png)</center>Anton is interested in the minimum number of operation he needs to perform in order to make the colors of all vertices equal. ## Input The first line of the input contains a single integer _n_ (1 ≤ _n_ ≤ 200 000) — the number of vertices in the tree. The second line contains _n_ integers _color__i_ (0 ≤ _color__i_ ≤ 1) — colors of the vertices. _color__i_ = 0 means that the _i_\-th vertex is initially painted white, while _color__i_ = 1 means it's initially painted black. Then follow _n_ - 1 line, each of them contains a pair of integers _u__i_ and _v__i_ (1 ≤ _u__i_, _v__i_ ≤ _n_, _u__i_ ≠ _v__i_) — indices of vertices connected by the corresponding edge. It's guaranteed that all pairs (_u__i_, _v__i_) are distinct, i.e. there are no multiple edges. ## Output Print one integer — the minimum number of operations Anton has to apply in order to make all vertices of the tree black or all vertices of the tree white. [samples] ## Note In the first sample, the tree is the same as on the picture. If we first apply operation _paint_(3) and then apply _paint_(6), the tree will become completely black, so the answer is 2. In the second sample, the tree is already white, so there is no need to apply any operations and the answer is 0.

Anton 在他的花园里种了一棵树。如果你忘记了，树是一个连通的无环无向图。树中有 #cf_span[n] 个顶点，每个顶点被涂成黑色或白色。Anton 不喜欢多色的树，因此他希望将树修改为所有顶点颜色相同（全黑或全白）。 Anton 只能使用一种操作来改变颜色。我们记该操作为 #cf_span[paint(v)]，其中 #cf_span[v] 是树中的某个顶点。该操作会改变所有满足“从 #cf_span[v] 到 #cf_span[u] 的最短路径上所有顶点颜色相同”（包括 #cf_span[v] 和 #cf_span[u]）的顶点 #cf_span[u] 的颜色。例如，考虑下述树：并应用操作 #cf_span[paint(3)]，得到如下结果： Anton 想知道，为了使所有顶点颜色一致，他至少需要执行多少次操作。输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200 000]）——树中顶点的数量。第二行包含 #cf_span[n] 个整数 #cf_span[colori]（#cf_span[0 ≤ colori ≤ 1]）——顶点的颜色。#cf_span[colori = 0] 表示第 #cf_span[i] 个顶点初始为白色，#cf_span[colori = 1] 表示初始为黑色。接下来是 #cf_span[n - 1] 行，每行包含一对整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n, ui ≠ vi]）——表示由对应边连接的两个顶点的编号。保证所有对 #cf_span[(ui, vi)] 互不相同，即不存在重边。输出一个整数——Anton 为了使所有顶点变为黑色或全部变为白色所需执行的最少操作次数。在第一个样例中，树与图中相同。如果我们先执行操作 #cf_span[paint(3)]，再执行 #cf_span[paint(6)]，树将全部变为黑色，因此答案是 #cf_span[2]。在第二个样例中，树已经是全白的，因此无需执行任何操作，答案是 #cf_span[0]。 ## Input 输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200 000]）——树中顶点的数量。第二行包含 #cf_span[n] 个整数 #cf_span[colori]（#cf_span[0 ≤ colori ≤ 1]）——顶点的颜色。#cf_span[colori = 0] 表示第 #cf_span[i] 个顶点初始为白色，#cf_span[colori = 1] 表示初始为黑色。接下来是 #cf_span[n - 1] 行，每行包含一对整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n, ui ≠ vi]）——表示由对应边连接的两个顶点的编号。保证所有对 #cf_span[(ui, vi)] 互不相同，即不存在重边。 ## Output 输出一个整数——Anton 为了使所有顶点变为黑色或全部变为白色所需执行的最少操作次数。 [samples] ## Note 在第一个样例中，树与图中相同。如果我们先执行操作 #cf_span[paint(3)]，再执行 #cf_span[paint(6)]，树将全部变为黑色，因此答案是 #cf_span[2]。在第二个样例中，树已经是全白的，因此无需执行任何操作，答案是 #cf_span[0]。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of vertices in a tree. Let $ c: V \to \{0,1\} $ be the initial coloring function, where $ c(v) = 0 $ denotes white and $ c(v) = 1 $ denotes black. Let $ T = (V, E) $ be an undirected tree with $ |V| = n $, $ |E| = n-1 $. An operation $ \text{paint}(v) $ changes the color of all vertices $ u \in V $ such that the unique path from $ v $ to $ u $ consists of vertices all of the same color (including endpoints). **Constraints** 1. $ 1 \leq n \leq 200{,}000 $ 2. $ c(v) \in \{0,1\} $ for all $ v \in V $ 3. The graph $ T $ is a tree (connected, acyclic, undirected). **Objective** Find the minimum number of $ \text{paint} $ operations required to make all vertices in $ T $ the same color (either all 0 or all 1).

Samples

Input #1

11
0 0 0 1 1 0 1 0 0 1 1
1 2
1 3
2 4
2 5
5 6
5 7
3 8
3 9
3 10
9 11

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. Anton and Tree",
    "description": {
      "content": "Anton is growing a tree in his garden. In case you forgot, the tree is a connected acyclic undirected graph. There are _n_ vertices in the tree, each of them is painted black or white. Anton doesn't ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF734E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Anton is growing a tree in his garden. In case you forgot, the tree is a connected acyclic undirected graph.\n\nThere are _n_ vertices in the tree, each of them is painted black or white. Anton doesn't ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Anton 在他的花园里种了一棵树。如果你忘记了，树是一个连通的无环无向图。\n\n树中有 #cf_span[n] 个顶点，每个顶点被涂成黑色或白色。Anton 不喜欢多色的树，因此他希望将树修改为所有顶点颜色相同（全黑或全白）。\n\nAnton 只能使用一种操作来改变颜色。我们记该操作为 #cf_span[paint(v)]，其中 #cf_span[v] 是树中的某个顶点。该操作会改变所有满足“从 #...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of vertices in a tree.  \nLet $ c: V \\to \\{0,1\\} $ be the initial coloring function, where $ c(v) = 0 $ denotes white and $ c(v) = 1 $ denotes...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments