[luogu8294]最大权独立集问题

记$ls$和$rs$分别为$k$的左右儿子$,sub_{k}$表示以$k$为根的子树中节点集合

定义$f_{k,i,j}$表示以$k$为根的子树中，子树内$d_{i}$与子树外$d_{j}$发生交换的最小代价，则
$$
f_{k,i,j}=d_{i}+d_{j}+\begin{cases}
0&(ls=rs=\empty)\\
\begin{cases}
\min_{x\in sub_{ls}}f_{ls,x,j}&i=k\\f_{ls,i,k}&i\in sub_{ls}
\end{cases}&(ls\ne \empty,rs=\empty)\\
\begin{cases}
\min_{x\in sub_{ls},y\in sub_{rs}}\min(f_{ls,x,j}+f_{rs,y,x},f_{rs,y,j}+f_{ls,x,y})&i=k\\
\min_{y\in sub_{rs}}\min(f_{ls,i,k}+f_{rs,y,j},f_{rs,y,k}+f_{ls,i,y})&i\in sub_{ls}
\end{cases}&(ls,rs\ne \empty)
\end{cases}
$$
（根据$ls$和$rs$的对称性，这里省略了部分情况）

另外，最终答案需要对根节点做一个类似的分类讨论，具体略

暴力转移，时空复杂度均为$o(n^{3})$，无法通过

观察转移式子，构造$\begin{cases}f0(k,j)=f_{k,k,j}\\f1(k,i)=f_{k,i,fa}\\f2(k,j)=\min_{i\in sub_{k}}f_{k,i,j}\\f3(k,i)=\min_{j\in sub_{rs}}f_{rs,j,k}+f_{ls,i,j}\end{cases}$?，则
$$
f_{k,i,j}=\begin{cases}f0(k,j)&i=k\\f1(ls,i)+d_{i}+d_{j}&i\in sub_{ls},ls\ne \empty,rs=\empty\\\min(f1(ls,i)+f2(rs,j),f3(k,i))+d_{i}+d_{j}&i\in sub_{ls},ls\ne \empty,rs\ne\empty\end{cases}
$$
利用$f[0-3]$在线$o(1)$算出$f_{k,i,j}$，空间复杂度降为$o(n^{2})$

