Codeforces Round #646 (Div. 2) E. Tree Shuffling dfs

V2AS问路

Codeforces Round #646 (Div. 2) E. Tree Shuffling dfs

阅读原文时间：2023年07月09日阅读：2

题意：

给你n个节点，这n个节点构成了一颗以1为树根的树。每一个节点有一个初始值bi，从任意节点 i 的子树中选择任意k个节点，并按他的意愿随机排列这些节点中的数字，从而产生k⋅ai 的成本。对于一个节点i你需要将bi改成ci。

这个bi值和ci值的范围是[0,1]

题解：

对于一个节点，如果它的bi==ci，那么我们就不用管它（因为你改变它的值，那么肯定之后还要花费成本再改回来，增加了成本）。那么我们首先找出来一共有多少个节点bi!=ci ，然后总权值肯定是

num1*a1+num2*a2…+numn*an

numi表示从节点 i 的子树中选择任意numi个节点

那么肯定是尽可能在ai的值越小的子树上尽量增加numi的数量，这样总权值肯定最小

cnt0[i]：以i节点为树根的子树，在bi!=ci，bi等于0的数量

cnt1[i]：以i节点为树根的子树，在bi!=ci，bi等于1的数量

那么我们就从树根开始dfs，并且维护一个ai最小值，在dfs过程中记录一下i这个节点的所有子节点上bi!=ci的数量（如果bi!=ci,还要记录一下i这个点的bi值），如果ai等于我们维护的那个ai最小值，那就对这个节点

的2*min(cnt0[i]，cnt1[i])个节点进行排序。然后让cnt1[i]和cnt0[i]都减去min(cnt0[i]，cnt1[i])

最后判断一下cnt1[1]和cnt0[1]是否为0，等于0就代表所有节点bi都等于ci，否则输出-1

代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Mem(a,b) memset(a,b,sizeof(a))
const double II = acos(-1);
const double PP = (II*1.0)/(180.00);
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=2e5+10;
ll a[maxn],b[maxn],c[maxn],cnt0[maxn],cnt1[maxn],sum;
vectorw[maxn];
void dfs(ll x,ll fa,ll minn)
{
minn=min(minn,a[x]);
for(ll i=0;i<w[x].size();++i)
{
ll now=w[x][i];
if(now!=fa)
{
dfs(now,x,minn);
cnt0[x]+=cnt0[now];
cnt1[x]+=cnt1[now];
}
}
if(b[x]!=c[x])
{
if(b[x])
cnt1[x]++;
else cnt0[x]++;
}
if(minn==a[x])
{
ll ans=min(cnt0[x],cnt1[x]);
ans*=2;
//printf("%d %d****\n",ans,a[x]);
sum=sum+ans*a[x];
ans/=2;
cnt0[x]-=ans;
cnt1[x]-=ans;
}
}
int main()
{
ll n;
sum=0;
scanf("%I64d",&n);
for(ll i=1;i<=n;++i)
{
scanf("%I64d%I64d%I64d",&a[i],&b[i],&c[i]);
}
for(ll i=1;i<n;++i)
{
ll u,v;
scanf("%I64d%I64d",&u,&v);
w[u].push_back(v);
w[v].push_back(u);
}
dfs(1,0,INF);
if(cnt1[1] || cnt0[1])
{
printf("-1\n");
}
else printf("%I64d\n",sum);
}

手机扫一扫

移动阅读更方便

你可能感兴趣的文章

Vue源码学习(二):<templete>渲染第一步,模板解析