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

Description

Solution

• 首先，问有几次操作等价于问有几条路径
• 显然我们只需要关心路径的起讫点
• 路径数为起讫点数/2
• 如图
  
• 如图C情况，当有一条边权值很大，超过其他所有边权和时，必然出现许多像粉色边一样的起讫点，点数为粉边数
• 若没有超过，如AB所示，则像欧拉一笔画问题一样，边权和为奇数则有起讫点，否则没有
• 维护时可以用STL中的multiset方便的查最大值，插入和删除边可以做到优秀的$O(logN)$O(logN)复杂度

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
multiset<ll> s[N];
multiset<ll>::iterator it;
int n,q,a[N],b[N];
ll w[N],sum[N],ans=0;
ll euler(int x)
{
	it=--(s[x].end());
	if(*it>sum[x]-*it) return 2*(*it)-sum[x];
	return sum[x]&1;
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<n;++i)
		scanf("%d%d%lld",a+i,b+i,w+i),
		s[a[i]].insert(w[i]),
		s[b[i]].insert(w[i]),
		sum[a[i]]+=w[i],
		sum[b[i]]+=w[i];
	for(int i=1;i<=n;++i) 
		ans+=euler(i);
	printf("%lld\n",ans/2ll);
	while(q--)
	{
		int p;ll val;
		scanf("%d%lld",&p,&val);
		ans-=euler(a[p])+euler(b[p]);
		s[a[p]].erase(s[a[p]].find(w[p]));
		s[b[p]].erase(s[b[p]].find(w[p]));
		s[a[p]].insert(val);
		s[b[p]].insert(val);
		sum[a[p]]+=val-w[p];
		sum[b[p]]+=val-w[p];
		w[p]=val;
		ans+=euler(a[p])+euler(b[p]);
		printf("%lld\n",ans/2ll);
	}		
}