作者：滴滴答2502906673 | 来源：互联网 | 2023-10-10 21:27
Decrement on the Tree
题目描述
样例 input: output:
题目大意 给你一棵树，现在你可以选择其中的一条链，将其边上的权值都减一。并且每条边的权值不能为负数。要求最少要删除多少次(每次只能减一)，才能使得整棵树的权值都是0。(只需要输出答案，而不是修改)q q
首先看到题目有一种树剖的感觉，但是显然，求答案时无法很好地用树剖解决。
所以这题应该是要维护每条边的权值。我们不妨思考一下求答案的过程实际是什么。实际就是找最少的链将树覆盖，然后每条边的重叠次数都有限制。
如果出现图三的情况，即一个点相连的边的权值中M a x M a x M a x Max M a x M a x Max M a x M a x − O t h e r s Max-Others M a x − O t h e r s 如果图二的情况，即没有一条边是大于其他边权和(虽然上图也是，但是请假装2不大于1:))，那么就要考虑欧拉回路的知识，如果是奇数，那么肯定有一个端点，如果是图一一样的偶数，那么可以做到这个点上没有端点。 那么用上述的方法可以求得整棵树上的端点个数，那么除以2就是链的个数了。
然后考虑修改的操作，我们只要维护一个m u l t i s e t multiset m u l t i s e t S T L STL S T L
#include #define ll long long using namespace std; const int MAXN= 1e5 + 10 ; [ MAXN] , sum[ MAXN] , ans= 0 ; < ll, ll> edge[ MAXN] ; < ll> du[ MAXN] ; < ll> :: iterator it; getnum ( int x) { it= -- ( du[ x] . end ( ) ) ; if ( * it> sum[ x] - * it) return * it- ( sum[ x] - * it) ; return sum[ x] & 1 ; } void update ( int id, int x, ll w) { ans- = getnum ( x) ; du[ x] . erase ( du[ x] . find ( len[ id] ) ) ; du[ x] . insert ( w) ; sum[ x] = sum[ x] - len[ id] + w; ans+ = getnum ( x) ; } int main ( ) { ll n, q, id, u, v, w; scanf ( "%lld%lld" , & n, & q) ; for ( int i= 1 ; i< n; i++ ) { scanf ( "%lld%lld%lld" , & u, & v, & w) ; edge[ i] = make_pair ( u, v) ; len[ i] = w; du[ u] . insert ( w) ; du[ v] . insert ( w) ; sum[ u] + = w; sum[ v] + = w; } for ( int i= 1 ; i<= n; i++ ) ans+ = getnum ( i) ; printf ( "%lld\n" , ans/ 2 ) ; while ( q-- ) { scanf ( "%lld%lld" , & id, & w) ; ll u= edge[ id] . first, v= edge[ id] . second; update ( id, u, w) ; update ( id, v, w) ; len[ id] = w; printf ( "%lld\n" , ans/ 2 ) ; } }
END m u l t i s e t multiset m u l t i s e t
京公网安备 11010802041100号