欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-02 22:37:38
...

Description

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

Solution

  • 首先,问有几次操作等价于问有几条路径
  • 显然我们只需要关心路径的起讫点
  • 路径数为起讫点数/2
  • 如图
    2020牛客多校第十场C-Decrement on the Tree
  • 如图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);
	}		
}