E. Археологи

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

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

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

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

Та Номхон далайн нэгэн арал дээр байгаа судлаачдын багт туслах хэрэгтэй болжээ. Тэд олон жилийн өмнө энэ арал дээр оршин суудаг байсан эртний овог аймгуудын соёлыг судалж байгаа юм.

Судлаачид нийтдээ $n$ тооны тосгоныг ухаж гаргачихаад байгаа. Зарим $2$ тосгод хоорондоо замаар холбогдсон байжээ. Энэ замаар нь ирж, очиж болдог буюу эдгээр нь $2$ чиглэлт зам байв. Тэнд нийтдээ яг $n-1$ тооны зам байсан бөгөөд аль нэг тосгоноос өөр аль ч тосгонд хүрэх боломжтой байв.

Овог аймгууд тийм ч амар тайван амьдардаггүй байсан бөгөөд олон дайн болж өнгөрчээ. Эдгээр дайны үр дүнд зарим тосгод бүрмөсөн устаж үгүй болсон ба хамгийн амар тайван жилүүдэд зарим тосгодыг дахин сэргээсэн байв.

Аль ч цаг үед хүмүүс тухайн цаг үед оршиж байсан $2$ тосгоны хоорондох хамгийн богино замыг ашигладаг байв. Өөрөөр хэлбэл, оршиж байгаа аль нэг тосгоноос өөр нэгэн рүү нь очих боломжтой замуудаас хүмүүс хамгийн богиныг нь ашигладаг байжээ. Арлын бүхий л хугацааны түүхийн турш тэнд судлаачдын тогтоосноор яг $n-1$ тооны зам байсан ба өөр ямар ч зам байгаагүй болохыг анхаараарай.

Судлаачид өөр өөр цаг үед ашиглагдсан замын уртын нийлбэрийг ажиглах нь овог аймгуудын соёлыг ойлгоход дөхөм болох төдийгүй хэд хэдэн түүхийн чанартай асуултуудад хариулт өгөхөд тусалж чадна гэж бодож байгаа юм.

Танд овог аймгуудын оршин тогтнолын бүрэн түүх өгөгдөх бол зарим цаг үеийн ашиглагдсан нийт замын уртыг тогтоож өгнө үү.

Оролт

Эхний мөрөнд тосгодын тоог харуулах $n$ ($1≤n≤10^{5}$) бүхэл тоо өгөгдөнө. Дараагийн $n-1$ мөрүүд нь замыг илэрхийлнэ. Эдгээр мөрүүдийн $i$-р мөрөнд $i$-р замаар холбогдсон тосгодын дугаар болон замын уртыг харуулах $a_{i}$, $b_{i}$, $c_{i}$ ($1≤a_{i}, b_{i}≤n$, $a_{i}≠b_{i}$, $1≤c_{i}≤10^{9}$, $1≤i

Дараагийн мөрөнд хүсэлтүүдийн тоог харуулах $q$ ($1≤q≤10^{5}$) бүхэл тоо өгөгдөнө. Хүсэлтүүд нь цаг хугацааны дарааллаараа тус бүртээ нэг мөрөнд өгөгдөнө. Хүсэлтүүд нь дараах 3 төрлийн аль нэгт хамаарна:

  • "+ x" - $x$ дугаартай тосгоныг сэргээсэн ($1≤x≤n$).
  • "- x" - $x$ дугаартай тосгоныг устгасан ($1≤x≤n$).
  • "?" - тухайн цаг үед ашиглагдаж байсан нийт замын уртыг археологичид мэдэхийг хүсч байгаа.

Хүсэлтүүд нь логик алдаагүй буюу оршдоггүй тосгоныг устгах эсвэл оршиж байгаа тосгоныг дахин сэргээх хүсэлт байхгүй гэдэг нь илэрхий юм. Мөн бидэнд "?" төрлийн дор хаяж $1$ хүсэлт байна. Аль нэг тосгоноос өөр нэг тосгон руу өгөгдсөн замаар явах боломж мөн үргэлжид байна.

Цаг хугацааны эхэнд ямар ч тосгон байхгүй гэж үзнэ.

Гаралт

"?" төрлийн хүсэлт бүрд ашиглагдаж байсан замуудын нийт уртыг нэг мөрөнд хэвлээрэй. Хүсэлтийн хариултуудыг оролтонд өгөгдсөн дарааллаар хэвлээрэй.

С++ хэлэнд $64$ битийн бүхэл тоог унших, бичихдээ %lld тодорхойлогчийг битгий ашиглаарай. Харин %I64d тодорхойлогчийг эсвэл cin, cout урсгалуудыг ашиглах нь дээр байдаг.

Орчуулсан: Солонго

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

Оролт
6
1 2 1
1 3 5
4 1 7
4 5 3
6 4 2
10
+ 3
+ 1
?
+ 6
?
+ 5
?
- 6
- 3
?
Гаралт
5
14
17
10
Сэтгэгдлүүдийг ачааллаж байна...