题意
给一棵$n$节点的树,每个节点有$a[i]$个人住,他们从$1$号节点回家,回家路上可能从开心的状态变成不开心的状态(但不可以由不开心变为开心),每个节点有个探测器,会探测经过该节点开心的人数减不开心的人数,而预期值为$h[i]$,问是否可能存在一种情况,使得所有节点的探测值等于真实值
分析
先想一下思路:我们可以发现叶子节点的人数开心人数和不开心人数,开心人数一定是从$1$号节点一直开心走回家的,不开心的人可能在路中间是开心的,那么我们不妨将题目转换为每个人从家出发到$1$号节点,他可能一开始是不开心的,他可以从不开心变为开心,但不会从开心变为不开心,那么对于一个节点,统计它的儿子节点的开心人数和不开心人数,然后不妨设该节点的所有人都是不开心,设$x$为开心的人数,$y$为不开心的人数,$tot$为经过该节点的总人数那么有方程
然后判断即可
1 |
|