胶州做网站的,河南省建筑信息平台,遂溪网站建设公司,专业网站网站设计BZOJ_2197 如果子树中有某个节点不符合要求#xff0c;即便根再怎么符合要求都是没有任何意义的#xff0c;因此要优先安排好子树中节点使其符合要求#xff0c;再考虑根节点。对于任何一棵子树来讲#xff0c;如果所有孩子选择的点的总和仍然不足根的C值的话#xff0c;那…BZOJ_2197 如果子树中有某个节点不符合要求即便根再怎么符合要求都是没有任何意义的因此要优先安排好子树中节点使其符合要求再考虑根节点。对于任何一棵子树来讲如果所有孩子选择的点的总和仍然不足根的C值的话那么就还要在孩子中选出一些节点而且如果要选那么必然应该选T最小的点。 #includestdio.h
#includestring.h
#includealgorithm
#define MAXD 100010
#define MAXM 100010
typedef long long LL;
int N, first[MAXD], e, next[MAXM], v[MAXM], c[MAXD], t[MAXD];
LL ANS, size[MAXD];
void add(int x, int y)
{v[e] y;next[e] first[x], first[x] e ;
}
void init()
{int p;memset(first, -1, sizeof(first[0]) * (N 1)), e 0;for(int i 1; i N; i ){scanf(%d%d%d, p, c[i], t[i]);if(p ! -1) add(p, i);}
}
int dfs(int cur)
{int min t[cur];size[cur] 0;for(int i first[cur]; i ! -1; i next[i]){min std::min(min, dfs(v[i]));size[cur] size[v[i]];}if(size[cur] c[cur])ANS (c[cur] - size[cur]) * min, size[cur] c[cur];return min;
}
void solve()
{ANS 0;dfs(1);printf(%lld\n, ANS);
}
int main()
{while(scanf(%d, N) 1){init();solve();}return 0;
} 转载于:https://www.cnblogs.com/staginner/archive/2012/09/29/2708900.html
