Decrement on the Tree

我们发现有几次操作就是覆盖几条路径，所以我们只要关注路径的起点和终点，路径数就是起点终点的数量和的一半
如果有一边的权值很大，超过了其他所有边的权值和，必然会出现某条边非常多的情况，起点和终点的数量就为这条边的数量乘2 。
代码：

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