3853: Double Tree
内存限制：512 MB
时间限制：15.000 S
评测方式：文本比较
命题人：
提交：5
解决：1
题目描述
You are given two trees, both with N vertices, numbered from 1 to N.
At the beginning, the weights of edges of both trees and the values of vertices of the first tree are given.
There are Q operations. In each operation, the value of a vertice of the first tree will be modified. Please output max1≤u<v≤n{T1.dis(u,v)+T2.dis(u,v)+val(u)+val(v)} after every operation.
Note that the symbol Tid.dis(u,v) denotes the distance between vertice u and vertice v in the tree id.
Note that the distance between two vertices in some tree is defined as the sum of the weights in the simple path between the two vertices.
Note that the symbol val(u) denotes the value of the vertice u in the first tree.
At the beginning, the weights of edges of both trees and the values of vertices of the first tree are given.
There are Q operations. In each operation, the value of a vertice of the first tree will be modified. Please output max1≤u<v≤n{T1.dis(u,v)+T2.dis(u,v)+val(u)+val(v)} after every operation.
Note that the symbol Tid.dis(u,v) denotes the distance between vertice u and vertice v in the tree id.
Note that the distance between two vertices in some tree is defined as the sum of the weights in the simple path between the two vertices.
Note that the symbol val(u) denotes the value of the vertice u in the first tree.
输入
There are multiple test cases.
Each case starts with a line containing two positive integers N,Q(2≤N≤1e5,1≤Q≤1e5).
The second line contains N integers a1,a2,...,aN(1≤ai≤1e9) denoting the values of vertices of the first tree.
Then follow N−1 lines. Each line contains three integers u,v,w(1≤u,v≤n,1≤w≤1e9) describing the first tree. Namely, u,v,w means that there is an edge weighted w between vertice u and vertice v.
Then follow N−1 lines. Each line contains three integers u,v,w(1≤u,v≤n,1≤w≤1e9) describing the second tree.
Then follow Q lines. Each line contains two integers u,w(1≤u≤n,1≤w≤1e9), denoting the value of vertice u of the first tree will be modified to w.
It is guaranteed that the sum of Ns and the sum of Qs in all test cases are both no larger than 2×1e5.
There is only one test case which contains N and Q that are both larger than 2×1e4.
It is guaranteed that N and Q in every other test case are all no larger than 2×1e4.
Each case starts with a line containing two positive integers N,Q(2≤N≤1e5,1≤Q≤1e5).
The second line contains N integers a1,a2,...,aN(1≤ai≤1e9) denoting the values of vertices of the first tree.
Then follow N−1 lines. Each line contains three integers u,v,w(1≤u,v≤n,1≤w≤1e9) describing the first tree. Namely, u,v,w means that there is an edge weighted w between vertice u and vertice v.
Then follow N−1 lines. Each line contains three integers u,v,w(1≤u,v≤n,1≤w≤1e9) describing the second tree.
Then follow Q lines. Each line contains two integers u,w(1≤u≤n,1≤w≤1e9), denoting the value of vertice u of the first tree will be modified to w.
It is guaranteed that the sum of Ns and the sum of Qs in all test cases are both no larger than 2×1e5.
There is only one test case which contains N and Q that are both larger than 2×1e4.
It is guaranteed that N and Q in every other test case are all no larger than 2×1e4.
输出
For each test case, output Q lines. Each line contains an integer denoting the answer.
样例输入 复制
5 3
1 2 3 4 5
1 2 1
1 3 2
1 4 3
1 5 4
1 2 1
1 3 2
1 4 3
1 5 4
1 100
1 1
2 100
样例输出 复制
113
23
115