c718: 路上的詛咒
Tags :
Accepted rate : 3人/4人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-04-05 22:35

Content

  $\color{black}{\space bert \space}$所在的世界是由$\color{black}{\space N \space}$個點和$\color{black}{\space N-1 \space}$條道路互相連結而成的,而且保證這些點可以互相直接或間接通過這些道路往來。

  $\color{black}{\space bert \space}$常常接到遠征任務,當他每次接到任務時,他會從所在編號是$\color{black}{\space S \space}$的點,出發到任務目標所派遣到的編號是$\color{black}{\space T \space}$的點遠征,遠征完後再原路返回。但事實上遠征並沒有很簡單,每條道路上都會有敵國所佈下的詛咒(沒錯,他們不直接攻打別人),路途上的詛咒必須自己承擔,而每種詛咒都有自己的強度,但$\color{black}{\space bert \space}$也不是好惹的,他每次出征前都會準備不同的防禦用品使他的防禦力變成$\color{black}{\space d \space}$,所以當$\color{black}{\space bert \space}$受到了強度$\color{black}{\space h_i \space}$的詛咒,如果$\color{black}{\space h_i>d \space}$,他就會受到$\color{black}{\space v_i \space}$點量值的傷害,否則他可以完整的抵擋這次詛咒。

  現在你清楚傷害的計算方式了,$\color{black}{\space bert \space}$在給了你道路資訊的同時想多次麻煩你,當他在點$\color{black}{\space S \space}$接到點$\color{black}{\space T \space}$的遠征任務時,若他的防禦力是$\color{black}{\space d \space}$,他將會受到多少傷害量值呢?由於去程跟回程的傷害是一樣的,所以你只需要計算去程的答案就好了。

  噢對了,由於敵國的詛咒是不斷在更新的,所以在$\color{black}{\space bert \space}$的多次詢問當中也會穿插多次的道路詛咒修改。

 

Input

首行有兩個正整數$\color{black}{\space N,Q(1\leq N,Q\leq 10^5) \space}$,代表點的個數和$\color{black}{\space bert \space}$詢問加上修改的總次數。

接下來$\color{black}{\space N-1 \space}$行,第$\color{black}{\space i+1(1\leq i<N) \space}$行有四個正整數$\color{black}{\space a_i,b_i,h_i,v_i(1\leq a_i,b_i,h_i\leq N,1\leq v_i \leq 10^9) \space}$代表第$\color{black}{\space i \space}$條道路連接點$\color{black}{\space a_i,b_i \space}$,且詛咒強度為$\color{black}{\space h_i \space}$,傷害值為$\color{black}{\space v_i \space}$。

接下來$\color{black}{\space Q\space}$行,每行代表一個操作,如果是$\color{black}{\space 0\space S\space T\space d(1\leq S,T\leq N,S\not=T,0\leq d\leq N) \space}$,代表$\color{black}{\space bert \space}$在點$\color{black}{\space S \space}$,他接到點$\color{black}{\space T \space}$的遠征任務,他的防禦力是$\color{black}{\space d \space}$;如果是$\color{black}{\space 1\space x\space h\space v(1\leq x<N,1\leq h\leq N,1\leq v\leq 10^9)\space}$,代表編號$\color{black}{\space x \space}$的道路的詛咒強度被更新成$\color{black}{\space h \space}$、傷害值被更新成$\color{black}{\space v \space}$了。

Output

對於每個遠征任務的詢問,輸出$\color{black}{\space bert \space}$將會受到多少傷害量值於一行。

Sample Input
6 5
1 2 3 7
1 3 1 3
3 4 5 2
3 5 4 5
3 6 2 8
0 1 4 2
0 2 6 2
1 2 4 4
0 1 4 2
0 2 6 2
Sample Output
2
7
6
11
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (10%): 1.2s , <10M
不公開 測資點#1 (11%): 1.2s , <10M
不公開 測資點#2 (6%): 1.2s , <10M
不公開 測資點#3 (6%): 1.2s , <10M
不公開 測資點#4 (11%): 1.2s , <1M
不公開 測資點#5 (8%): 1.2s , <10M
不公開 測資點#6 (8%): 1.2s , <10M
不公開 測資點#7 (13%): 1.2s , <10M
不公開 測資點#8 (13%): 1.2s , <10M
不公開 測資點#9 (14%): 1.2s , <10M
Hint :

  本題共有五組測試題組,條件限制如下所示。每一組可對應到一或多筆測試資料。

測資點$\color{black}{\space 0\sim 1(21\%)\space}$:每個點至多只被兩條道路連接。

測資點$\color{black}{\space 2\sim 3(12\%)\space}$:所有詢問的 $\color{black}{\space d=0 \space}$。

測資點$\color{black}{\space 4(11\%)\space}$:$\color{black}{\space N,Q\leq 5000 \space}$。

測資點$\color{black}{\space 5\sim 6(16\%)\space}$:沒有修改操作。

測資點$\color{black}{\space 7\sim 9(40\%)\space}$:無特別限制。

Tags:
出處:
[管理者:
baluteshih (波路特石)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」