P1055 · OFFICIAL SOLUTION

P1055 树的遍历官方题解

Gioush OJ · P1055 树的遍历

【数据点 1∼31\sim 31∼3】

这一档保证 $n\leq3$ ，非叶结点最多只有 $7$ 个，可以枚举被唤醒的守卫集合。
固定集合以后，从叶结点向上计算遍历序列。沉睡结点把字典序较小的子树序列放在前面，唤醒结点固定先左后右。
在花费不超过 $k$ 的集合中取字典序最大的序列即可。

【数据点 4∼64\sim 64∼6】

这一档保证 $k=0$ 且所有花费为正，因此没有守卫能够被唤醒。
每个非叶结点都由小 R 选择先访问哪棵子树。由于叶结点符文互不相同，只需比较两棵子树最终序列的第一个符文。
递归计算两棵子树，再把首项较小的序列放在前面。时间复杂度为 $\mathcal{O}(n2^n)$ 。

【数据点 7∼197\sim 197∼19】

令 $S_u$ 表示结点 $u$ 子树中的符文集合，定义

f_{u,x}=\text{使结点 $u$ 的遍历序列首项为 $x$ 的最小花费}.

若 $u$ 是写有符文 $q_u$ 的叶结点，则 $f_{u,q_u}=0$ ，其余状态均不合法。
若 $u$ 的左右儿子为 $l,r$ ，当 $x\in S_l$ 时，可以唤醒 $u$ ，也可以让右子树首项严格大于 $x$ 。
当 $x\in S_r$ 时，不能唤醒 $u$ ，并且左子树首项必须严格大于 $x$ 。

【数据点 7∼197\sim 197∼19：状态转移】

完整转移为

f_{u,x}= \begin{cases} f_{l,x}+\min\left(w_u,\displaystyle\min_{y\in S_r,\,y>x}f_{r,y}\right),&x\in S_l,\\[8pt] f_{r,x}+\displaystyle\min_{y\in S_l,\,y>x}f_{l,y},&x\in S_r. \end{cases}

空集合的最小值视为正无穷。加法中只要有一项不合法，结果也不合法。
直接枚举 $x$ 与另一棵子树的 $y$ ，可以做到 $\mathcal{O}(4^n)$ ，足以通过 $n\leq8$ 。

【正解】

定义严格后缀最小值

g_{u,x}=\min_{y\in S_u,\,y>x}f_{u,y}.

于是转移可以写成

f_{u,x}= \begin{cases} f_{l,x}+\min(w_u,g_{r,x}),&x\in S_l,\\ f_{r,x}+g_{l,x},&x\in S_r. \end{cases}

将两棵子树的状态按 $x$ 合并，并从右向左维护后缀最小值，每个状态只需常数次计算。
整棵树共有 $\mathcal{O}(n2^n)$ 个状态，建表时间与空间复杂度均为 $\mathcal{O}(n2^n)$ 。

【答案恢复】

在根结点中选择最大的 $x$ ，使得 $f_{1,x}\leq k$ ，这就是最终序列的首项。
恢复答案时，先预留保证当前子树先被访问所需的最小花费，再把剩余预算交给先访问的子树，使这一段序列尽可能大。
第一段确定以后，再在仍满足首项比较关系的状态中选择第二棵子树的最大首项，继续递归。
每一步都先最大化当前尚未确定的第一个位置，因此得到的完整序列字典序最大。

【实现与复杂度】

当当前首项 $x$ 来自左子树时，需要预留 $\min(w_u,g_{r,x})$ 。之后右子树首项若小于 $x$ ，就必须额外支付 $w_u$ 唤醒当前守卫。
当 $x$ 来自右子树时，需要预留 $g_{l,x}$ ，并且最后选择的左子树首项必须严格大于 $x$ 。
实现中所有花费以及预算均使用 long long，不合法状态用足够大的正数表示。

【参考代码】

