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

题目大意

有一棵包含n个顶点（n-1条边）的带边权的树，每次都可以选择两个不同的顶点，将这条链上每个边权值减去1。
要使所有边权值为零，最小操作数是多少？
还需要支持边权的修改：将第p个边的权重更改为w，每次修改后都要输出答案。

解题思路

没有图示，我很抱歉！我会尽量清楚地叙述一下这个做法的原理。（刚才我题解也看的很懵）。

转换题意

看到在带边权的树上操作，我们一个惯用的套路就是：边权转点权。
这里，我们可以把减边权的操作，转化为访问点的操作。当一条边权值减1时，它的两个端点都被访问到1次。
所以我们可以把问题转化为：最少访问多少次，就能所有边权变为0。

每个点的考虑

现在，我们的首要任务，就是找到每个点应该占用几次访问。我们先画图观察每个点，推出一个简单易得的结论：
如果一个点连接的边中，最大权值（在代码中记为y）小于这个点连接的边权总和（d[x]）的一半，那么这个点所连接的这些边可以通过操作变为0。

所以，我们需要判断边权总和d[x]的奇偶：

• d[x]为奇，就只要再访问一次，消去剩余的那1边权；
• d[x]为偶，我们就再加上2*y-d[x]次访问，来消去不能与这个点其他相连的边消去的部分。

解释

• 对于叶子结点，我们一定要访问边权值那么多次（只有一条边），而叶子节点总是满足上方👆最大权值大于边权总和的一半。
• 而对于非叶子节点，因为我们在访问原有的叶子节点时，可能会使一些地方的边权值归0断掉，产生新的叶子节点，所以这是不一定的。
  非叶子节点也有可能在几次操作后变成新的叶子节点，因为叶子节点要访问边权次，所以，对于于非叶子结点：
  • 2y>=d[x]时我们要加上2y-d[x]；
  • 而2y<d[x]时，若d[x]为奇数就+1，因为这个结点在满足以上情况时会在某个时刻变成一个叶子节点，而叶子节点所连的边权需要全部加上。（反复重申）

AC代码

multiset用的时候要小心啊！RE那都是血的教训！

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