DP

\(F_{i,j}\) 表示处理掉以 \(i\) 为根的子树，并向上支援 \(j\) 格的最小代价

\(j\in [-D,D]\)

暴力转移 \(O(ND^3)\) ~ \(O(ND^2)\)

稍作修改

\(F_{i,j}\) 表示处理掉以 \(i\) 为根的子树，并向上支援至少 \(j\) 格的最小代价

容易得到 \(O(ND)\) 做法

#include 
    
     #include 
     
      #include 
      
       using std::min;using std::vector;const int MAXN=500111;const int MAXD=23;const int INF=1034567890;int N, D, M;struct Vert{    int Val;    bool Is;    int FE;    int F_[MAXD<<1], *F;    Vert(){F=F_+MAXD;}} V[MAXN];struct Edge{    int y, next;} E[MAXN<<1];int Ecnt;void addE(int a, int b){    ++Ecnt;    E[Ecnt].y=b;E[Ecnt].next=V[a].FE;V[a].FE=Ecnt;}void DFS(int at, int f){    vector
       
         Son;    for(int k=V[at].FE, to;k;k=E[k].next){        to=E[k].y;        if(to==f)   continue;        Son.push_back(to);        DFS(to, at);    }    if(!Son.size()){        for(int i=1-V[at].Is;i<=D;++i)  V[at].F[i]=V[at].Val;        return;    }    //j=D;    for(int i=0, s=Son.size();i
        
         =-D;--j){        for(int i=0, s=Son.size();i
         
          =-D;--i) V[at].F[i]=min(V[at].F[i+1], V[at].F[i]);}int main(){ scanf("%d%d", &N, &D); for(int i=1;i<=N;++i) scanf("%d", &V[i].Val); scanf("%d", &M); for(int i=1, a;i<=M;++i) {scanf("%d", &a);V[a].Is=true;} for(int i=1, a, b;i