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

2023-10-31 20:08

本文主要是介绍Codeforces E. Tree Shuffling (树 dfs) (Round #646 Div.2),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传送门

题意: 有一棵n个节点的树,每个节点都有其a[i]代价,b[i]现有值,c[i]目标值。每次可以选择一个节点x作为根节点,选其子树的k个节点随机排序以得到目标值,消耗k *a[x]。试问是否可以使得整棵树变成目标值,并输出最小消耗;若不行输出-1.

在这里插入图片描述
思路:

  • 用dfs维护一下子树中 0 -> 1和 1 -> 0的个数, 再用minn维护a[i]的最小值。
  • 可以知道,若子节点比父节点代价小,那肯定以子节点为根消耗最小,所以用dfs来递归就好啦。
  • 若minn == a[i]表示没有比其代价小的父节点, 反之其就不是最优根。每次再减去子树修改的点数s,最后判断一下-1的情况即可。

代码实现:

#include<bits/stdc++.h>
#define endl '\n'
#define null NULL
#define ll long long
#define int long long
#define pii pair<int, int>
#define lowbit(x) (x &(-x))
#define ls(x) x<<1
#define rs(x) (x<<1+1)
#define me(ar) memset(ar, 0, sizeof ar)
#define mem(ar,num) memset(ar, num, sizeof ar)
#define rp(i, n) for(int i = 0, i < n; i ++)
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define pre(i, n, a) for(int i = n; i >= a; i --)
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int way[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
using namespace std;
const int  inf = 0x7fffffff;
const double PI = acos(-1.0);
const double eps = 1e-6;
const ll   mod = 1e9 + 7;
const int  N = 2e5 + 5;int n, ans;
int a[N], b[N], c[N];
int to0[N], to1[N];
vector<int> g[N];void dfs(int u, int y, int minn)
{minn = min(minn, a[u]);for(auto v : g[u]){if(v != y){dfs(v, u, minn);to0[u] += to0[v];to1[u] += to1[v];}}if(b[u] != c[u]){if(b[u] == 1) to0[u] ++;else to1[u] ++;}if(minn == a[u]){int s = min(to0[u], to1[u]);ans += s * 2 * a[u];to1[u] -= s;to0[u] -= s;}
}signed main()
{IOS;cin >> n;for(int i = 1; i <= n; i ++)cin >> a[i] >> b[i] >> c[i];for(int i = 1; i < n; i ++){int u, v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}dfs(1, 1, inf);if(to0[1] || to1[1]) cout << -1 << endl;else cout << ans << endl;return 0;
}

还看见一个大佬的代码比较简洁。

这篇关于Codeforces E. Tree Shuffling (树 dfs) (Round #646 Div.2)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/317795

相关文章

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵,求由多少个由连续6个元素组成的不一样的字符的个数。 解析: dfs + set去重搞定。 代码: #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

ural 1149. Sinus Dances dfs

1149. Sinus Dances Time limit: 1.0 second Memory limit: 64 MB Let  An = sin(1–sin(2+sin(3–sin(4+…sin( n))…) Let  Sn = (…( A 1+ n) A 2+ n–1) A 3+…+2) An+1 For given  N print  SN Input One

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn

树(Tree)——《啊哈!算法》

树 什么是树?树是一种特殊的图,不包含回路的连通无向树。 正因为树有着“不包含回路”这个特点,所以树就被赋予了很多特性。 一棵树中的任意两个结点有且仅有唯一的一条路径连通。一棵树如果有n个结点,那么它一定恰好有n-1条边。在一棵树中加一条边将会构成一个回路。 一棵树有且只有一个根结点。 没有父结点的结点称为根结点(祖先)。没有子结点的结点称为叶结点。如果一个结点既不是根结点也不是叶