Decrement on the Tree
题目链接
题目大意
一棵树，每次选一条路径让这条路径上的边权都减一，问最少操作多少次可以让这棵树的边权变成0？
还有m次修改，每次给出x，y把第x条边边权变为y。
每次修改完输出答案是多少。
题解
一直以为是什么数据结构维护之类的。。是我太年轻了
每次选一条边，也就是两个点，让这两个点之间的边权都减一。
然后考虑每个点选几次
如果这个点连的边两两可以匹配，那么就不用选这个点。
怎么确定两两可以匹配完呢？
如果最大值小于总和 - 最大值。就一定可以匹配。当然还要判断一下奇偶的情况。奇数的话 肯定是要选这个点一次的。
如果最大值大于总和 - 最大值，这个点就选2*最大值 - 总和次。
妙啊妙啊
这谁想得到
所以求答案需要维护的值：总和、这条边连的最大值
因为需要修改操作，用个set就好。
代码：
#include<algorithm>
#include<iostream>
#include <cstdio>
#include <string>
#include <queue>
#include <cstring>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef unsigned long long ull;
typedef set<int>::iterator sit;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void tempwj(){freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){a %= mod;ll ans = 1;while(b > 0){if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{bool operator()(const pii & a, const pii & b){return a.second < b.second;}};
int lb(int x){return x & -x;}
//friend bool operator < (Node a,Node b) 重载
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1000000007;
const int maxn = 1e5+10;
const int M = 2e6 + 10;struct cmp2
{bool operator ()(const int& a, const int & b){return a > b;}
};
multiset<int, cmp2> ss[maxn];
ll val[maxn];ll getans(int x)
{int xx = *ss[x].begin();ll y = val[x] - xx;if(xx > y){return xx - y;}else{return val[x] % 2;}
}
struct Edge
{int x,y,v;
}edge[maxn];
int main()
{int n,m;scanf("%d%d",&n,&m);for (int i = 1; i < n; i ++ ){int x,y,v;scanf("%d%d%d",&x,&y,&v);edge[i].x = x;edge[i].y = y;edge[i].v = v;ss[x].insert(v);ss[y].insert(v);val[x] += v;val[y] += v;}ll ans = 0;for (int i = 1; i <= n; i ++ ){ans += getans(i);}printf("%lld\n", ans/2);while(m -- ){int i,y;scanf("%d%d",&i,&y);ans -= getans(edge[i].x);ans -= getans(edge[i].y);val[edge[i].x] -= edge[i].v;val[edge[i].y] -= edge[i].v;ss[edge[i].x].erase(ss[edge[i].x].find(edge[i].v));ss[edge[i].y].erase(ss[edge[i].y].find(edge[i].v));edge[i].v = y;val[edge[i].x] += y;val[edge[i].y] += y;ss[edge[i].x].insert(y);ss[edge[i].y].insert(y);ans += getans(edge[i].x);ans += getans(edge[i].y);printf("%lld\n", ans/2);}
}