P8127题解

· · 题解

题目传送门

做完看题解才发现题解的状态设计和转移都好冗余。

题目很简洁明了，很典型的树形DP的题面，考虑状态设计。

首先将无根树提一个根出来以后，若对一个节点进行操作，只会对其本身、父节点和儿子节点造成影响。而我们不希望进行操作时对父节点产生影响，否则不利于DP，所以考虑强制只对当前节点的儿子节点进行操作。

若状态已知则操作产生的影响很容易计算，因此考虑将节点权值放进状态定义中，而我们需知当前节点和儿子节点的权值（儿子的儿子的权值可以根据儿子的状态确定），因此可以得到状态定义。

每个结点对应 4 个状态：

这里强制定义全部儿子节点的权值相同，且以 i 为根的子树中除去 i 和儿子节点外其余全部节点均为 0。

接下来考虑转移，转移可以考虑每加进一棵子树对当前节点答案的影响，每个状态都有两种转移方式，一种是从相应的状态直接转移过来，一种是对新加的儿子做一次操作转移过来，则可以写出代码。

#include <cstdio>
#include <iostream>
using namespace std;
const int N=100005,MX=1e9;
int pn,cnt,first[N],v[N],dp[N][4];
struct Bian{
    int to,next;
}b[N*2];
void add(int from,int to){
    cnt++;
    b[cnt]=(Bian){to,first[from]};
    first[from]=cnt;
}
void dfs(int now,int f){
    if(v[now]==0){
        dp[now][2]=dp[now][3]=MX;
    }else{
        dp[now][0]=dp[now][1]=MX;
    }
    //初始状态即为单个节点时的状态，此时不用考虑儿子节点，不可能的状态就直接赋为无穷大。 
    for(int i=first[now];i!=0;i=b[i].next){
        if(b[i].to!=f){
            dfs(b[i].to,now);
            int ls0=dp[now][0],ls1=dp[now][1],ls2=dp[now][2],ls3=dp[now][3];
            //一定要将当前的状态记录下来，否则后面的转移会互相影响。 
            dp[now][0]=min(min(ls0+dp[b[i].to][0],ls2+dp[b[i].to][3]+1),MX);
            dp[now][1]=min(min(ls1+dp[b[i].to][2],ls3+dp[b[i].to][1]+1),MX);
            dp[now][2]=min(min(ls2+dp[b[i].to][0],ls0+dp[b[i].to][3]+1),MX);
            dp[now][3]=min(min(ls3+dp[b[i].to][2],ls1+dp[b[i].to][1]+1),MX);
        }
    }
}
int main(){
    scanf("%d",&pn);
    for(int i=1;i<pn;i++){
        int from,to;
        scanf("%d%d",&from,&to);
        add(from,to);
        add(to,from);
    }
    for(int i=1;i<=pn;i++){
        scanf("%d",&v[i]);
    }
    dfs(1,0);
    if(min(dp[1][0],dp[1][3]+1)>=MX){
        printf("impossible");
    }else{
        printf("%d",min(dp[1][0],dp[1][3]+1));
    }
    return 0;
}