C.Decrement on the Tree .2020牛客暑期多校训练营（第十场）

题意

给你一棵树，有n个顶点和n-1条边，每条边都有一个非负的权值。每次你可以选择两个连通的顶点u,v,将这两点间路径上的每一条边的权值减去1，问最少需要多少次操作，才能让所有的边权都变成0。
你还需要改变边权：将第p条边的权值改成w，你需要输出每一次改变后的答案。

输入：第一行有两个整数n,q。
接下来n-1行，每行三个整数u,v,w,代表顶点为u,v的边权值为w，每条边按输入顺序标记成第1到第n-1条边。
接下来的q行，每行有两个整数p,w。

输出：输出答案，q+1个整数

---

解题思路

计算最小操作数

由于每次选择一条路径进行操作，要求最少的操作数，那么就相当于选择的路径数量越少越好，两个端点构成一条路径，因此可以通过计算最少端点数/2来计算路径。
怎么计算最少端点数呢，那就可以分别计算每个顶点最少需要当几次端点，然后把次数加起来。 设一个顶点x所连的边的最大权值为max；所连的边权和为sum；将顶点所连边权和减到0，顶点x最少需要当num次端点，则：

• 如果max<=sum-max(最大边权值小于其它边权和)，说明大部分边都可以完成两两匹配，每匹配两条边sum-2。当边权和为偶数的时候，一定能够匹配完，也就是x可以不作为端点。而奇数的时候会剩一条路径一定要以x为端点。此时num=sum%2。
• 如果max>sum-max,说明最大边跟其它边匹配完后还有剩2*max-sum的权值，因此顶点至少要做2*max-num次端点。

(丑！！！qwq)
举个栗子，上图可以看到顶点1最少需要做5次端点，顶点2要做2次，顶点3要做2次，顶点4要做1次。要让端点数最少就要尽量让多个边连成一条路径，中间的点就可以不做端点了。

修改边权（multiset)

由上面的结论可以知道我们需要每个顶点的sum和max，而修改一条边的权值需要改变这条边连接的两个顶点的sum和max。
我们需要快速地找到这条边的边并对它的顶点性质和权值进行操作。这个时候就要用到multiset，multiset跟set一样可以将每个元素进行排序，不同的是multiset可以存放重复元素。multiset还有一个优势是删除和添加元素的复杂度在（logn)
创建一个multiset数组node,将顶点x所连的每条边的权值添加进node[x],每当要修改的时候就将旧权值删掉，并添加新权值，还可以方便地从队尾拿到最大值。

---

代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
#define maxvex 100010
int list[maxvex * 2];
ll weight[maxvex];
multiset<ll>nodeWeight[maxvex];
struct Node
{
	ll sum;
	ll max;
}point[maxvex];
ll Calculate(int i)
{
	ll numNode;
	if (point[i].max > point[i].sum-point[i].max)
	{
		numNode = point[i].max * 2 - point[i].sum;
	}
	else
	{
		numNode = point[i].sum % 2;
	}
	return numNode;
}
int main()
{
	int n, q;
	long long numNode = 0;
	scanf("%d %d", &n, &q);
    if(n==1){puts("0");while(q--) puts("0");return 0;}
	for (int i = 0; i<n - 1; i++)
	{
		int x, y;
        ll w;
		scanf("%d %d %lld", &x, &y, &w);
		list[i * 2] = x;//list按顺序存放每条边的两个顶点
		list[i * 2 + 1] = y;
		nodeWeight[x].insert(w);
		nodeWeight[y].insert(w);
		weight[i] = w;//weight存放第i条边权值
		point[x].sum += w;
		point[y].sum += w;
		point[x].max = max(point[x].max, w);
		point[y].max = max(point[y].max, w);
	}
	for (int i = 1; i <= n; i++)
	{
		numNode += Calculate(i);//计算每个顶点的最少端点
	}
	printf("%lld\n", numNode / 2);
	for (int i = 0; i<q; i++)
	{
		int idx;
        ll w;
		scanf("%d %lld", &idx, &w);
		int x = list[(idx - 1) * 2];//取出边的两个顶点
		int y = list[(idx - 1) * 2 + 1];
		auto a = nodeWeight[x].find(weight[idx - 1]);//查找到值等于旧边权的元素的位置
		auto b = nodeWeight[y].find(weight[idx - 1]);
		nodeWeight[x].erase(a);//通过这个位置把这个旧边权删掉
		nodeWeight[y].erase(b);
		nodeWeight[x].insert(w);
		nodeWeight[y].insert(w);
		numNode -= Calculate(x) + Calculate(y);//减去旧的端点数
		auto it = nodeWeight[x].end();
		it--;
		point[x].max = *it;
		it = nodeWeight[y].end();
        it--;//末尾指向最后一个元素的后一个位置，需要减一
		point[y].max = *it;
		point[x].sum += -weight[idx-1] + w;
		point[y].sum += -weight[idx-1] + w;
		weight[idx-1] = w;
		numNode += Calculate(x) + Calculate(y);//加上新的端点数
		printf("%lld\n", numNode / 2);
	}
	system("pause");
	return 0;
}