P1051 · OFFICIAL SOLUTION

P1051 树的价值官方题解

Gioush OJ · P1051 树的价值

树的价值

【题意简述】

给定一棵以 $1$ 为根的树。每次按照某个顺序探索一个尚未探索的叶子，从根到该叶子的路径上新出现的结点构成一条链。若这条链的最高结点为 $t$ 、长度为 $l$ ，则产生价值 $a_tb_l$ 。求遍历全部叶子时能够得到的最大总价值。

【数据点 1∼21\sim 21∼2】

【题目描述】

这一档保证 $n\leq 7$ 。

【Hint】

枚举全部叶子的排列，并按照题意模拟探索过程。

【解法】

用标记数组维护已经探索的结点。加入一个叶子时，从它向根跳父亲，直到遇到第一个已经探索的结点，再由新结点数量与其中最高结点的权值计算本次价值。

若叶子数量为 $k$ ，时间复杂度为 $\mathcal{O}(k!kn)$ 。

【数据点 3∼63\sim 63∼6】

【题目描述】

叶子数量允许使用状压动态规划。

【Hint】

已经探索的叶子集合确定后，所有根到叶路径的并集也随之确定。

【解法】

令 $F_S$ 表示已经探索集合 $S$ 中所有叶子时的最大价值。枚举下一个叶子 $v\notin S$ ，直接求出加入 $v$ 时的新探索链，并作转移

F_{S\cup\{v\}} \leftarrow \max\left(F_{S\cup\{v\}},F_S+\operatorname{Value}(S,v)\right).

这一做法仍然枚举叶子的探索先后，但它提示我们：真正影响价值的是每个结点第一次从哪个儿子方向被经过。

【正解】

【题目描述】

设计树形动态规划，消去叶子排列这一维。

【Hint】

一个探索序列会把全部结点划分成若干条从上向下的链。处理完结点 $u$ 的子树以后，只有一条从 $u$ 开始的链可能继续向祖先延伸。

【状态】

定义 $d_{u,l}$ 表示：

已经确定 $u$ 子树内的探索顺序；
其中有一条从 $u$ 开始、长度为 $l$ 的链暂时不计算价值，等待连接到 $u$ 的祖先；
除这条链外，其余新探索链均已结算时能够得到的最大总价值。

若 $u$ 为叶子，唯一的链只包含 $u$ ，所以

d_{u,1}=0,

其余状态均为负无穷。

【转移】

对于 $u$ 的儿子 $v$ ，先计算这棵子树完全在 $v$ 处封口时的最优价值

g_v= \max_{1\leq l\leq h_v} \left\{ d_{v,l}+a_vb_l \right\}.

若选择儿子 $v$ 的保留链穿过 $u$ ，原来长度为 $l$ 的链增长为 $l+1$ ；其余儿子 $w$ 的子树全部在 $w$ 处封口。因此

d_{u,l+1} = \max_{v\in\operatorname{Son}(u)} \left\{ d_{v,l} +\sum_{w\in\operatorname{Son}(u)}g_w-g_v \right\}.

不可达状态必须设为负无穷，不能用 $0$ 代替，因为 $a_u,b_l$ 均可能为负数。

【答案与正确性】

根结点没有祖先，最后一条保留链必须在根处结算，因此答案为

\max_{1\leq l\leq h_1} \left\{ d_{1,l}+a_1b_l \right\}.

对任意探索序列，在每个非叶结点 $u$ 处，只有第一个被探索的儿子方向能够把链继续向上延伸，故它必然对应某次转移。

反过来，先探索被选中儿子中的保留链，再依次完成其余儿子的最优探索顺序，就能实现转移给出的链划分与价值。因此上述状态恰好覆盖全部合法探索序列。

【复杂度分析】

记 $h_u$ 为 $u$ 子树的高度。每个非根结点的动态规划数组只会在处理父亲时完整扫描常数次，因此时间复杂度为

\mathcal{O}\left(\sum_{u=1}^{n}h_u\right) \leq \mathcal{O}(nm).

空间复杂度同样为 $\mathcal{O}\left(\sum_uh_u\right)\leq\mathcal{O}(nm)$ 。

【参考代码】

1/*2Author:Ehundategh3Date:2026/7/244Name:tree.cpp5You steal,I kill.6*/7#include <vector>8#include <cstdio>9#include <cstring>10#include <algorithm>11#define MAXN 801012#define MAXM 81013using namespace std;14const long long INF=4e18;15int T,n,m,Fa[MAXN],Height[MAXN];16long long a[MAXN],b[MAXN],Dp[MAXN][MAXM],Best[MAXN];17vector <int> Son[MAXN];18void Solve(){19    scanf("%d%d",&n,&m);20    for(int i=1;i<=n;i++) Son[i].clear();21    for(int i=2;i<=n;i++){22        scanf("%d",&Fa[i]);23        Son[Fa[i]].push_back(i);24    }25    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);26    for(int i=1;i<=n;i++) scanf("%lld",&b[i]);27    memset(Dp,0x80,sizeof(Dp));28    for(int Now=n;Now>=1;Now--){29        if(Son[Now].empty()){30            Height[Now]=1;31            Dp[Now][1]=0;32            continue;33        }34        Height[Now]=1;35        long long Sum=0;36        for(int To:Son[Now]){37            Height[Now]=max(Height[Now],Height[To]+1);38            Best[To]=-INF;39            for(int j=1;j<=Height[To];j++){40                Best[To]=max(Best[To],Dp[To][j]+a[To]*b[j]);41            }42            Sum+=Best[To];43        }44        for(int To:Son[Now]){45            for(int j=1;j<=Height[To];j++){46                Dp[Now][j+1]=max(Dp[Now][j+1],Dp[To][j]+Sum-Best[To]);47            }48        }49    }50    long long Ans=-INF;51    for(int i=1;i<=Height[1];i++) Ans=max(Ans,Dp[1][i]+a[1]*b[i]);52    printf("%lld\n",Ans);53    return;54}55int main(){56    int c;57    scanf("%d%d",&c,&T);58    while(T-->0) Solve();59    return 0;60}