题解：P16562 [ICPC 2026 APC] Christmas Tree Un-decoration

· · 题解

题意简述

一棵有根树的每个结点上都有若干饰品。一次操作选择结点 u，将根到 u 的路径上每个仍有饰品的结点各减少一个饰品。

在单点修改饰品数量后，求清空整棵树所需的最少操作次数。修改只改变数据，并不会真正执行清空操作。

解题思路

先求静态树上的转移。

设 f_u 表示清空 u 的整棵子树所需的最少操作次数，S_u 表示 u 的儿子集合。

每次操作的终点只会落入至多一棵儿子子树。清空不同儿子子树所需的操作无法相互替代，因此至少要进行：

\sum_{v\in S_u}f_v

次操作。另一方面，每次操作至多移除 u 上的一个饰品，所以操作次数也至少为 a_u。

依次执行每棵儿子子树的最优方案时，所有操作都会经过 u，可以顺便移除 u 上的饰品。若这些操作仍不够，再以 u 为终点补足。因此两个下界可以同时达到：

f_u=\max\left(a_u,\sum_{v\in S_u}f_v\right)

接下来处理动态修改。

对树进行重链剖分，记 h_u 为 u 的重儿子，并令轻儿子的贡献和为：

g_u=\sum_{\substack{v\in S_u\\v\ne h_u}}f_v

转移式变为：

f_u=\max(g_u+f_{h_u},a_u)

常见做法会把它写成最大值–加法矩阵。本题只需要一种特殊的一元函数，可以直接维护函数复合。

用数对 (b,c) 表示函数：

\varphi(x)=\max(x+b,c)

结点 u 对应的函数数对就是 (g_u,a_u)。若数对 (b_1,c_1) 和 (b_2,c_2) 分别表示函数 \varphi_1,\varphi_2，则：

\begin{aligned} \varphi_1(\varphi_2(x)) & =\max\left(x+b_2+b_1,c_2+b_1,c_1\right) \end{aligned}

所以复合后的数对为：

(b_1,c_1)\circ(b_2,c_2)=\left(b_1+b_2,\max(c_1,b_1+c_2)\right)

函数复合满足结合律，恒等函数对应 (0,-\infty)。同一条重链上，从链头到链尾依次复合结点函数。链尾没有重儿子，相当于把 0 代入整条链的复合函数，所得结果就是链头的 f 值。

按照重链顺序给结点编号，用线段树维护这些函数的区间复合。因为复合不满足交换律，查询时要分别累积左侧结果和右侧结果，并保持从上到下的顺序。

修改结点 u 的 a_u 后，先在线段树中修改 u 对应的函数，再查询当前重链链头 t 的新 f_t。若 t 不是根，它一定是父亲的轻儿子，所以 f_t 的变化量应加到 g_{fa_t} 中。随后转到 fa_t 所在的重链，重复这一过程，直到根链。

下面说明动态维护的正确性。

线段树中的每个叶子准确表示对应结点从重儿子答案到自身答案的转移。区间合并严格按照链上次序进行函数复合，所以查询一条完整重链并代入 0，准确得到链头子树的当前答案。

一次单点修改只会直接改变该结点的函数。链内影响由重新计算整条链的复合结果完整处理。链头作为父亲的轻儿子时，它对子树转移的影响只体现为父亲 g 的等量变化。逐条向上更新经过的重链后，所有受影响的祖先都被重新计算，其余结点的转移保持不变。因此最终得到的 f_1 正是修改后的最优答案。

题目保证 p_i<i。代码据此按编号逆序计算子树大小和初始动态规划。确定重儿子后，每个不是重儿子的结点都是链头，直接沿重儿子指针向下即可完成链编号，不需要递归遍历。

根到任意结点至多跨过 O(\log n) 条轻边，每条重链进行一次 O(\log n) 的单点修改和区间查询。单次修改的时间复杂度为 O(\log^2 n)，预处理时间为 O(n)，空间复杂度为 O(n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=200005;
const ll inf=0x3f3f3f3f3f3f3f3f;
struct Func
{
    ll x,y;
};
int n,bs;
int fa[N],siz[N],son[N],top[N],bot[N],dfn[N];
ll a[N],sum[N],g[N],f[N];
Func tr[N<<2];
Func operator*(const Func &a,const Func &b)
{
    return {a.x+b.x,max(a.y,a.x+b.y)};
}
Func unit()
{
    return {0,-inf};
}
Func get(int u)
{
    return {g[u],a[u]};
}
void upd(int u)
{
    int p=bs+dfn[u]-1;
    tr[p]=get(u);
    for(p>>=1;p;p>>=1)tr[p]=tr[p*2]*tr[p*2+1];
}
Func qry(int l,int r)
{
    Func x=unit();
    Func y=unit();
    for(l+=bs-1,r+=bs-1;l<=r;l>>=1,r>>=1)
    {
        if(l&1)x=x*tr[l++];
        if(!(r&1))y=tr[r--]*y;
    }
    return x*y;
}
ll ask(int u)
{
    Func x=qry(dfn[u],dfn[bot[u]]);
    return max(x.x,x.y);
}
void solve()
{
    int q;
    cin>>n>>q;
    fill(siz,siz+n+1,1);
    siz[0]=0;
    fill(son,son+n+1,0);
    fill(sum,sum+n+1,0);
    fa[1]=0;
    f[0]=0;
    for(int i=2;i<=n;i++)cin>>fa[i];
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=n;i>1;i--)
    {
        siz[fa[i]]+=siz[i];
        if(siz[i]>siz[son[fa[i]]])son[fa[i]]=i;
    }
    for(int i=n;i>=1;i--)
    {
        f[i]=max(a[i],sum[i]);
        sum[fa[i]]+=f[i];
    }
    for(int i=1;i<=n;i++)g[i]=sum[i]-f[son[i]];
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(i>1&&son[fa[i]]==i)continue;
        for(int j=i;j;j=son[j])
        {
            top[j]=i;
            bot[i]=j;
            dfn[j]=++cnt;
        }
    }
    for(bs=1;bs<n;bs*=2);
    for(int i=1;i<bs*2;i++)tr[i]=unit();
    for(int i=1;i<=n;i++)tr[bs+dfn[i]-1]=get(i);
    for(int i=bs-1;i;i--)tr[i]=tr[i*2]*tr[i*2+1];
    cout<<f[1]<<'\n';
    while(q--)
    {
        int u;
        ll x;
        cin>>u>>x;
        a[u]=x;
        while(u)
        {
            upd(u);
            int t=top[u];
            ll cur=ask(t);
            ll d=cur-f[t];
            f[t]=cur;
            u=fa[t];
            if(u)g[u]+=d;
        }
        cout<<f[1]<<'\n';
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}