BZOJ3037 创世纪[基环树DP]

实际上基环树DP的名字是假的。。

这个限制关系可以看成每个点有一条出边，所以就是一个内向基环树森林。

找出每个基环树的环，然后对于树的部分，做DP，设状态选或不选为$f_{x,0/1}$，则

$f_{x,0}=\sum\limits_{y\in son_x} \max\{f_{y,0},f_{y,1}\}$

$f_{x,1}=\sum\limits_{y\in son_x} \max\{f_{y,0},f_{y,1}\}+[全选了f_{y,1}?]\sum\limits_{y\in son_x} \max\{f_{y,0}-f_{y,1}\}$

这个DP很简单，但是在环上很难处理，因为每个点取不取既和环上前一个点有关也和儿子有关，这个环上的点DP转移是有后效性的。

采用基环树DP另一个常用的手段：断环成树，树形容易处理，避免后效性。断环时，应当注意断开的环上两个点相互影响的关系。

比如此题，每一个点可能会影响后一个点的选择，分两种情况：此点不影响下一个点，则断开后，以此点为根做树形DP，那么两点互不影响，题目条件都成立。

若考虑有影响，则需要这个点不选，让下一个点可以随便选儿子的两个状态较大值而不用担心没有指向他的不选的点。

综上，断边后做两次DP即可。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #define mst(x) memset(x,0,sizeof x)

 #define dbg(x) cerr << #x << " = " << x <<endl

 #define dbg2(x,y) cerr<< #x <<" = "<< x <<"  "<< #y <<" = "<< y <<endl

 using namespace std;

 typedef long long ll;

 typedef double db;

 typedef pair<int,int> pii;

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}

 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}

 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 const int N=1e6+;

 struct thxorz{

     int head[N],nxt[N<<],to[N<<],tot;

     thxorz(){tot=;}

     inline void add(int x,int y){

         to[++tot]=y,nxt[tot]=head[x],head[x]=tot;

         to[++tot]=x,nxt[tot]=head[y],head[y]=tot;

     }

 }G;

 int n;

 #define y G.to[j]

 int vis[N],to,rt,flag,ans,res,ban;

 void dfs(int x){//dbg(x);

     vis[x]=;

     for(register int j=G.head[x];j;j=G.nxt[j])if(!(j&)){

         if(vis[y])return rt=x,to=y,ban=j,void();

         else dfs(y);

     }

 }

 int f[N][];

 void dp1(int x,int fa){

     vis[x]=;int chosen=;f[x][]=;

     for(register int j=G.head[x];j;j=G.nxt[j])if(y^fa&&j^ban&&j^(ban^)){

         dp1(y,x);

         if(f[y][]<f[y][])f[x][]+=f[y][],f[x][]+=f[y][];

         else f[x][]+=f[y][],f[x][]+=f[y][],chosen=;

     }

     if(chosen){

         int tmp=-N;

         for(register int j=G.head[x];j;j=G.nxt[j])if(y^fa&&j^ban&&j^(ban^))MAX(tmp,f[y][]-f[y][]);

         f[x][]+=tmp;

     }//dbg2(x,chosen);

 }

 void dp2(int x,int fa){

     int chosen=;f[x][]=,f[x][]=;

     for(register int j=G.head[x];j;j=G.nxt[j])if(y^fa&&j^ban&&j^(ban^)){

         dp2(y,x);

         if(f[y][]<f[y][])f[x][]+=f[y][],f[x][]+=f[y][];

         else f[x][]+=f[y][],f[x][]+=f[y][],chosen=;

     }

     if(chosen&&x!=to){

         int tmp=-N;

         for(register int j=G.head[x];j;j=G.nxt[j])if(y^fa&&j^ban&&j^(ban^))MAX(tmp,f[y][]-f[y][]);

         f[x][]+=tmp;

     }

 }

 #undef y

 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);

     read(n);

     for(register int i=,x;i<=n;++i)read(x),G.add(i,x);

     for(register int i=;i<=n;++i,res=)if(!vis[i]){

         dfs(i);

         dp1(rt,);//不考虑断环之后根对断点有影响

         res=_max(f[rt][],f[rt][]);

         dp2(rt,);//考虑断环之后根对断点有影响（即不选根）

         MAX(res,f[rt][]);

         ans+=res;

     }

     printf("%d\n",ans);

     return ;

 }

总结：基环树另一种常见做法：断环成树，考虑影响，做两次树形DP。

巴特西

BZOJ3037 创世纪[基环树DP]

最新文章

热门文章