2020牛客暑期多校第十场 C - Decrement on the Tree（树的思维好题）

传送门

题目大意：给出一棵生成树，每条边都有一个权值，现在每次操作可以任意选择两点间的一条路径然后将这条路径的权值都减一，问最少多少次能将所有边权值都减小到0。除此之外还问如果修改了某条边的权值，这个最小的次数是多少

看到本题突然想到了这次杭电有场题很类似，那道题是并查集写的，而且给出的是每个点的权值。而本题最大的难点是修改后最多$logn$求出更新后的答案，也就是每次$O(n)$求是不允许的

自己没有想出来，但是看到正解的神奇之处也是五体投地

首先我们模拟一下样例的操作过程：

对于每次的操作我们可以通过考虑每点被操作多少次，那么最终的答案就是总的点数除以二

然后本题有一个很重要的结论：

如果一个点连接的边中，最大权值大于等于这个点连接的边权总和的一半，那么这个点所连接的这些边需要多操作2*maxval-sum；如果最大权值小于这个点连接的边权总和的一半，那么只需要判断总和是否为奇数，如果为奇数则需要再操作一次

因为要保证消的最多，那么每次找一个节点出发的最长路径，消去这条路径的最小值。或者说最优的路径选择一定会是从一个叶子节点出发然后再到另一个叶子节点结束，然后每次都会再从最小的节点处断开形成新的叶子节点。因此叶子节点处一定是满足最大权值大于等于边权总和的一半，也就是直接加上了这个权值。至于中间的节点，如果最大权值小于边权总和的一半，如果为偶数就可以相互抵消，如果为奇数只需多操作一次，这是在叶子节点连接的路径上相互抵消后剩下一次需要操作。然后就是中间节点最大权值大于等于边权总和的一半时，因为小于它的其他部分肯定都会经过最大权值然后消去，那么剩下的就只需要加上一次$2\ast maxval-sum$

可以以这个图为例，直接计算和标答算出的都是恰好需要$6$次，深入理解一下上述结论的正确性（蒟蒻不会证明）：

最大权值我们可以维护一个$multiset$，$logn$查询最大值

最后就是修改了，显然只修改一条边只影响周围的边，即影响该点的操作次数，那么减去原来的，再加上更改后的即可$O(logn)$查询，修改和插入

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=1e5+10;

struct node{
    int u,v;
    ll w;
}a[maxn];

multiset<ll,greater<ll>> s[maxn];
ll sum[maxn];

ll cal(int pos){
    ll cur=*s[pos].begin();
    
    if(cur*2>=sum[pos]) return cur*2-sum[pos];
    return sum[pos]&1;
}


int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,q,p;
    ll ans=0,w;
    cin>>n>>q;
    for(int i=1;i<n;i++){
        cin>>a[i].u>>a[i].v>>a[i].w;
        sum[a[i].u]+=a[i].w,sum[a[i].v]+=a[i].w;
        s[a[i].u].insert(a[i].w);
        s[a[i].v].insert(a[i].w);
    }
    for(int i=1;i<=n;i++){
         ans+=cal(i);
            cout<<cal(i)<<endl;
    }
    cout<<ans/2<<"\n";
    while(q--){
        cin>>p>>w;
        ans-=cal(a[p].u)+cal(a[p].v);
        sum[a[p].u]-=a[p].w,sum[a[p].v]-=a[p].w;
        s[a[p].u].erase(s[a[p].u].find(a[p].w));
        s[a[p].v].erase(s[a[p].v].find(a[p].w));
        a[p].w=w;
        sum[a[p].u]+=w,sum[a[p].v]+=w;
        s[a[p].u].insert(w);
        s[a[p].v].insert(w);
        ans+=cal(a[p].u)+cal(a[p].v);
        cout<<ans/2<<"\n";
    }
    return 0;
}