C. Centroids

Codeforces

IDCF708C

Time4000ms

Memory512MB

Difficulty—

data structuresdfs and similardpgraphsgreedytrees

English · Original

Chinese · Translation

Formal · Original

_Tree_ is a connected acyclic graph. Suppose you are given a tree consisting of _n_ vertices. The vertex of this tree is called _centroid_ if the size of each connected component that appears if this vertex is removed from the tree doesn't exceed . You are given a tree of size _n_ and can perform no more than one edge replacement. _Edge replacement_ is the operation of removing one edge from the tree (without deleting incident vertices) and inserting one new edge (without adding new vertices) in such a way that the graph remains a tree. For each vertex you have to determine if it's possible to make it centroid by performing no more than one edge replacement. ## Input The first line of the input contains an integer _n_ (2 ≤ _n_ ≤ 400 000) — the number of vertices in the tree. Each of the next _n_ - 1 lines contains a pair of vertex indices _u__i_ and _v__i_ (1 ≤ _u__i_, _v__i_ ≤ _n_) — endpoints of the corresponding edge. ## Output Print _n_ integers. The _i_\-th of them should be equal to 1 if the _i_\-th vertex can be made centroid by replacing no more than one edge, and should be equal to 0 otherwise. [samples] ## Note In the first sample each vertex can be made a centroid. For example, in order to turn vertex 1 to centroid one have to replace the edge (2, 3) with the edge (1, 3).

_树_ 是一个连通的无环图。假设你被给定一棵包含 #cf_span[n] 个顶点的树。如果从树中移除某个顶点后，每个连通分量的大小都不超过 #cf_span[n/2]，则该顶点被称为 _重心_。你被给定一棵大小为 #cf_span[n] 的树，可以执行至多一次边替换操作。_边替换_ 是指从树中移除一条边（不删除其关联的顶点），并插入一条新的边（不添加新顶点），使得图仍然是一棵树。对于每个顶点，你需要判断是否可以通过执行至多一次边替换，使其成为重心。输入的第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 400 000]) —— 树中顶点的数量。接下来的 #cf_span[n - 1] 行每行包含一对顶点编号 #cf_span[ui] 和 #cf_span[vi] (#cf_span[1 ≤ ui, vi ≤ n]) —— 对应边的两个端点。请输出 #cf_span[n] 个整数。第 #cf_span[i] 个整数应为 #cf_span[1]，如果第 #cf_span[i] 个顶点可以通过替换至多一条边成为重心；否则应为 #cf_span[0]。在第一个样例中，每个顶点都可以被变为重心。例如，为了将顶点 #cf_span[1] 变为重心，需要将边 #cf_span[(2, 3)] 替换为边 #cf_span[(1, 3)]。 ## Input 输入的第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 400 000]) —— 树中顶点的数量。接下来的 #cf_span[n - 1] 行每行包含一对顶点编号 #cf_span[ui] 和 #cf_span[vi] (#cf_span[1 ≤ ui, vi ≤ n]) —— 对应边的两个端点。 ## Output 请输出 #cf_span[n] 个整数。第 #cf_span[i] 个整数应为 #cf_span[1]，如果第 #cf_span[i] 个顶点可以通过替换至多一条边成为重心；否则应为 #cf_span[0]。 [samples] ## Note 在第一个样例中，每个顶点都可以被变为重心。例如，为了将顶点 #cf_span[1] 变为重心，需要将边 #cf_span[(2, 3)] 替换为边 #cf_span[(1, 3)]。

**Definitions** Let $ T = (V, E) $ be a tree with $ n = |V| $ vertices and $ n-1 $ edges. For a vertex $ v \in V $, let $ C_v $ denote the multiset of sizes of connected components of $ T \setminus \{v\} $. A vertex $ v $ is a *centroid* if $ \max(C_v) \leq \left\lfloor \frac{n}{2} \right\rfloor $. **Given** - $ n \in \mathbb{Z} $, $ 2 \leq n \leq 400{,}000 $ - $ T $ is a tree on $ n $ vertices, given via $ n-1 $ edges $ (u_i, v_i) $ **Operation** One *edge replacement* is: remove an edge $ e \in E $, then add a new edge $ e' \notin E $ such that the result is still a tree. At most one such operation may be performed. **Objective** For each vertex $ i \in \{1, \dots, n\} $, determine whether there exists a sequence of at most one edge replacement such that $ i $ becomes a centroid. Output: a binary vector $ (b_1, \dots, b_n) \in \{0,1\}^n $, where $$ b_i = \begin{cases} 1 & \text{if vertex } i \text{ can be made a centroid with } \leq 1 \text{ edge replacement} \\ 0 & \text{otherwise} \end{cases} $$

Samples

Input #1

3
1 2
2 3

Output #1

1 1 1

Input #2

Output #2

1 0 0 0 0

API Response (JSON)

{
  "problem": {
    "name": "C. Centroids",
    "description": {
      "content": "_Tree_ is a connected acyclic graph. Suppose you are given a tree consisting of _n_ vertices. The vertex of this tree is called _centroid_ if the size of each connected component that appears if this ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF708C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_Tree_ is a connected acyclic graph. Suppose you are given a tree consisting of _n_ vertices. The vertex of this tree is called _centroid_ if the size of each connected component that appears if this ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "_树_ 是一个连通的无环图。假设你被给定一棵包含 #cf_span[n] 个顶点的树。如果从树中移除某个顶点后，每个连通分量的大小都不超过 #cf_span[n/2]，则该顶点被称为 _重心_。\n\n你被给定一棵大小为 #cf_span[n] 的树，可以执行至多一次边替换操作。_边替换_ 是指从树中移除一条边（不删除其关联的顶点），并插入一条新的边（不添加新顶点），使得图仍然是一棵树。对于每个顶点，...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T = (V, E) $ be a tree with $ n = |V| $ vertices and $ n-1 $ edges.  \nFor a vertex $ v \\in V $, let $ C_v $ denote the multiset of sizes of connected components of $ T \\setminu...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments