4-й этап Республиканской олимпиады по информатике 2020-2021, 2 тура

Есеп С. Канто марафоны

Ограничение по времени:

2 seconds

Ограничение по памяти:

256 megabytes

Жаз келіп, Есмахан таңертең өзінің Канто қаласында жүгіретін уақыты келді деп шешті. Канто қаласы $n - 1$ жолдарымен байланысқан $n$ қиылыстарыдан тұрады. Мұнда кез-келген қиылыстан жолдар бойымен кез-келген басқа қиылысқа жетуге болады. Жоспар бойынша, жүгіру жексенбі күні басталуы керек еді, бірақ сол күні қалада жыл сайын өтетін Канто веломарафоны жоспарланған болатын. Біз $(a,b)$, маршрутын, $a$ бастапқы қиылысы мен $b$ соңғы қиылысы арасындағы жолдар жиынтығымен анықтаймыз, мұнда әрқашан $a < b$. $(a,b)$ маршрутының ұзындығы - ол өтетін жолдардың саны. Есмахан жүгіру кезінде веломарафонның маршрутымен қиылысқаның қаламайды. Сондықтан ол веломарофонмен қиылыспайтын, ең ұзын $(u, v)$ маршрутың білгісі келеді. Сондай-ақ, берілген $k$ санына, Есмахан қанша $ (x,y) $ веломарафонының маршрутың бар екенің білгісі келеді, егер ол тандаған маршруттың ұзындығы $k$ болса. Сізге Канто қаласындағы $n$, қиылыстар саны, берілген. Әрі қарай, екі қиылысты қосатын $ n - 1 $ жол беріледі. Кез-келген қиылыстан жолдар бойымен кез-келген басқа қиылысқа жетуге болады. Осыдан кейін $q$ сұраныстардың саны беріледі. Сұраныстардың екі түрі бар:

1. $x$ $y$, егер сіз веломарафон $(x,y) $ маршрутында өтсе, онда сіз ең ұзақ жолдың ұзындығын табуыңыз керек.
2. $k$, қанша $ (x, y) $ веломарафонының маршрутың бар екенін табуыңыз керек, егер Есмахан тандаған маршруттың ұзындығы $k$ болса.

Формат входного файла

Бірінші жолда $n$ ($ 2 <= n <= 5 * 10^5 $) Келесі $ n-1 $ жолдарының әрқайсысы жолдардың сиппатталады: $ u $ және $ v $ $ (1 <= v, u <= n, u \ne v) $. Келесі жолда $ q $ ($ 1 <= q <= 5 * 10^5 $) - сұраныстар саны. Келесі $ q $ жолдары сұраныстардың сипаттамаларын қамтиды. $1$ $x$ $y$ $(1 <= x < y <= n) $ - бірінші түрдегі сұраныстар үшін. $2$ $k$ $ (0 <= k <= n - 1 $) - екінші түрдегі сұраныстар үшін

Формат выходного файла

Әр сұраныс үшін оның жауабын шығарыңыз

Пример:

Вход

8
1 2
2 3
2 4
3 5
1 6
4 7
7 8
6
2 3
1 4 6
1 1 8
2 4
1 2 3
2 2

Ответ

4
2
2
6
5
12

Замечание

Бұл тапсырмада $10$ бөлімнен тұрады:

1. Шарттан мысалдар. $ 0 $ баллға бағаланады.
2. $n <= 1000$. $ u_i = i $, $ v_i = i + 1 $ барлық $ i $ ($ 1 <= i < n$). $8$ баллға бағаланады.
3. $ u_i = i $, $ v_i = i + 1 $ барлық $ i $ ($ 1 <= i < n$). 10 баллға бағаланады.
4. $ n, q <= 500 $. 9 баллға бағаланады.
5. $ n, q <= 3000 $. 11 баллға бағаланады.
6. Барлық сұраныстар 1 түр және $x_i = 1$ $ i $ ($ 1 <= i <= q $) үшін кепілдендірілген. 12 баллға бағаланады.
7. Барлық сұраныстар 1 түр екеніне кепілдік беріледі. 12 баллға бағаланады.
8. $ q <= 10 $. $11$ баллға бағаланады.
9. $ u_i = i + 1, v_i = \lfloor \frac {i + 1} {2} \rfloor$ барлық $ i $ $ (1 <= i < n$). $10$ баллға бағаланады.
10. Мәселенің бастапқы шарттары. $17$ баллға бағаланады.

( Narkhan Kamzabek )