1/*2Author:Ehundategh3Date:2026/7/244Name:traverse.cpp5You steal,I kill.6*/7#include <cstdio>8#include <vector>9#include <algorithm>10#define MAXN 10001011using namespace std;12const long long INF=(1ll<<62);13 14int c,n,Leaf,T,Line[MAXN<<1],Pos[MAXN],Right[MAXN<<1];15long long k,Val[MAXN];16 17struct Data {18    int Mark;19    long long Val;20};21 22vector <Data> Dp[MAXN<<1];23vector <long long> Suff[MAXN<<1];24 25long long Add(long long x,long long y){return (x>=INF||y>=INF)?INF:x+y;}26 27long long Query(int Now,int x) {28    int l=0,r=(int)Dp[Now].size();29    while (l<r) {30        int Mid=(l+r)>>1;31        if (Dp[Now][Mid].Mark<=x) l=Mid+1;32        else r=Mid;33    }34    return l==(int)Dp[Now].size()?INF:Suff[Now][l];35}36 37void Build(int Now) {38    if (Now>=Leaf) {39        Right[Now]=Now-Leaf+1;40        Dp[Now].push_back({Line[Now],0});41        Suff[Now].push_back(0);42        return;43    }44    int ls=Now<<1,rs=Now<<1|1;45    Build(ls);Build(rs);46    Right[Now]=Right[rs];47    int i=0,j=0,p=0,q=0;48    Dp[Now].reserve(Dp[ls].size()+Dp[rs].size());49    while (i<(int)Dp[ls].size()||j<(int)Dp[rs].size()) {50        bool Tag=j==(int)Dp[rs].size()||51            (i<(int)Dp[ls].size()&&Dp[ls][i].Mark<Dp[rs][j].Mark);52        int Mark=Tag?Dp[ls][i].Mark:Dp[rs][j].Mark;53        while (p<(int)Dp[ls].size()&&Dp[ls][p].Mark<=Mark) p++;54        while (q<(int)Dp[rs].size()&&Dp[rs][q].Mark<=Mark) q++;55        if (Tag) {56            long long Ret=q==(int)Dp[rs].size()?INF:Suff[rs][q];57            Dp[Now].push_back({Mark,Add(Dp[ls][i].Val,min(Val[Now],Ret))});58            i++;59        }60        else {61            long long Ret=p==(int)Dp[ls].size()?INF:Suff[ls][p];62            Dp[Now].push_back({Mark,Add(Dp[rs][j].Val,Ret)});63            j++;64        }65    }66    Suff[Now].resize(Dp[Now].size());67    for (int t=(int)Dp[Now].size()-1;t>=0;t--) {68        Suff[Now][t]=Dp[Now][t].Val;69        if (t+1<(int)Dp[Now].size()) Suff[Now][t]=min(Suff[Now][t],Suff[Now][t+1]);70    }71    return;72}73 74long long Print(int Now,int x,long long Limit) {75    if (Now>=Leaf) {printf("%d ",Line[Now]);return 0;}76    int ls=Now<<1,rs=Now<<1|1,Temp=0;77    if (Pos[x]<=Right[ls]) {78        long long Need=min(Val[Now],Query(rs,x));79        long long Ret=Print(ls,x,Limit-Need);80        Limit-=Ret;81        for (int i=(int)Dp[rs].size()-1;i>=0;i--) {82            long long Extra=Dp[rs][i].Mark<x?Val[Now]:0;83            if (Add(Dp[rs][i].Val,Extra)<=Limit) {84                Temp=Dp[rs][i].Mark;85                break;86            }87        }88        long long Extra=Temp<x?Val[Now]:0;89        return Ret+Extra+Print(rs,Temp,Limit-Extra);90    }91    long long Need=Query(ls,x);92    long long Ret=Print(rs,x,Limit-Need);93    Limit-=Ret;94    for (int i=(int)Dp[ls].size()-1;i>=0;i--) {95        if (Dp[ls][i].Mark>x&&Dp[ls][i].Val<=Limit) {96            Temp=Dp[ls][i].Mark;97            break;98        }99    }100    return Ret+Print(ls,Temp,Limit);101}102 103void Solve() {104    scanf("%d%lld",&n,&k);Leaf=1<<n;105    for (int i=1;i<(Leaf<<1);i++) Dp[i].clear(),Suff[i].clear();106    for (int i=1;i<Leaf;i++) scanf("%lld",&Val[i]);107    for (int i=Leaf;i<(Leaf<<1);i++) {108        scanf("%d",&Line[i]);109        Pos[Line[i]]=i-Leaf+1;110    }111    Build(1);112    int Temp=0;113    for (int i=(int)Dp[1].size()-1;i>=0;i--) {114        if (Dp[1][i].Val<=k) {115            Temp=Dp[1][i].Mark;116            break;117        }118    }119    Print(1,Temp,k);120    printf("\n");121    return;122}123 124int main() {125    scanf("%d%d",&c,&T);126    while (T-->0) Solve();127    return 0;128}