I. Древо пицц

Codeforces

IDCF10077I

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

У многих людей есть генеалогическое древо, но мало кто знает, что у пицц оно тоже есть. Всё потому что изначально был только один вид пиццы, а затем постепенно появлялись новые виды пицц. Новые пиццы появлялись не просто так – они основывались на своём предке - так постепенно появилось целое генеалогическое древо из пицц, где пиццы соединены линиями со своими предшественниками. В пиццерии «Эль ням» работает величайший повар по имени Джордж Вкусняшков. Для него очень важно сочетание пицц, это буквально смысл его жизни. Поэтому он никогда не сделает заказ из двух пицц, если первая не является предком второй. Так как просмотр генеалогического древа перед выполнением каждого заказа занимает слишком много времени, администрация «Эль ням» решила автоматизировать данный процесс. Так как «Эль ням» просто пиццерия, здесь нет программистов, поэтому администрация просит вас помочь с решением данной проблемы. Вам даны Q заказов на изготовление 2-ух пицц. Вам необходимо выяснить для каждого заказа, будет ли его делать Джордж Вкусняшков. В первой строке указано целое число N – количество видов пицц (2 ≤ N ≤ 105). Далее следуют N-1 строк. Каждая строка содержит два натуральных числа a и b, которые означают, что a – пицца-предшественник b (1 ≤ a, b ≤ N), корнем древа пицц является пицца с номером 1. Далее дано число натуральное Q (1 ≤ Q ≤ 105). Далее следуют Q строк. Каждая строка содержит два натуральных числа А и В – заказ на две пиццы (1 ≤ А, В ≤ N). Для каждого заказа в отдельной строке ответьте на вопрос: будет ли его готовить Джордж Вкусняшков, то есть является ли А предком В. В случае положительного ответа выведите “YES”, иначе “NO” (заглавными буквами). ## Входные Данные В первой строке указано целое число N – количество видов пицц (2 ≤ N ≤ 105). Далее следуют N-1 строк. Каждая строка содержит два натуральных числа a и b, которые означают, что a – пицца-предшественник b (1 ≤ a, b ≤ N), корнем древа пицц является пицца с номером 1. Далее дано число натуральное Q (1 ≤ Q ≤ 105).Далее следуют Q строк. Каждая строка содержит два натуральных числа А и В – заказ на две пиццы (1 ≤ А, В ≤ N). ## Выходные Данные Для каждого заказа в отдельной строке ответьте на вопрос: будет ли его готовить Джордж Вкусняшков, то есть является ли А предком В. В случае положительного ответа выведите “YES”, иначе “NO” (заглавными буквами). ## Примеры Входные данные81 61 76 56 86 28 48 371 71 36 44 36 55 63 7Выходные данныеYESYESYESNOYESNONOВходные данные31 21 331 21 32 1Выходные данныеYESYESNO [samples]

**Definitions** Let $ N \in \mathbb{Z} $ be the number of pizza types. Let $ T = (V, E) $ be a rooted tree with $ V = \{1, 2, \dots, N\} $, where vertex $ 1 $ is the root, and each edge $ (a, b) \in E $ denotes that pizza $ a $ is an immediate ancestor of pizza $ b $. Let $ Q \in \mathbb{Z} $ be the number of queries. Each query is a pair $ (A, B) \in V \times V $. **Constraints** 1. $ 2 \leq N \leq 10^5 $ 2. $ |E| = N - 1 $, and $ T $ is a tree rooted at 1. 3. $ 1 \leq Q \leq 10^5 $ 4. For each query $ (A, B) $: $ 1 \leq A, B \leq N $ **Objective** For each query $ (A, B) $, determine whether $ A $ is an ancestor of $ B $ in $ T $. Output "YES" if $ A $ is an ancestor of $ B $, otherwise output "NO".

API Response (JSON)

{
  "problem": {
    "name": "I. Древо пицц",
    "description": {
      "content": "У многих людей есть генеалогическое древо, но мало кто знает, что у пицц оно тоже есть. Всё потому что изначально был только один вид пиццы, а затем постепенно появлялись новые виды пицц. Новые пиццы ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10077I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "У многих людей есть генеалогическое древо, но мало кто знает, что у пицц оно тоже есть. Всё потому что изначально был только один вид пиццы, а затем постепенно появлялись новые виды пицц. Новые пиццы ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of pizza types.  \nLet $ T = (V, E) $ be a rooted tree with $ V = \\{1, 2, \\dots, N\\} $, where vertex $ 1 $ is the root, and each edge $ (a, b) \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments