题意：
【DFS|CodeForces - 1099D（树上贪心+DFS）】给出一棵有根树，根节点编号为 1，每个节点存在一个权值 a[x]，同时还有一个 s[x]为从根节点到节点 x 这条路径上的所有节点的 a[x]之和。此时，擦除了所有深度为偶数的节点的 s[x]（根节点深度为 1）。然后要求反推出所有节点的 a[x]，使得所有节点的 a[x]之和最小。
思路：
对于叶子结点来说，权值为0就行。对于s为-1的结点来说，a[x]=s[fa]-s[x]，要使得a[x]最小，那么s[x]要最大，但最大不能超过x的子结点的所有的s，所以s[x]=min(s[g[x][i])。对于s已经确定的结点来说，a[x]=s[fa]-s[x]即可。
#include
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int maxn=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
vector g[maxn];
int s[maxn],a[maxn],flag=1;
void dfs(int x,int fa)
{
if(!flag)
return ;
if(s[x]==-1)
{
if(g[x].empty())
{
s[x]=s[fa],a[x]=0;
return ;
}
int mn=inf;
for(int i=0;
in;
for(int i=2;
i<=n;
i++)
{
int p;
cin>>p;
g[p].push_back(i);
}
for(int i=1;
i<=n;
i++)
cin>>s[i];
s[0]=0;
flag=1;
dfs(1,0);
if(!flag)
{
cout<<-1<
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 遇见蓝桥遇见你|小唐开始刷蓝桥（一）2020年第十一届C/C++ B组第二场蓝桥杯省赛真题
- 题库-CF|【Codeforces Round 263 (Div 2)C】【贪心 哈弗曼思维】Appleman and Toastman 每个非1size子树延展为2子树的最大权
- Codeforces|Codeforces Round #643 (Div. 2) B.Young Explorers
- DFS|使用DFS（深搜）遍历所有的序列所有的子组合（子序列）（排列组合中的组合）
- ZOJ-3447---Doraemon's Number Game (贪心+大数）
- Pavel loves grid mazes（CodeForce 377A）
- CodeForces 567A Lineland Mail 贪心
- codeforces|Codeforces Round #643 (Div. 2) D. Game With Array (思维，贪心)
- Codeforces Round #643 (Div. 2) B. Young Explorers 题解（贪心）
- CodeForces - 1060D E - Social Circles