G. The Winds of Winter

Codeforces

IDCF768G

Time2000ms

Memory512MB

Difficulty—

binary searchdata structures

English · Original

Chinese · Translation

Formal · Original

Given a rooted tree with _n_ nodes. The Night King removes exactly one node from the tree and all the edges associated with it. Doing this splits the tree and forms a forest. The node which is removed is not a part of the forest. The root of a tree in the forest is the node in that tree which does not have a parent. We define the strength of the forest as the size of largest tree in forest. Jon Snow wants to minimize the strength of the forest. To do this he can perform the following operation at most once. _He removes the edge between a node and its parent and inserts a new edge between this node and any other node in forest such that the total number of trees in forest remain same._ For each node _v_ you need to find the minimum value of strength of the forest formed when node _v_ is removed. ## Input The first line of the input contains an integer _n_ (1 ≤ _n_ ≤ 105) — the number of vertices in the tree. Each of the next _n_ lines contains a pair of vertex indices _u__i_ and _v__i_ (1 ≤ _u__i_, _v__i_ ≤ _n_) where _u__i_ is the parent of _v__i_. If _u__i_ = 0 then _v__i_ is the root. ## Output Print _n_ line each containing a single integer. The _i_\-th of them should be equal to minimum value of strength of forest formed when _i_\-th node is removed and Jon Snow performs the operation described above at most once. [samples] ## Note The tree for first test case is depicted below. ![image](https://espresso.codeforces.com/11c39aaab54dce5e508a594b4f57109d5cc3b317.png) When you remove the first node, the tree splits to form the following forest. The strength of this forest is 4. ![image](https://espresso.codeforces.com/af8ff74e6630469b37f09c01be60d58b59cfabbd.png) Jon Snow now changes the parent of vertex 10 from 5 to 3. The strength of forest now becomes 3. ![image](https://espresso.codeforces.com/7c76b3c1797ba9a71a6f8086986b53ad566ff4ea.png)

给定一棵包含 #cf_span[n] 个节点的有根树。夜王恰好移除树中的一个节点以及与之关联的所有边。这会将树分割成一片森林。被移除的节点不属于森林。森林中每棵树的根是该树中没有父节点的节点。我们定义森林的强度为森林中最大树的大小。琼·雪希望最小化森林的强度。为此，他最多可以执行一次以下操作： _他移除一个节点与其父节点之间的边，并在该节点与森林中的任意其他节点之间插入一条新边，使得森林中的树的总数保持不变。_ 对于每个节点 #cf_span[v]，你需要求出当移除节点 #cf_span[v] 时，经过上述操作后森林强度的最小值。输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 树中顶点的数量。接下来的 #cf_span[n] 行每行包含一对顶点编号 #cf_span[ui] 和 #cf_span[vi] (#cf_span[1 ≤ ui, vi ≤ n])，其中 #cf_span[ui] 是 #cf_span[vi] 的父节点。若 #cf_span[ui = 0]，则 #cf_span[vi] 是根节点。请输出 #cf_span[n] 行，每行一个整数。第 #cf_span[i] 行应为当移除第 #cf_span[i] 个节点且琼·雪最多执行一次上述操作时，形成的森林的最小强度。第一个测试用例的树如下图所示。当你移除第一个节点时，树分裂成如下森林。该森林的强度为 #cf_span[4]。琼·雪现在将顶点 #cf_span[10] 的父节点从 #cf_span[5] 改为 #cf_span[3]。此时森林的强度变为 #cf_span[3]。 ## Input 输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 树中顶点的数量。接下来的 #cf_span[n] 行每行包含一对顶点编号 #cf_span[ui] 和 #cf_span[vi] (#cf_span[1 ≤ ui, vi ≤ n])，其中 #cf_span[ui] 是 #cf_span[vi] 的父节点。若 #cf_span[ui = 0]，则 #cf_span[vi] 是根节点。 ## Output 请输出 #cf_span[n] 行，每行一个整数。第 #cf_span[i] 行应为当移除第 #cf_span[i] 个节点且琼·雪最多执行一次上述操作时，形成的森林的最小强度。 [samples] ## Note 第一个测试用例的树如下图所示。当你移除第一个节点时，树分裂成如下森林。该森林的强度为 #cf_span[4]。琼·雪现在将顶点 #cf_span[10] 的父节点从 #cf_span[5] 改为 #cf_span[3]。此时森林的强度变为 #cf_span[3]。

**Definitions** Let $ T = (V, E) $ be a rooted tree with $ n $ nodes, where $ V = \{1, 2, \dots, n\} $. For each node $ v \in V $, let $ \text{parent}(v) $ denote its parent (0 if root), and $ \text{children}(v) $ denote its set of children. Let $ \text{size}(v) $ denote the size of the subtree rooted at $ v $. **Given** For each node $ v \in V $, we remove $ v $ and all incident edges, resulting in a forest $ F_v $ consisting of: - The subtrees rooted at each child of $ v $, - The connected component containing the parent of $ v $ (if $ v \neq \text{root} $), excluding the subtree of $ v $. Let $ S_v = \{ \text{size}(u) \mid u \in \text{children}(v) \} \cup \{ n - \text{size}(v) \} $ (excluding 0). The initial strength of $ F_v $ is $ \max(S_v) $. Jon Snow may perform **at most one operation**: - Remove the edge between a node $ u \neq v $ and its parent, - Reattach $ u $ to any other node $ w \neq v $ in the forest, - Such that the number of trees in the forest remains unchanged. This operation allows moving an entire subtree from one parent to another, without merging trees. **Objective** For each node $ v \in V $, compute the **minimum possible strength** of the forest $ F_v $ after performing at most one such operation. That is, for each $ v $, minimize $ \max(\text{new component sizes}) $, where the new sizes are obtained by reassigning **at most one** subtree (from $ S_v \setminus \{\max(S_v)\} $) to reduce the largest component. **Constraints** - $ 1 \le n \le 10^5 $ - The input defines a valid rooted tree with exactly one root (parent = 0).

Samples

Input #1

Output #1

Input #2

2
2 1
0 2

Output #2

1
1

API Response (JSON)

{
  "problem": {
    "name": "G. The Winds of Winter",
    "description": {
      "content": "Given a rooted tree with _n_ nodes. The Night King removes exactly one node from the tree and all the edges associated with it. Doing this splits the tree and forms a forest. The node which is removed",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF768G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given a rooted tree with _n_ nodes. The Night King removes exactly one node from the tree and all the edges associated with it. Doing this splits the tree and forms a forest. The node which is removed...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一棵包含 #cf_span[n] 个节点的有根树。夜王恰好移除树中的一个节点以及与之关联的所有边。这会将树分割成一片森林。被移除的节点不属于森林。\n\n森林中每棵树的根是该树中没有父节点的节点。我们定义森林的强度为森林中最大树的大小。\n\n琼·雪希望最小化森林的强度。为此，他最多可以执行一次以下操作：\n\n_他移除一个节点与其父节点之间的边，并在该节点与森林中的任意其他节点之间插入一条新边，使得森林...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T = (V, E) $ be a rooted tree with $ n $ nodes, where $ V = \\{1, 2, \\dots, n\\} $.  \nFor each node $ v \\in V $, let $ \\text{parent}(v) $ denote its parent (0 if root), and $ \\te...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments