[treeDp][状态分析][dfs] UVa12093 Protecting Zonk

这个题确实是，自己想没有整出来。由于多考虑了一层，状态变得复杂了。

首先还是转化为有根树去做，然后考虑下自底向上的推法。因为这里多考虑一层，所以还需要考虑子节点的放置情况，也就是除了考虑i节点放A/放B/不放，还需要考虑i的子节点，有没有放B/放A/不放，这样的话可以发现所有的情况到最后可以归类为4类，1）i处放B 2）i处放A且子节点放A/放B/没但是其字节点全放A/B，或者i处不放，其字节点至少有一个放B 3）i处不放，但是子节点全为2状态 4）能保证父节点放一个B就能覆盖到往下所有未覆盖路径的任意状态。然后就可以把状态转移方程搞出来，记忆化搜索即可。

自己思考存在的问题：脱离了无后效性这个基本点在想。如果按照一遍dfs来dp的思路，应该是保证了子树推出来之后才能推更高的祖先。

wa的话，因为用了一个cur的变量，之后再用却没有正确赋值。。。

#include

using namespace std;
const int maxn=1e5+5;
const int mod=1e9+7;


vectorG[maxn];
int vis[maxn][4];
int n,c1,c2,u,v;

int d(int i,int s,int p)
{
    if(~vis[i][s])
        return vis[i][s];
    int ans=0;
    int len=G[i].size(),cur;

    for(int j=0;j