树形国

【问题描述】

一个国家有n个城市,城市间恰有n-1条道路将城市连接起来,使n个城市构成一棵树。现在需要选取一些城市作为国家直接管理的城市,但这些城市中不能有两个城市有道路直接相连,否则会发生冲突。国王希望选取的城市人口之和要最大,并且想知道有多少种方案可以达到最大人口之和。

【输入格式】

第一行一个数n。
接下来n行,每行两个数f[i]与a[i],f[i]表示第i个城市的父亲城市,若f[i]为0,则表示该城市为根,a[i]表示该城市的人口数。

【输出格式】

第一行一个数,表示最大的人口和。
第二行一个数,表示方案总数 mod 26457的结果。

【数据范围】

1≤a[i]≤10000
对于20%的数据:n≤20
对于100%的数据:n≤200000

【题解】

裸裸的树形DP

记一下取/不取该点的最大值及个数就可以了

按深度从下往上更新

说点什么

您将是第一位评论人!

提醒
wpDiscuz