D.Decrement on the Tree

给定一颗无根树，有n个结点，n-1条边，每条边有一个权值。
修改操作：选择两个点，两个点之间的最短路径上的边权减一。
询问:将第i条边的权值赋值为x，询问要执行多少次修改操作可以使得所有边权变为零。

分析：修改操作可以看成将树划分成若干条路径。每个点将它所连接的边一一匹配起来。那么我们只需要计算路径的起点和终点个数就可以得到路径的条数。
对于一个点，如果所连接的边中，没有一条边的边权超过连接边的所有边权一半，那么一定可以两两匹配（会根据奇偶性多出至多一条，那么这条边的起点就是该点）.如果超过了一半，那么未匹配的边就是2 * max-sum,这些边的起点就是该点。
修改可以用个set简单维护。

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const int maxn=1e5+10;

multiset<ll> s[maxn];
multiset<ll> :: iterator it;

int n,q,a[maxn],b[maxn];
ll w[maxn],sum[maxn],ans;

ll date( int x )
{
    it=s[x].end();
    --it;
    ll maxn=*it;
    if( maxn*2>sum[x] ) return 2*maxn-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+=date(i);
    }
    printf("%lld\n",ans/2ll);

    while( q-- )
    {
        int p;ll val;
        scanf("%d%lld",&p,&val);
        ans-=date(a[p])+date(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+=date(a[p])+date(b[p]);
        printf("%lld\n",ans/2ll);
    }
}