E. Машмок-ын зохиосон бодлого

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Маш их оролдсоны эцэст Машмок нэгэн бодлого зохиосон ба таны даалгавар бол үүнийг бодох юм.

Танд $n$ оройнууд бүхий $T$ мод өгөгдөв. Орой бүр нь 1-ээс $n$ хүртэлх цорын ганц индекстэй (өөрөөр хэлбэл 1-ээс $n$ хүртэл дугаар үл давтагдах байдлаар дугаарлагдсан). $T$ модны үндэс нь $1$ гэсэн индекстэй байна. Уг модны $v$ орой бүрийн хувьд танд уг модны үрүүдийн (үр гэдэг нь тус оройноос эхлэлтэй орой болно) тодорхой дараалал өгөгдөнө. Та уг модон дээр 3-н төрлийн асуултыг гүйцэтгэх юм:

  1. $u$ болон $v$-ын хоорондын зайг олно (хамгийн богино зам дээрх ирмэгүүдийн тоо);
  2. $v$ болон $h$ өгөгдөх ба $v$-г өөрийнх нь эх үндсээс салгах ба түүнийг $h$-дахь эх үндэстэй холбох юм. Илүү дэлгэрэнгүйгээр хэлбэл $v$-ээс модны үндэс хүртэлх замыг $x_{1}, x_{2}, ..., x_{l} (h < l)$ гэж тэмдэглэх ба энд $x_{1} = v$, $x_{l}$ нь модны үндэс байна. Тэгвэл $v$-г үүний эх үндэс ($x_{2}$)-оос салгах ба $x_{h + 1}$-тэй холбох юм. Үүний дараа $v$ нь $x_{h + 1}$ оройн үрүүдийн бүртгэлийн төгсгөлд нэмэгдэх ёстой. Өөрөөр хэлбэл $x_{h + 1}$ оройн үрүүдийн (үр гэдэг нь тус оройноос эхлэлтэй орой болно) хамгийн сүүлийн үр болж нэмэгдэх юм.
  3. Дуудагдах функц dfs(үндэс)-ээр үүсэх оройн дарааллаас модны үндсээс $k$ зайтай байх хамгийн сүүлийн оройг олно.

dfs(v) функцийн хуурмаг код:

// ls[v]: list of children of vertex v   
// its i-th element is ls[v][i]  
// its size is size(ls[v])  
sequence result = empty sequence;  
void dfs(vertex now)  
{  
    add now to end of result;  
    for(int i = 1; i <= size(ls[v]); i = i + 1) //loop from i = 1 to i = size(ls[v])  
        dfs(ls[v][i]);  
}

Оролт

Эхний мөрөнд $T$-ын оройн тоо болон гүйцэтгэх ёстой асуултуудын тоог илэрхийлэх зайгаар тусгаарлагдсан 2 бүхэл тоо $n, m (2 ≤ n ≤ 10^{5}; 1 ≤ m ≤ 10^{5})$ өгөгдөнө.

Дараагийн $n$ мөрүүдийн $i$-дахь мөрөнд бүхэл тоо $l_{i} (0 ≤ l_{i} ≤ n)$ өгөгдөх ба энэ нь $i$-дахь оройн үрүүдийн тоог илэрхийлнэ. Дараа нь зайгаар тусгаарлагдсан $l_{i}$ ширхэг бүхэл тоо өгөгдөх ба эдгээрийн $j$-дэх нь $i$-дахь оройн $j$-дэх үрийн индекс байна. Эдгээр оройнуудын дараалал их чухал болохыг анхаарна уу.

Дараагийн $m$ мөрийн мөр болгонд дараах хэлбэрүүдийн нэг нь өгөгдөнө: "$1$ $v$ $u$", "$2$ $v$ $h$", эсвэл "$3$ $k$". Тухайн мөрийн эхний тоо нь бодлогын өгүүлбэрт өгөгдсөний дагуу гүйцэтгэх ёстой асуултын төрлийг илэрхийлнэ. Дараагийн тоонууд нь тухайн асуултыг дүрсэлнэ.

Бүх асуултууд нь зөв байна. Жишээлбэл, 2-р төрлийн асуултын $h$ нь хамгийн багадаа 2 байх ба хамгийн ихдээ $v$-ээс модны үндэс хүртэлх зайтай тэнцүү байна. Мөн 3-р төрлийн асуултын хувьд уг асуулт өгөгдөх үед модны үндсээс $k$ зайтай байх дор хаяж нэг ширхэг орой оршин байна.

Гаралт

1 эсвэл 3-р төрлийн асуулт бүрийн хувьд уг асуултын хариуг агуулах нэг мөр хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
4 9
1 2
1 3
1 4
0
1 1 4
2 4 2
1 3 4
3 1
3 2
2 3 2
1 1 2
3 1
3 2
Гаралт
3
2
2
4
1
3
4
Оролт
2 2
1 2
0
1 2 1
3 1
Гаралт
1
2
Сэтгэгдлүүдийг ачааллаж байна...