2020牛客暑期多校训练营（第十场）C Decrement on the Tree —— 思维，边访问转换为点访问，有丶东西

本文主要是介绍2020牛客暑期多校训练营（第十场）C Decrement on the Tree —— 思维，边访问转换为点访问，有丶东西，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

现在有一棵树，每条边都有一个权值，现在你每次可以选择两个点使得路径上的所有边的权值-1，问你最少需要操作几次。并且依次做m个操作，每次都将一条边的权值改变，并且求最少操作次数。

题解：

在赛场上我就想着DP，树剖什么的，但是搞不出来。这想法有丶东西，由于将一条边的权值-1，那必然要将它连接的两个点访问一次。那么这道题可以变成：最少的访问点的次数。
那么假设一个点连了一条边，它访问次数就是这个边权。
如果连了多条边，那么可以知道如果和这个点相连的边的最大值*2>边的权值和，那么最大的这条边是无法被消掉的，所以这个点要多访问mx*2-v[i]次。否则，就有可能相互消掉，判一下总和的奇偶性即可。
最后由于每条边会被算两次，那么答案/2
tql/QAQ.jpg

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
int x[N],y[N];
ll w[N],v[N];
multiset<ll,greater<ll> >s[N];
ll cal(int i){ll mx=*s[i].begin();if(mx*2>v[i])return mx*2-v[i];return v[i]%2;
}
int main()
{int n,m;scanf("%d%d",&n,&m);ll ans=0;for(int i=1;i<n;i++){scanf("%d%d%lld",&x[i],&y[i],&w[i]);v[x[i]]+=w[i],v[y[i]]+=w[i];s[x[i]].insert(w[i]),s[y[i]].insert(w[i]);}for(int i=1;i<=n;i++)ans+=cal(i);printf("%lld\n",ans/2);while(m--){int p;ll nv;scanf("%d%lld",&p,&nv);ans-=cal(x[p])+cal(y[p]);v[x[p]]-=w[p],v[y[p]]-=w[p];s[x[p]].erase(s[x[p]].find(w[p]));s[y[p]].erase(s[y[p]].find(w[p]));w[p]=nv;v[x[p]]+=w[p],v[y[p]]+=w[p];s[x[p]].insert(nv);s[y[p]].insert(nv);ans+=cal(x[p])+cal(y[p]);printf("%lld\n",ans/2);}return 0;
}