题解 P7163 [COCI2020-2021#2] Svjetlo
novax
·
·
题解
题面。
思路
很强的树形dp。
要求选择一个最短行走序列打开所有灯。
既然是序列，那就得有起点和终点。
考虑对序列的起点和终点分类讨论。
设dp中的当前点为 p，那么可以设三个状态：f_{p},g_{p},h_{p}。分别对应所选路径的起点终点都在 p 的子树之外/选路径的端点有一个在 p 的子树之外另一个在子树内/所选路径的起点终点都在 p 的子树内，打开 p 子树内所有灯的最小步数。
每个状态还要有额外的 0/1 一维，记录这个状态下当前点上灯的状态。
为了方便转移，f,h 状态本都有一进一出两步，但我们的状态中只记录一步，另一步在转移时再加上。
dp之前先记录一下哪些子树内的灯初始时已经全被打开了，这样的子树不需要被走过。
然后说状态转移。将某个子树的状态与当前信息合并，更新当前状态。
设当前要将状态合并到当前点的子树为to。
f[p][0]=\min({f[p][1]+f[to][0]+2,f[p][0]+f[to][1]+4})\\
f[p][1]=\min({f[p][0]+f[to][0]+2,f[p][1]+f[to][1]+4})\\
\end{cases}
↑↑↑ 先说 f 的转移。
$+4$ 的转移：走一次 $+2$ 的转移后，再走两步：$p \rightarrow to \rightarrow p$。这样起到了在 $+2$ 转移基础上使 $p$ 和 $to$ 的灯泡状态都反转的效果。
$$\begin{cases}
g[p][0]=\min({g[p][1]+f[to][0]+2,g[p][0]+f[to][1]+4,f[p][1]+g[to][1]+1,f[p][0]+g[to][0]+3})\\
g[p][1]=\min({g[p][0]+f[to][0]+2,g[p][1]+f[to][1]+4,f[p][0]+g[to][1]+1,f[p][1]+g[to][0]+3})\\
\end{cases}$$
↑↑↑ 然后是 $g$ 的转移。
因为 $g$ 有一个端点在子树内而另一个端点在子树外，所以分端点在原有子树与端点在 $to$ 子树内分开讨论。状态也即 $f$ 与 $g$ 的合并。
$+2$ 的转移：原理与 $f$ 的对应转移类似。将子树 $to$ 的 $f$ 状态接在当前点的 $g$ 状态上。
$+1$ 的转移：将子树 $to$ 的 $g$ 状态接在当前点的 $f$ 状态上。此时该路径的起点在子树 $to$ 内，只有从 $to$ 点向上走到 $p$ 的额外一步，所以是加一。因为此转移只走过 $p$ 点一次而没有走过 $to$，所以 $to$ 的状态需要为 $1$ 而 $p$ 的状态正常取反。
$+4,+3$ 的转移：与 $f$ 的 $+4$ 的转移类似，在 $+2,+1$ 的基础上走到 $to$ 点再走回来一次。
$$\begin{cases}
h[p][0]=\min({h[p][1]+f[to][0]+2,h[p][0]+f[to][1]+4,f[p][1]+h[to][0]+2,f[p][0]+h[to][1]+4,g[p][0]+g[to][1],g[p][1]+g[to][0]+2})\\
h[p][1]=\min({h[p][0]+f[to][0]+2,h[p][1]+f[to][1]+4,f[p][0]+h[to][0]+2,f[p][1]+h[to][1]+4,g[p][1]+g[to][1],g[p][0]+g[to][0]+2})\\
\end{cases}$$
↑↑↑ 最麻烦的 $h$ 的转移。
$h$ 的两个端点都在子树内。所以有三种情况到达合并后的结果：原有子树内有两个端点而 $to$ 内没有；原树与 $to$ 子树内各有一个；两个端点都在 $to$ 子树内。
第一个 $+2$ 转移：对应上述第二个转移。原理与 $f$ 的 $+2$ 转移类似。将子树 $to$ 的 $f$ 状态接在当前点的 $h$ 状态上。
第二个 $+2$ 转移：对应上述第三个转移。将子树 $to$ 的 $f$ 状态接在当前点的 $h$ 状态上。同样是需要多走两步。
$+0$ 的转移：对应上述第二个转移。合并当前点的 $g$ 与 $to$ 的 $g$ 状态。因为 $g$ 状态本来就记录了离开当前点的一步，所以两个状态可以直接合并，并不需要额外走任何步数。
两个 $+4$ 的转移及第三个 $+2$ 的转移：与 $f$ 的 $+4$ 的转移类似，在上面三个转移的基础上走到 $to$ 点再走回来一次以实现 $p$ 点和 $to$ 点上状态都反转的效果。
$g$ 和 $h$ 的状态考虑了路径端点，所以不一定要从子树里转移而来，也有可能是以当前点为状态中路径的端点。
$$\begin{cases}
g[p][0]=min(g[p][0],f[p][1]+1)\\
g[p][1]=min(g[p][1],f[p][0]+1)\\
h[p][0]=min(h[p][0],f[p][0])\\
h[p][1]=min(h[p][1],f[p][1])\\
\end{cases}$$
↑↑↑ 四个以当前点为路径端点的转移。
对于 $g$ 的两个转移：设置当前点为起点。因为我们定义的 $f$ 状态中没有记录进入当前点的那一步，而以 $p$ 为起点后状态里少了起点那一步，所以要 $+1$，$f$ 的状态也对应反转。
对于 $h$ 的两个转移：设置当前点为一个端点。$g$ 与 $h$ 同样都只记录了离开当前点的一步，所以直接与 $f$ 状态取 $\min$ 即可。
初始选定的根需要其上的灯是关闭的，否则会通过一些不必要的步数将打开的灯关上再打开。最后的 $h_{root,1}$ 即为最终的答案。
#### 代码
```cpp
#include <cstdio>
#include <algorithm>
using std::min;
const int Nx=500010;
int N;
char A[Nx];
struct edge{int to,nex;};
edge a[2*Nx];
int head[Nx],cnt;
void add(int u,int v)
{
a[++cnt].to=v;
a[cnt].nex=head[u];
head[u]=cnt;
}
int siz[Nx],saz[Nx],used[Nx];
void dfs_X(int p,int fa)
{
int i;
siz[p]=1;
saz[p]=A[p];
for(i=head[p];i;i=a[i].nex)
{
if(a[i].to==fa)
continue;
dfs_X(a[i].to,p);
siz[p]+=siz[a[i].to];
saz[p]+=saz[a[i].to];
}
if(siz[p]==saz[p])
used[p]=1;
}
int F[Nx][3],G[Nx][3],H[Nx][3];//i的子树内灯泡全部被点亮的最短路径长度 F该路径两端点都不在i子树内 G有一个端点在i子树里 H两个端点都在i子树里
void dfs_DP(int p,int fa)
{
//printf("DP : %d %d\n",p,fa);
int i,to,f[3],g[3],h[3];
F[p][A[p]]=0;
for(i=head[p];i;i=a[i].nex)
{
if(a[i].to==fa||used[a[i].to])
continue;
dfs_DP(a[i].to,p);
to=a[i].to;
f[0]=F[p][0],g[0]=G[p][0],h[0]=H[p][0];
f[1]=F[p][1],g[1]=G[p][1],h[1]=H[p][1];
F[p][0]=min({f[1]+F[to][0]+2,f[0]+F[to][1]+4});
F[p][1]=min({f[0]+F[to][0]+2,f[1]+F[to][1]+4});
G[p][0]=min({g[1]+F[to][0]+2,g[0]+F[to][1]+4,f[1]+G[to][1]+1,f[0]+G[to][0]+3});
G[p][1]=min({g[0]+F[to][0]+2,g[1]+F[to][1]+4,f[0]+G[to][1]+1,f[1]+G[to][0]+3});
H[p][0]=min({h[1]+F[to][0]+2,h[0]+F[to][1]+4,f[1]+H[to][0]+2,f[0]+H[to][1]+4,g[0]+G[to][1],g[1]+G[to][0]+2});
H[p][1]=min({h[0]+F[to][0]+2,h[1]+F[to][1]+4,f[0]+H[to][0]+2,f[1]+H[to][1]+4,g[1]+G[to][1],g[0]+G[to][0]+2});
}
G[p][0]=min(G[p][0],F[p][1]+1);
G[p][1]=min(G[p][1],F[p][0]+1);
H[p][0]=min(H[p][0],G[p][0]);
H[p][1]=min(H[p][1],G[p][1]);
}
int main()
{
scanf("%d%s",&N,A+1);
int i,j,k;
for(i=1;i<=N;i++)
A[i]-='0';
for(i=1;i<N;i++)
{
scanf("%d%d",&j,&k);
add(j,k),add(k,j);
}
k=0;
for(i=1;i<=N;i++)
{
F[i][0]=G[i][0]=H[i][0]=1e8;
F[i][1]=G[i][1]=H[i][1]=1e8;
if(k==0&&A[i]==0)
k=i;
}
if(k==0)
{
printf("0\n");
return 0;
}
dfs_X(k,0);
dfs_DP(k,0);
printf("%d\n",H[k][1]);
}
```