https://pintia.cn/problem-sets/994805046380707840/exam/problems/1649748772845703169
当时比赛的时候想到方法的 结果时间不够了.... 后面一遍就过了 挺可惜的吧
分析：
分情况
如果子树大小为偶数 这样里面一定是一半0 一半1
如果子树大小为奇数 可能0比1多一个 或者1比0多一个
设dp[u][0/1]分别表示 u子树0比1多一个的最小代价 和1比0多一个的最小代价
设v是u的亲儿子 如果v子树大小为偶数 则不用管他了 累计答案 对u造成不了影响
现在考虑奇数 每个v有dp[v][0] 和dp[v][1] 这样两种状态 怎样选择才能最小代价
这是一个很经典的问题
考虑我们都先选择0即：dp[v][0] 然后将选择1的代价改为：dp[v][1]-dp[v][0]
res=Σdp[v][0]
这样只需要将选择1的数组排序取前一半+res即可表示最小代价了
最后如果1节点子树大小不是偶数 要么要取min(dp[u][0],dp[u][1])
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
void solve();
const int maxn=1e5+5;
int n,ans;
int c[maxn],p[maxn],dp[maxn][3];
vector<int>Q[maxn];
void dfs(int);
int main(){
solve();
return 0;
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>c[i]>>p[i];
int k;cin>>k;
for(int j=1;j<=k;j++){
int x;cin>>x;
Q[i].push_back(x);
}
}
dfs(1);
if(dp[1][2]!=1e9+7)
ans+=min(dp[1][0],dp[1][1]);
cout<<ans<<endl;
}
void dfs(int u){
for(int i=0;i<Q[u].size();i++){
int to=Q[u][i];
dfs(to);
}
vector<int>G;
int res;
if(c[u]!=0)res=p[u],G.push_back(-p[u]);
else res=0,G.push_back(p[u]);
for(int i=0;i<Q[u].size();i++){
int to=Q[u][i];
if(dp[to][2]==1e9+7)continue;
res+=dp[to][0];
G.push_back(dp[to][1]-dp[to][0]);
}
int sz=G.size();
sort(G.begin(),G.end());
int tot=0;
for(int i=0;i<sz/2;i++)
tot+=G[i];
if(sz&1){
dp[u][0]=res+tot;
dp[u][1]=dp[u][0]+G[sz/2];
}else{
dp[u][2]=1e9+7;
ans+=res+tot;
}
}