G. Gadget Hackwrench

Codeforces

IDCF10068G

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Chip 'n' Dale rescue rangers! But observant viewers know that help is usually required by Chip and Dale themselves. Today you are in the role of cunning Gadget Hackwrench. So, Chip and Dale are again in the paws of Fat Cat. He doesn't like rodents much and therefore prepared a treacherous test. He is going to put them to a labyrinth and see if they can escape from it. The labyrinth is actually built as a tree where each edge has fixed direction (by definition #cf_span(class=[tex-font-style-underline], body=[tree]) is a connected unoriented graph without cycles). Gadget has intercepted a talk between Fat Cat and his henchmen about future tests. For each test round she knows the exact location where Chip and Dale are to be put by Fat Cat and the location of an exit. Gadget wants to compute whether they will be able to find an exit for each test. The first line of input contains an integer N (1 ≤ N ≤ 105) — the number of vertices in a graph. On the next N - 1 lines of input directed arcs of the tree are given. On the (i + 1)th line integer numbers ai and bi are given (1 ≤ ai, bi ≤ N) denoting an arc from vertex ai to vertex bi. It is guaranteed that arcs a1, a2, ..., an - 1 without orientation form a tree. Then a string with integer number M (1 ≤ M ≤ 105) is given — the number of queries to process. Next M lines describe queries: (n + 1 + i)th line contain integers xi and yi (1 ≤ xi, yi ≤ N). For each query please output a separate line containing 'Yes' (without quotes) if graph contains a path between xi and yi, or 'No' (without quotes) in other case. ## Input The first line of input contains an integer N (1 ≤ N ≤ 105) — the number of vertices in a graph. On the next N - 1 lines of input directed arcs of the tree are given. On the (i + 1)th line integer numbers ai and bi are given (1 ≤ ai, bi ≤ N) denoting an arc from vertex ai to vertex bi. It is guaranteed that arcs a1, a2, ..., an - 1 without orientation form a tree. Then a string with integer number M (1 ≤ M ≤ 105) is given — the number of queries to process. Next M lines describe queries: (n + 1 + i)th line contain integers xi and yi (1 ≤ xi, yi ≤ N). ## Output For each query please output a separate line containing 'Yes' (without quotes) if graph contains a path between xi and yi, or 'No' (without quotes) in other case. [samples]

**Definitions** Let $ G = (V, E) $ be a directed tree with $ |V| = N $, where $ E \subseteq V \times V $ is a set of directed edges. The underlying undirected graph of $ G $ is a tree. **Constraints** 1. $ 1 \leq N \leq 10^5 $ 2. $ |E| = N - 1 $ 3. For each edge $ (a_i, b_i) \in E $, $ 1 \leq a_i, b_i \leq N $ 4. Let $ M \in \mathbb{Z} $, $ 1 \leq M \leq 10^5 $, be the number of queries. 5. Each query is a pair $ (x_i, y_i) \in V \times V $, $ 1 \leq x_i, y_i \leq N $ **Objective** For each query $ (x_i, y_i) $, determine whether there exists a directed path from $ x_i $ to $ y_i $ **or** from $ y_i $ to $ x_i $ in $ G $. Output "Yes" if such a path exists in either direction; otherwise, output "No".

API Response (JSON)

{
  "problem": {
    "name": "G. Gadget Hackwrench",
    "description": {
      "content": "Chip 'n' Dale rescue rangers! But observant viewers know that help is usually required by Chip and Dale themselves. Today you are in the role of cunning Gadget Hackwrench. So, Chip and Dale are again",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10068G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Chip 'n' Dale rescue rangers! But observant viewers know that help is usually required by Chip and Dale themselves. Today you are in the role of cunning Gadget Hackwrench.\n\nSo, Chip and Dale are again...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be a directed tree with $ |V| = N $, where $ E \\subseteq V \\times V $ is a set of directed edges. The underlying undirected graph of $ G $ is a tree.\n\n**Constraint...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments