锐客网

  1. 首页 > it技术 > >

DFS|CodeForces - 1099D（树上贪心+DFS）

DFS贪心

题意：
【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<

    推荐阅读


    上一篇：清除服务器缓存办法

    下一篇：mybatis_generator