2020牛客多校十C-Decrement on the Tree

原题链接

意思就是给一颗树，你可以操作若干次，每次操作可使一条路径上经过的边的边权-1，你要使所有边的边权为0，求最小操作次数。完成之后题目还会修改边权，对于每次修改，你需要再次给出答案。

分析

边权转化为点权，不如把减边权的操作转化为增加路径的两个端点的访问次数，那所求即转化为求最少的访问次数。
设一个点为$c$c，$sum$sum为所有与$c$c点连接的边的权值的和。我们用$*t$∗t来保存$sum$sum中最大边权的值。如果$*t>sum-*t$∗t>sum−∗t，其余所有边都与最大边匹配也会剩下$*t*2-sum$∗t∗2−sum的边权失配。当前的点必须作为端点这些次才能把边权减为$0$0，这样$getsum(c)$getsum(c)的值就是$*t*2-sum$∗t∗2−sum。如果$*t<=sum-*t$∗t<=sum−∗t，肯定存在匹配方法使边权两两匹配，只需让$c$c点作为中间点被经过即可，若最大边权为奇数，会有一个边权失配，需以当前点作为端点形成一条路径才行，这样$getsum(c)$getsum(c)的值就是$sum$sum%$2$2。
因为减边减一次增加点访问数是$2$2，所以$总访问数/2$总访问数/2才是真正的结果。
修改边权的操作也很简单，减去边的两个端点在答案中的值，删除边，增加新边再算一次$getsum$getsum就行了。

#include<iostream>
#include<set>
#define ll long long
using namespace std;
const int N=1e5+10;
ll sum[N];
int u[N],v[N],p[N];
int x,y;
multiset<ll>s[N];
ll ans;
ll getsum(ll c)
{
	auto t=--(s[c].end());
	if(*t>sum[c]-*t)return *t*2-sum[c];
	if(sum[c]%2)return 1;
	return 0;
}
void update(int c)
{
	ans-=getsum(c);
	sum[c]+=-p[x]+y;
	s[c].erase(s[c].find(p[x]));
	s[c].insert(y);
	ans+=getsum(c);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,q;
	cin>>n>>q;
	for(int i=1;i<n;i++)
	{
		cin>>u[i]>>v[i]>>p[i];
		sum[u[i]]+=p[i];
		sum[v[i]]+=p[i];
		s[u[i]].insert(p[i]);
		s[v[i]].insert(p[i]);
	}
	for(int i=1;i<=n;i++)
		ans+=getsum(i);
	cout<<ans/2<<'\n';
	for(int i=1;i<=q;i++)
	{
		cin>>x>>y;
		update(u[x]);
		update(v[x]);
		p[x]=y;
		cout<<ans/2<<'\n';
	}
}