P1060 · OFFICIAL SOLUTION

P1060 云止聆佳响官方题解

Gioush OJ · P1060 云止聆佳响

【部分分：测试点 1∼31\sim 31∼3】

当 $n\leq 20$ 时，可以枚举所有非空听音台集合。
判断这些听音台能否按照祖先关系排成一条龙吟，再统计相邻音高方向改变的次数与鸣响值。
枚举集合并检查，时间复杂度为 $\mathcal O(2^n n)$ 。

【部分分：测试点 4∼74\sim 74∼7】

设 $d_{u,j,0/1}$ 表示以 $u$ 结尾、发生 $j$ 次激荡，最后一段分别上扬或低回的最大鸣响值。
枚举 $u$ 的所有祖先 $v$ 进行转移。若 $a_v<a_u$ ，可以接到上扬状态，否则可以接到低回状态。
每对祖先与后代至多处理 $\mathcal O(k)$ 个状态，总时间复杂度为 $\mathcal O(n^2k)$ 。

【部分分：测试点 8∼118\sim 118∼11】

当 $k=0$ 时，音高方向一旦确定就不能改变。
深度优先搜索时，分别维护各音高下上扬龙吟与低回龙吟的最大鸣响值。
查询严格更低或严格更高音高中的最大值即可完成转移。

【部分分：测试点 12∼1512\sim 1512∼15】

特殊性质 A 保证整棵树是一条链，祖先集合就是当前位置之前的前缀。
对每个激荡次数和末段方向维护一棵按音高建立的线段树。
查询严格更低或严格更高音高的前缀、后缀最大值，时间复杂度为 $\mathcal O(nk\log n)$ 。

【部分分：测试点 16∼2016\sim 2016∼20】

在一般树上进行深度优先搜索。进入结点 $u$ 时，数据结构中只保留根到 $u$ 的祖先状态。
离开 $u$ 时撤销它对数据结构的修改。这样同一套链上转移可以直接用于一般树。
音高先离散化。每个激荡次数与末段方向各维护一棵线段树。

【正解】

令 $d_{u,j,0}$ 表示以 $u$ 结尾、发生 $j$ 次激荡且最后一段上扬的最大鸣响值。
令 $d_{u,j,1}$ 表示以 $u$ 结尾、发生 $j$ 次激荡且最后一段低回的最大鸣响值。
单独选择 $u$ 的状态记为 $d_{u}=w_u$ 。不存在相邻听音台，因此尚未确定末段方向。
记 $\max_{a_v<a_u}$ 表示在当前祖先链上对所有满足 $a_v<a_u$ 的状态取最大值，则

d_{u,j,0}=w_u+\max_{a_v<a_u} \begin{cases} d_v,\\ d_{v,j,0},\\ d_{v,j-1,1},&j>0. \end{cases}

前两项分别表示从单点开始与继续上扬，第三项表示由低回转为上扬并新增一次激荡。
对称地，记 $\max_{a_v>a_u}$ 表示在当前祖先链上对所有满足 $a_v>a_u$ 的状态取最大值，则

d_{u,j,1}=w_u+\max_{a_v>a_u} \begin{cases} d_v,\\ d_{v,j,1},\\ d_{v,j-1,0},&j>0. \end{cases}

音高必须严格不同，因此查询区间不包含 $a_u$ 对应的位置。
进入结点前保存各线段树在音高 $a_u$ 处的旧值，写入由 $u$ 得到的新状态。
递归处理完子树后恢复旧值，从而保证兄弟子树之间不会互相转移。
状态数为 $2(k+1)+1$ 。时间复杂度为 $\mathcal O(nk\log n)$ ，空间复杂度为 $\mathcal O(nk)$ 。

【参考代码】

1#include <cstdio>2#include <vector>3#include <algorithm>4#define MAXK 85using namespace std;6 7const long long INF=-(1LL<<60);8 9class SegmentTree{10public:11    int n;12    vector<long long> Val;13    void Init(int m){14        n=1;15        while(n<m) n<<=1;16        Val.assign(n<<1,INF);17    }18    long long Get(int p){return Val[n+p-1];}19    void Give(int p,long long v){20        int x=n+p-1;21        Val[x]=v;22        for(x>>=1;x;x>>=1) Val[x]=max(Val[x<<1],Val[x<<1|1]);23    }24    long long Query(int l,int r){25        if(l>r) return INF;26        long long Ret=INF;27        for(l=n+l-1,r=n+r-1;l<=r;l>>=1,r>>=1){28            if(l&1) Ret=max(Ret,Val[l++]);29            if(!(r&1)) Ret=max(Ret,Val[r--]);30        }31        return Ret;32    }33};34 35int main(){36    int c,T;37    scanf("%d%d",&c,&T);38    while(T-->0){39        int n,k;40        scanf("%d%d",&n,&k);41        vector<vector<int>> Son(n+1);42        for(int u=2,p;u<=n;u++) scanf("%d",&p),Son[p].push_back(u);43        vector<int> a(n+1),w(n+1),Dis;44        for(int u=1;u<=n;u++) scanf("%d",&a[u]),Dis.push_back(a[u]);45        for(int u=1;u<=n;u++) scanf("%d",&w[u]);46        sort(Dis.begin(),Dis.end());47        Dis.erase(unique(Dis.begin(),Dis.end()),Dis.end());48        int m=Dis.size(),State=1+2*(k+1);49        vector<SegmentTree> Tree(State);50        for(int i=0;i<State;i++) Tree[i].Init(m);51        vector<vector<long long>> Old(n+1,vector<long long>(State));52        vector<pair<int,bool>> S;53        S.push_back({1,0});54        long long Ans=0;55        while(!S.empty()){56            int u=S.back().first;57            bool Exit=S.back().second;58            S.pop_back();59            int p=lower_bound(Dis.begin(),Dis.end(),a[u])-Dis.begin()+1;60            if(Exit){61                for(int s=0;s<State;s++) Tree[s].Give(p,Old[u][s]);62                continue;63            }64            vector<long long> Dp(State,INF);65            Dp[0]=w[u];66            for(int j=0;j<=k;j++){67                int Up=1+(j<<1),Down=Up+1;68                long long Best=max(Tree[0].Query(1,p-1),Tree[Up].Query(1,p-1));69                if(j) Best=max(Best,Tree[1+((j-1)<<1)+1].Query(1,p-1));70                if(Best>INF/2) Dp[Up]=Best+w[u];71                Best=max(Tree[0].Query(p+1,m),Tree[Down].Query(p+1,m));72                if(j) Best=max(Best,Tree[1+((j-1)<<1)].Query(p+1,m));73                if(Best>INF/2) Dp[Down]=Best+w[u];74            }75            for(int s=0;s<State;s++){76                Old[u][s]=Tree[s].Get(p);77                Tree[s].Give(p,max(Old[u][s],Dp[s]));78                Ans=max(Ans,Dp[s]);79            }80            S.push_back({u,1});81            for(int i=(int)Son[u].size()-1;i>=0;i--) S.push_back({Son[u][i],0});82        }83        printf("%lld\n",Ans);84    }85    return 0;86}