P3549 [POI2013]MUL-Multidrink 题解--zhengjun
A_zjzj
·
·
题解
其他题解都是大码量的直接构造，来一发 dp 的题解。
思路很明确，直接 dp，然后输出路径即可。
考虑先把 1\to n 的路径找出来，记为 a_i(1\le i\le m)。
那么肯定存在一种路径依次经过这些点的子树，然后遍历完 a_i 的子树后再遍历 a_{i+1} 的子树。
这样的话，每个 a_i 的子树就各自独立了，所以分别对每个子树进行求解。
遍历子树
由于每次最多只能跳 2 步，所以如果要遍历 u 的子树内的所有点，那么只有以下几种情况：
观察这些情况，发现第二种和第四种本质上是一样的，无非就是遍历顺序正反而已，先合并为一种。
于是，设 f_{u,i=0/1/2} 分别为上述的第 i+1 中情况是否可行。
考虑如何转移：
f_{u,0}=[u\ is\ \texttt{leaf}];
即 $f_{u,1}=\operatorname{and}_{v\in son(u)}f_{v,0}/f_{v,1}$，其中只能有一个 $f_{v,1}$。
所以转移就是：
```cpp
f[u][1]=1;
int t1=0;
for(int v:A[u])if(v^fa&&!vis[v]){
dfs(v,u);
if(!f[v][0])
if(!f[v][1])f[u][1]=0;
else if(++t1>1)f[u][1]=0;
}
```
$f_{u,2}$ 的话就是要有两个儿子可以先到 $v$，再从 $v$ 的儿子跳出或先到 $v$ 的儿子再从 $v$ 跳出（两个儿子的遍历顺序决定了是属于第二种还是第四种，先遍历到的选择第二种，后遍历到的选择第四种）。
转移如下：
```cpp
f[u][2]=1;
int t2=0;
for(int v:A[u])if(v^fa&&!vis[v]){
dfs(v,u);
if(!f[v][0])
if(!f[v][1])f[u][2]=0;
else if(++t2>2)f[u][2]=0;
}
```
这样 $f$ 就可以 $O(n)$ 完成转移了。
#### 遍历 $1\to n$ 的链
设 $g_{i,0/1}$ 表示 $a_i$ 的子树遍历完之后，在 $u$ 或 $u$ 的某个儿子，是否可行。
这样就很简单了，枚举 $a_i$ 和 $a_{i+1}$ 的状态，选择合适的 $f_{a_{i+1}}$ 进行转移即可。
转移见代码，其实并不难，复杂度也是 $O(n)$。
### 总结
至此，我们已经完成了 $f,g$ 的转移，判断有解无解，然后按照转移的方式输出 dp 的路径即可。
具体实现见代码，总复杂度：$O(n)$。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;using ll=long long;const int N=5e5+10;
int n,m,top,a[N],stk[N],vis[N],f[N][3],g[N][2];vector<int>ans,A[N];
void add(int u,int v){A[u].push_back(v);A[v].push_back(u);}
void find(int u,int fa=0){
stk[++top]=u;if(u==n)copy(stk+1,stk+1+top,a+1),m=top;
for(int v:A[u])if(v^fa)find(v,u);stk[top--]=0;
}
void dfs(int u,int fa=0){
f[u][0]=f[u][1]=f[u][2]=1;
int t=0,t1=0,t2=0;
for(int v:A[u])if(v^fa&&!vis[v]){//f 的转移
t++;dfs(v,u);
if(!f[v][0])if(!f[v][1])f[u][1]=0;else if(++t1>1)f[u][1]=0;
if(!f[v][0])if(!f[v][1])f[u][2]=0;else if(++t2>2)f[u][2]=0;
}
if(t)f[u][0]=0;else f[u][1]=f[u][2]=0;//特判叶子节点
}
void findf(int u,int i,int fa=0){
if(!i){
ans.push_back(u);//叶子节点
}
else if(i==1){//u 开始,v 结束
ans.push_back(u);//因为是 u 开始,所以直接把 u 扔进去就好了
for(int v:A[u])if(v^fa&&!vis[v]){//先遍历非叶子
if(!f[v][0])findf(v,3,u);
}
for(int v:A[u])if(v^fa&&!vis[v]){//再遍历叶子
if(f[v][0])findf(v,0,u);
}
}
else if(i==2){//v 开始,v' 结束
int t=0;
for(int v:A[u])if(v^fa&&!vis[v]){
if(!f[v][0])t++;
}
if(t==1)return findf(u,1,fa);//必须要找到两个不同的 v 和 v',否则就是第 2 种情况
t=0;
for(int v:A[u])if(v^fa&&!vis[v]){
if(!f[v][0]){
if(!t)findf(v,1,u),ans.push_back(u),t++;
else findf(v,3,u);
//第一个 v 先到 v,再到儿子
//第二个 v' 先到儿子，再到 v'
}
}
for(int v:A[u])if(v^fa&&!vis[v]){
if(f[v][0])findf(v,0,u);//最后遍历叶子节点
}
}else{//与情况 2 类似,倒着做就好了
for(int v:A[u])if(v^fa&&!vis[v]){
if(f[v][0])findf(v,0,u);
}
for(int v:A[u])if(v^fa&&!vis[v]){
if(!f[v][0])findf(v,1,u);
}
ans.push_back(u);
}
}
void findg(int i,int j){//g 的路径输出
if(i==1){
findf(i,j);
return;
}
int u=a[i];
if(j==0){//直接照搬转移的方程即可
if(g[i-1][0]&f[u][0])return findg(i-1,0),findf(u,0);
if(g[i-1][0]&f[u][1])return findg(i-1,0),findf(u,3);
findg(i-1,1);findf(u,0);
}else{
if(g[i-1][0]&f[u][1])return findg(i-1,0),findf(u,1);
if(g[i-1][0]&f[u][2])return findg(i-1,0),findf(u,2);
findg(i-1,1);findf(u,1);
}
}
int main(){
scanf("%d",&n);for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),add(u,v);
find(1);for(int i=1;i<=m;i++)vis[a[i]]=1;for(int i=1;i<=m;i++)dfs(a[i]);
g[1][0]=f[1][0];g[1][1]=f[1][1];//g 的初始化
for(int i=2,u;u=a[i],i<=m;i++){//g 的转移
g[i][0]|=g[i-1][0]&(f[u][0]|f[u][1]);
g[i][0]|=g[i-1][1]&f[u][0];
g[i][1]|=g[i-1][0]&(f[u][1]|f[u][2]);
g[i][1]|=g[i-1][1]&f[u][1];
}
if(!g[m][0])return puts("BRAK"),0;//注意最后要落在 n，所以 g[m][1] 没有用
findg(m,0);
for(int x:ans)printf("%d\n",x);
return 0;
}
```
### 谢谢您的阅读，有问题请指出