Description:


PS国是一个拥有诸多城市的大国,国王Louis为城市的交通建设可谓绞尽脑汁。Louis可以在某些城市之间修建道路,在不同的城市之间修建道路需要不同的花费。Louis希望建造最少的道路使得国内所有的城市连通。但是由于某些因素,城市之间修建道路需要的花费会随着时间而改变,Louis会不断得到某道路的修建代价改变的消息,他希望每得到一条消息后能立即知道使城市连通的最小花费总和, Louis决定求助于你来完成这个任务。

Input:


文件第一行包含三个整数 \(N\) , \(M\) , \(Q\) ,分别表示城市的数目,可以修建的道路个数,及收到的消息个数。
接下来 \(M\) 行,第 \(i+1\) 行有三个用空格隔开的整数 \(X_i\) , \(Y_i\) , \(Z_i\) ( \(1\le X_i,Y_i\le n\) , \(0\le Z_i\le 50000000\) ),表示在城市 \(X_i\) 与城市 \(Y_i\) 之间修建道路的代价为 \(Z_i\)
接下来 \(Q\) 行,每行包含两个数 \(k\) , \(d\) ,表示输入的第 \(k\) 个道路的修建代价修改为 \(d\) (即将 \(Z_k\) 修改为 \(d\) )。

Output:


输出包含 \(Q\) 行,第 \(i\) 行输出得知前 \(i\) 条消息后使城市连通的最小花费总和。

Sample Input:


Sample Output:


Hint:


对于20%的数据, \(n\le 1000,m\le 6000,Q\le 6000\)
对于另20%的数据, \(n\le 1000,m\le 50000,Q\le 8000\) ,修改后的代价不会比之前的代价低。
对于100%的数据, \(n\le 20000,m\le 50000,Q\le 50000\)

题解:


一道口胡好题。

题意就是待修改的最小生成树,可以用CDQ分治来做。

考虑对询问进行分治,假设正在处理询问区间 \([l, r]\)

把所有边分为待修改(即在区间 \([l, r]\) 中存在修改)和确定的。考虑把待修改的边权赋值为INF后来做Kruskal,那么仍不能加入最小生成树的确定边一定不能加入最小生成树,直接删除;考虑把待修改的边权赋值为-INF后来做Kruskal,那么仍能够加入最小生成树的确定边一定在最小生成树上,用并查集缩点。

接下来递归处理 \([l, mid]\)\([mid+1, r]\)

可以发现这两种操作后,边数一定不会超过 \((r-l+1)\times 2 - 1\)

\(T(n) = 2\times T(n/2) + O(m\log m)\) ,解得 \(T(n) = O(m\log n \log m)\)