題目鏈接：點擊查看

題目大意：給出一棵有根樹，根節(jié)點為點 1 ，每個節(jié)點都有一個權(quán)值 val 和兩個屬性 b , c ，屬性 b 和 c 的權(quán)值非 0 即 1 ，現(xiàn)在可以進(jìn)行的操作是，選擇一個節(jié)點 x ，再從子樹中任選 k 個結(jié)點，將這 k 個結(jié)點的屬性 b 重新分配，代價為 val[ x ] * k ，問讓所有節(jié)點的屬性 b 都等于屬性 c 的最小花費是多少

題目分析：拖了三天的題解，這兩天被比賽，期末答辯還有數(shù)模測試折磨的不成人樣了，終于有時間再來做做題目，寫寫博客放松一下了

首先對于這棵樹，自上而下維護(hù)一下點權(quán)的最小值，因為節(jié)點 fa 是節(jié)點 u 的祖先，如果 val[ u ] > val[ fa ] ，因為 u 的子樹也肯定是 fa 的子樹，那么顯然在?fa 選擇原本打算在?u 需要選擇的 k 個結(jié)點更優(yōu)，所以不妨直接將 val 維護(hù)為祖先的最小值

這樣自底向上統(tǒng)計子樹中有多少個 0 需要變成 1 ，記為 c0 ，同理統(tǒng)計 c1 為有多少個 1 需要變成 0 ，然后貪心交換就好了

注意特判一下，如果 b 和 c 中 0 1 的數(shù)量不相等，直接輸出 -1 即可

因為 pair 不支持加法，所以我自己寫了一個結(jié)構(gòu)體代替 pair，并且重載了加法和減法，還是比較方便的

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;struct Node {int a,b;Node(){a=b=0;}Node(int a,int b):a(a),b(b){}Node operator+(const Node& t)const{return Node(a+t.a,b+t.b);}Node operator-(int val)const{return Node(a-val,b-val);}int get_min(){return min(a,b);} };int a[N],b[N],c[N];vector<int>node[N];LL ans=0;Node dfs(int u,int fa) {Node temp;if(b[u]!=c[u]){if(b[u]==1)temp.a++;elsetemp.b++;}for(auto v:node[u]){if(v==fa)continue;a[v]=min(a[v],a[u]);temp=temp+dfs(v,u);}int mmin=temp.get_min();temp=temp-mmin;ans+=2LL*mmin*a[u];return temp; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,c0=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d%d",a+i,b+i,c+i);c0+=(b[i]==0)-(c[i]==0);}for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}if(c0)return 0*puts("-1");dfs(1,-1);printf("%lld\n",ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1363E Tree Shuffling(树上贪心)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。