P7163 [COCI2020-2021#2] Svjetlo 树形dp

· · 题解

Description

还不清楚？出门左转。

Solution

大体思路：树形dp

真的是一道树形dp神题，不论是状态设计还是转移都使我叹服QAQ。

1. 状态设计

我们最终相当于在树上找一条路，可以反复走，那么这条路一定会有两个端点吧。

看不懂图解一下，红色是我们走的路

然后讲一下状态设计的细节，从图中很容易发现， f 会伸出两个头， g 会伸出一个头， h 会伸出两个头。

然后在 f 伸出的两个头里，我们是算一个在 f 里，为的是后面好转移，不妨算出去的一个，后面会好理解一点。

当然这么讲你不可能懂，所以上图。

我们走的路径是 1 2 3 2 4 2 1 5 1 ，这时给 f_{1,1} 或者是 f_{1,0} 的值就是8，即我们只考虑 2 3 2 4 2 1 5 1。

然后 g 伸出的一个头算在里面， h 伸出的两个头只算一个，为了好理解，你也可以算是出去的那一个（其实你算哪一个效果是一样的）。

2.状态转移

树形dp肯定是深搜嘛，我们总的思路是把新的子树向已经算好的子树上合并，或者说把子树一棵一棵向x上接。

先讲一个小技巧，这将贯穿整个转移过程。

我们接子树的时候，一去一回，会把两个关着的灯打开，那如果是两个本来就开着的灯怎么办，再走一次不就又开了？这里建议自己画图模拟理解一下。

下文中，f0,f1,g0,g1,h0,h1分别代表在 y 子树还没有来的时候 f_{x} g_{x} h_{x} 的答案，即上一次的结果。

建议结合下面的图一起看。

i. 对于 f 的转移

f_{x,1}=\min(f0+f_{y,0}+2,f1+f_{y,1}+4) f_{x,0}=\min(f1+f_{y,0}+2,f0+f_{y,1}+4)

当求 f_{x,1}，走完x前面的子树，如果x和y的灯都关了 ，我们从x到y，再从y回到x，打开两个灯，如上图。如果x和y都开了，走四步，依然如上图，这样就把两棵子树接起来了。

#### ii. 对于 $g$ 的转移 $g_{x,1}=\min(g0+f_{y,0}+2,g1+f_{y,1}+4,f0+g_{y,1}+1,f1+g_{y,0}+3) g_{x,0}=\min(g1+f_{y,0}+2,g0+f_{y,1}+4,f1+g_{y,1}+1,f0+g_{y,0}+3)

由定义， g 维护的是仅有一个端点在该子树内的情况，这个端点可能在x里，也可能是在y里，所以要么是 g_x+f_y 要么是 f_x+g_y 。至于后面是+1+2+3还是+4，详见上面那张图，都是一个道理。

iii. 对于 h 的转移

h_{x,1}=\min(f0+h_{y,0}+2,f1+h_{y,1}+4,g0+g_{y,0}+2,g1+g_{y,1},h0+f_{y,0}+2,h1+f_{y,1}+4) h_{x,0}=\min(f1+h_{y,0}+2,f0+h_{y,1}+4,g1+g_{y,0}+2,g0+g_{y,1},h1+f_{y,0}+2,h0+f_{y,1}+4) h$ 比较烦，$h_x$是两个端点都在x为根的子树中，那么这两个端点可能都在x的子树中，可能都在y的子树中，也可能两边各一个。所以$h_x$就是$h_x+f_y

或f_x+h_y或g_x+g_y。后面加的那个1234还是看上面那张图。

图解一下

左上是 f_x 的转移，右上是 g_x 的转移，下面是 h_x 的转移（下中图子树里两个端点少了红点，右上好像也忘记画了，应该能懂（逃））。

iv.特例，关于 g_x,h_x 端点就在x的转移

以上的分析都是端点在子树之内，如果x就是端点呢？

g_{x,0}=\min(g_{x,0},f_{x,1}+1) g_{x,1}=\min(g_{x,1},f_{x,0}+1) h_{x,0}=\min(h_{x,0},g_{x,0}) h_{x,1}=\min(h_{x,1},g_{x,1})

什么意思呢， g 是有一个端点， f 是没有端点，我们把进来的那个x算成端点，它就是 g 了， g 要算一个出去的头，f正好有，但是 f 是不算进来的那一个点的，即你现在定的端点，所以要加1。

### 3.关于初值 设点x初始的开关状态为 $l_x$ ，那么 $f_{x,l_x}=0$，本来就是这样，不需要操作。其他的由于可能要取min，所以设为正无穷。 注意，这里如果不是叶节点设为0不会有影响，因为你在转移 $f_x$ 的时候不会和自己取min ~~（不信你翻上面式子）~~。 ### 4.dfs从哪里开始 从开始关着的灯开始。若从开着的灯（1）开始**有可能**会不是最优，因为你从下面走上来，如果接下来的子树本来就都是1，那么你的这么多步，包括上来到1的这一步，都是无效的，而你会用刚才上面那张图走4步的方法让1在变成1，这就不满足题目要的最少步数了。 而你从关着的灯（0）开始，上来到根这一步是肯定必要的，所以一定是最优。 ### 5.亿点小优化（bushi） #### 说是优化，你不优化就是WA 如果当前子树本来初始状态就全是开着的（1），根本没必要遍历这个子树，道理和上面以0为根的有点相似，都开了你再走干嘛，如果你跑这个dp，它会用4步把1变成1 。 这个东西可以先dfs预处理一下。 ### 6.得到答案 到这儿基本上就没了，答案就是 $h_{rt,1}$ rt是你之前找到的一个初始状态为0的点。 由于一开始我们定义，h伸出的两个头我们只算一个，所以根节点不会被算两遍。 # Analysis 我们只需要把整棵树遍历两边，整体复杂度 $O(n)$ 。 # Code ```cpp #include<bits/stdc++.h> #define int long long using namespace std; inline void read(int& x) { x=0;int y=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} x=x*y; } const int N=500010; int n,l[N],chk[N],f[N][2],g[N][2],h[N][2]; struct node{ int to,nxt; }e[N<<1]; int cnt,head[N]; inline void add(int u,int v){e[++cnt].nxt=head[u];e[cnt].to=v;head[u]=cnt;} char s[N]; void dfs(int x,int fa)//dfs预处理出全是1的子树 { if(l[x])chk[x]=1; for(int i=head[x];i;i=e[i].nxt) { int y=e[i].to; if(y==fa)continue; dfs(y,x); if(!chk[y])chk[x]=0; } } inline int Min(int A,int B,int C,int D,int E,int F) { return min(A,min(B,min(C,min(D,min(E,F))))); } void dfs1(int x,int fa)//树形dp { f[x][l[x]]=0;//初值 for(int i=head[x];i;i=e[i].nxt) { int y=e[i].to; if(y==fa||chk[y])continue; dfs1(y,x); int f0=f[x][0],f1=f[x][1],g1=g[x][1],g0=g[x][0],h1=h[x][1],h0=h[x][0]; f[x][1]=min(f0+f[y][0]+2,f1+f[y][1]+4);//正常转移 f[x][0]=min(f1+f[y][0]+2,f0+f[y][1]+4); g[x][1]=min(min(g0+f[y][0]+2,g1+f[y][1]+4),min(f0+g[y][1]+1,f1+g[y][0]+3)); g[x][0]=min(min(g1+f[y][0]+2,g0+f[y][1]+4),min(f1+g[y][1]+1,f0+g[y][0]+3)); h[x][1]=Min(f0+h[y][0]+2,f1+h[y][1]+4, g0+g[y][0]+2,g1+g[y][1], h0+f[y][0]+2,h1+f[y][1]+4); h[x][0]=Min(f1+h[y][0]+2,f0+h[y][1]+4, g1+g[y][0]+2,g0+g[y][1], h1+f[y][0]+2,h0+f[y][1]+4); } g[x][0]=min(g[x][0],f[x][1]+1);//以x为根转移 g[x][1]=min(g[x][1],f[x][0]+1); h[x][0]=min(h[x][0],g[x][0]); h[x][1]=min(h[x][1],g[x][1]); } signed main(){ freopen("lihtg.in","r",stdin);//教练让我们练习打乱七八糟的文件名emm freopen("lihtg.out","w",stdout); read(n); scanf("%s",s+1); for(int i=1;i<=n;i++)l[i]=s[i]-'0'; for(int i=1,x,y;i<=n-1;i++){read(x),read(y);add(x,y),add(y,x);} int rt=1;for(int i=1;i<=n;i++)if(l[i]==0)rt=i;//找一个初始为0的点 dfs(rt,0); memset(f,0x3f,sizeof(f));//初值 memset(g,0x3f,sizeof(g)); memset(h,0x3f,sizeof(h)); dfs1(rt,0); printf("%lld\n",h[rt][1]); return 0;//完结撒花 } ``` # Conclusion 这题状态设计有三个，在设计dp状态的时候要打开思路，仔细分类，既要不重不漏，也要没有冗余。这样以路径端点是否在子树内的分类也是为我们提供了一种新的思考方向。 想看更多好题？[欢迎光临我的博客qwq](https://www.luogu.com.cn/blog/HZOIHuEnqi/#)