原题链接：https://ac.nowcoder.com/acm/contest/5675/C

题目描述

有一颗有n个顶点和n-1条边的树，每条边都有非负的权值，每次可以选择两个不同的顶点u,v，并将连接这两个顶点的边的权值减去一。
请问最少要操作多少次才能将所有边的权值变为零。
当然还有另外的一个操作，将第p条边的权值改为w。对于每个这样的操作，您也需要输出一个答案。

输入描述

第一行输入两个整数n,q，分别表示节点数和第二个操作的次数；
接下来n-1行每行输入三个整数u,v,w,分别表示这条边连接的两个顶点和这条边的权值；
最后q行每行输入两个整数p,w，分别表示在该次操作时操作的边的序号和修改后的权值。

输出描述

输出q+1行，分别表示每次需要把边权值变为零的操作步数。

数据范围

样例

• 输入

  5 3
  1 2 3
  1 3 4
  2 4 5
  3 5 6
  1 10
  2 10
  3 10

• 输出

  8
  12
  10
  10

题解思路

首先，这篇题解可能很水，因为我看其他奆佬的代码的时候亿脸懵逼。
看到树上的边权，很容易想到用边权转点权的方法，然后就莫名其妙地想到树链剖分。但请注意，再求答案使用树链剖分会非常麻烦。
再仔细观察题目并细细思考，不难得出，某几次操作是覆盖几条路径，所以我们只需要关注路径的起点和终点，而路径数就是起点和终点的数量和的一半。
当有边的权值过大（超过其他所有边的权值和）时，如下图所示，那么易得出，起点和终点的数量就是这条边的数量的两倍。

当然如果没有这种情况，就像欧拉一笔画问题，边权和为奇数那么就有起点和终点，若为偶数则没有。

参考代码

#include<bits/stdc++.h>
using namespace std;
long long sum[100100],v[100100],w[100100],p[100100],x,y,n,m,i,j,k,l,o;
multiset<long long>s[100100];
multiset<long long>::iterator it;
long long ans;
long long go(long long x)
{
    it=--(s[x].end());
    if (*it>sum[x]-*it) return *it*2-sum[x];
    return sum[x]&1;
}
void Terra(long long i)
{
    ans-=go(i);
    sum[i]+=y-p[x];
    s[i].erase(s[i].find(p[x]));
    s[i].insert(y);
    ans+=go(i);
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for (i=1;i<n;i++)
    {
        scanf("%lld%lld%lld",&v[i],&w[i],&p[i]);
        sum[v[i]]+=p[i];
        sum[w[i]]+=p[i];
        s[v[i]].insert(p[i]);
        s[w[i]].insert(p[i]);
    }
    for (i=1;i<=n;i++)
     ans+=go(i);
    printf("%lld\n",ans/2);
    for (i=1;i<=m;i++)
    {
        scanf("%lld%lld",&x,&y);
        Terra(v[x]);
        Terra(w[x]);
        p[x]=y;
        printf("%lld\n",ans/2);
    }
}