对式子简单优化（求$f0$时需要将$f$展开），时间复杂度也降为$o(n^{2})$，可以通过

  1 #include
  2 using namespace std;
  3 #define N 5005
  4 #define ll long long
  5 int n,x,d[N],ls[N],rs[N],dfn[N],vis[N];
  6 ll ans,f0[N][N],f1[N][N],f2[N][N],f3[N][N];
  7 vector<int>v0,v[N];
  8 ll get(int k,int i,int j){
  9     if (i==k)return f0[k][j];
 10     if (!rs[k])return f1[ls[k]][i]+d[i]+d[j];
 11     if (dfn[i]return min(f1[ls[k]][i]+f2[rs[k]][j],f3[k][i])+d[i]+d[j];
 12     return min(f1[rs[k]][i]+f2[ls[k]][j],f3[k][i])+d[i]+d[j];
 13 }
 14 void dfs(int k,int fa){
 15     dfn[k]=++dfn[0],v[k].push_back(k);
 16     if (ls[k]){
 17         dfs(ls[k],k);
 18         for(int i:v[ls[k]])v[k].push_back(i);
 19     }
 20     if (rs[k]){
 21         dfs(rs[k],k);
 22         for(int i:v[rs[k]])v[k].push_back(i);
 23     }
 24     v0.clear();
 25     memset(vis,0,sizeof(vis));
 26     for(int i:v[k])vis[i]=1;
 27     for(int i=1;i<=n;i++)
 28         if (!vis[i])v0.push_back(i);
 29     if (!ls[k]){
 30         for(int j:v0)f0[k][j]=0;
 31         if (fa){
 32             for(int i:v[k])f1[k][i]=0;
 33         }
 34         int s=1e9;
 35         for(int i:v[k])s=min(s,d[i]);
 36         for(int j:v0)f2[k][j]=s;
 37     }
 38     else{
 39         if (!rs[k]){
 40             for(int j:v0)f0[k][j]=f2[ls[k]][j];
 41             if (fa){
 42                 for(int x:v[ls[k]])f1[k][k]=min(f1[k][k],get(ls[k],x,fa));
 43                 for(int i:v[ls[k]])f1[k][i]=get(ls[k],i,k);
 44             }
 45             ll s=1e18;
 46             for(int i:v[ls[k]])s=min(s,get(ls[k],i,k)+d[i]);
 47             for(int j:v0)f2[k][j]=min(f2[ls[k]][j]+d[k],s);
 48         }
 49         else{
 50             for(int j:v0)f0[k][j]=f0[ls[k]][j]+f2[rs[k]][ls[k]];
 51             if (ls[ls[k]]){
 52                 ll s1=1e18,s2=1e18;
 53                 for(int x:v[ls[ls[k]]]){
 54                     s1=min(s1,f1[ls[ls[k]]][x]+d[x]+f2[rs[k]][x]);
 55                     s2=min(s2,f3[ls[k]][x]+d[x]+f2[rs[k]][x]);
 56                 }
 57                 if (!rs[ls[k]]){
 58                     for(int j:v0)f0[k][j]=min(f0[k][j],s1+d[j]);
 59                 }
 60                 else{
 61                     for(int j:v0)f0[k][j]=min(f0[k][j],min(s1+f2[rs[ls[k]]][j],s2)+d[j]);
 62                     s1=s2=1e18;
 63                     for(int x:v[rs[ls[k]]]){
 64                         s1=min(s1,f1[rs[ls[k]]][x]+d[x]+f2[rs[k]][x]);
 65                         s2=min(s2,f3[ls[k]][x]+d[x]+f2[rs[k]][x]);
 66                     }
 67                     for(int j:v0)f0[k][j]=min(f0[k][j],min(s1+f2[ls[ls[k]]][j],s2)+d[j]);
 68                 }
 69             }
 70             for(int j:v0)f0[k][j]=min(f0[k][j],f0[rs[k]][j]+f2[ls[k]][rs[k]]);
 71             if (ls[rs[k]]){
 72                 ll s1=1e18,s2=1e18;
 73                 for(int y:v[ls[rs[k]]]){
 74                     s1=min(s1,f1[ls[rs[k]]][y]+d[y]+f2[ls[k]][y]);
 75                     s2=min(s2,f3[rs[k]][y]+d[y]+f2[ls[k]][y]);
 76                 }
 77                 if (!rs[rs[k]]){
 78                     for(int j:v0)f0[k][j]=min(f0[k][j],s1+d[j]);
 79                 }
 80                 else{
 81                     for(int j:v0)f0[k][j]=min(f0[k][j],min(s1+f2[rs[rs[k]]][j],s2)+d[j]);
 82                     s1=s2=1e18;
 83                     for(int y:v[rs[rs[k]]]){
 84                         s1=min(s1,f1[rs[rs[k]]][y]+d[y]+f2[ls[k]][y]);
 85                         s2=min(s2,f3[rs[k]][y]+d[y]+f2[ls[k]][y]);
 86                     }
 87                     for(int j:v0)f0[k][j]=min(f0[k][j],min(s1+f2[ls[rs[k]]][j],s2)+d[j]);
 88                 }
 89             }
 90             for(int i:v[ls[k]])
 91                 for(int j:v[rs[k]])f3[k][i]=min(f3[k][i],get(rs[k],j,k)+get(ls[k],i,j));
 92             for(int i:v[rs[k]])
 93                 for(int j:v[ls[k]])f3[k][i]=min(f3[k][i],get(ls[k],j,k)+get(rs[k],i,j));
 94             if (fa){
 95                 for(int x:v[ls[k]])f1[k][k]=min(f1[k][k],get(ls[k],x,fa)+f2[rs[k]][x]);
 96                 for(int y:v[rs[k]])f1[k][k]=min(f1[k][k],get(rs[k],y,fa)+f2[ls[k]][y]);
 97                 for(int i:v[ls[k]])f1[k][i]=min(get(ls[k],i,k)+f2[rs[k]][fa],f3[k][i]);
 98                 for(int i:v[rs[k]])f1[k][i]=min(get(rs[k],i,k)+f2[ls[k]][fa],f3[k][i]);
 99             }
100             ll s=1e18,s1=1e18,s2=1e18;
101             for(int i:v[ls[k]])s=min(s,f3[k][i]+d[i]),s1=min(s1,get(ls[k],i,k)+d[i]);
102             for(int i:v[rs[k]])s=min(s,f3[k][i]+d[i]),s2=min(s2,get(rs[k],i,k)+d[i]);
103             for(int j:v0)f2[k][j]=min(f0[k][j]+d[k],min(s,min(s1+f2[rs[k]][j],s2+f2[ls[k]][j])));
104         }
105     }
106     for(int j:v0)f0[k][j]+=d[k]+d[j];
107     if (fa){
108         for(int i:v[k])f1[k][i]+=d[i]+d[fa];
109     }
110     for(int j:v0)f2[k][j]+=d[j];
111 }
112 int main(){
113     scanf("%d",&n);
114     for(int i=1;i<=n;i++)scanf("%d",&d[i]);
115     for(int i=2;i<=n;i++){
116         scanf("%d",&x);
117         if (!ls[x])ls[x]=i;
118         else rs[x]=i;
119     }
120     memset(f0,0x3f,sizeof(f0));
121     memset(f1,0x3f,sizeof(f1));
122     memset(f2,0x3f,sizeof(f2));
123     memset(f3,0x3f,sizeof(f3));
124     ans=1e18,dfs(1,0);
125     if (!ls[1])ans=0;
126     else{
127         if (!rs[1]){
128             for(int x:v[ls[1]])ans=min(ans,get(ls[1],x,1));
129         }
130         else{
131             for(int x:v[ls[1]])
132                 for(int y:v[rs[1]])ans=min(ans,min(get(ls[1],x,1)+get(rs[1],y,x),get(rs[1],y,1)+get(ls[1],x,y)));
133         }
134     }
135     printf("%lld\n",ans);
136     return 0;
137 }