Fişierul intrare/ieşire:traffickers.in, traffickers.outSursăRMI 2018
AutorAndrei ArnautuAdăugată delaurageorgescuLaura Georgescu laurageorgescu
Timp execuţie pe test3 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Traffickers

Pablo este unul dintre cei mai notorii bărbaţi din Vestul Sălbatic, bine cunoscut pentru influenţa sa asupra N oraşe, interconectate prin drumuri, care formează un arbore. Băieţii lui Pablo sunt traficanţi care transportă neobosiţi marfă. Fiecare traficant este definit de o pereche de oraşe (u, v) după cum urmează: traficantul călătoreşte, începând cu momentul de timp 0, de la oraşul u spre oraşul v, pe cel mai scurt drum. În fiecare moment de timp, fiecare traficant livrează o unitate de marfă, după care se duce la următorul oraş.

Traficanţii lui Pablo nu sunt uşor de urmărit: după ce un traficant ajunge la destinaţia lui v şi livrează marfa, în următorul moment acesta se teleportează înapoi în u (dacă la timpul t el livrează marfă în v, la t + 1 va livra în u). Deoarece afacerea se tot dezvoltă şi ar fi păcat ca Pablo să o oprească, traficanţii îşi vor continua rutele pentru totdeauna.

Deşi sistemul aranjat de Pablo pare imposibil de spart, el se întreabă dacă este loc de îmbunătăţiri. Aşadar, el va face 3 tipuri de queryuri asupra sistemului:

  • 1 u v: Adaugă traficant care călătoreşte între perechea de oraşe (u, v).
  • 2 u v: Scoate un traficant care călătoreşte între perechea de oraşe (u, v). Se garantează ca există un astfel de traficant.
  • 3 u v t1 t2: Pablo vrea să ştie câte unităţi de marfă sunt livrate în total, în toate oraşele de pe cel mai scurt drum dintre u şi v inclusiv, între momentele de timp t1 şi t2 inclusiv.

Date de intrare

Fişierul de intrare traffickers.in conţine pe prima linie N, numărul de oraşe. Urmatoarele N - 1 linii conţin 2 numere u şi v, semnificând că există un drum direct între oraşele u şi v.
Pe următoarea linie este K, numărul de traficanţi prezenţi iniţial în reteaua lui Pablo. Următoarele K linii conţin fiecare câte 2 numere u şi v, perechea de oraşe care defineşte drumul unui traficant.
Următoarea linie îl conţine pe Q, numarul de queryuri pe care Pablo vrea sa le facă. Fiecare din următoarele Q linii conţine câte un query in formatul menţionat mai sus.

Date de ieşire

În fişierul de ieşire traffickers.out se vor afişa răspunsurile queryurilor de tip 3, fiecare pe câte o linie nouă.

Restricţii

  • 1 ≤ N ≤ 30 000
  • 0 ≤ K ≤ 50 000
  • 1 ≤ Q ≤ 50 000
  • 0 ≤ t1 ≤ t2 ≤ 2 000 000
  • Drumul fiecărui traficant acoperă maxim 20 de oraşe (incluzând capetele).
  • Pentru 15% din teste, N ≤ 1 000; K, Q ≤ 500; 0 ≤ t1 ≤ t2 ≤ 10.
  • Pentru 45% din teste, N ≤ 10 000; K, Q ≤ 5 000.

Exemplu

traffickers.intraffickers.out
5
1 2
2 3
2 4
1 5
1
4 1
3
3 3 5 0 3
1 2 5
3 4 5 1 5
2
10

Explicaţii

Traficantul 1 livrează 2 unităţi de marfă pe drumul 3-2-1-5 între timpii 0 şi 3:
- în oraşul 2 la timpul 1,
- în oraşul 1 la timpul 2.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?