真的是假的吗?

题解 P4096 【[HEOI2013]Eden 的博弈树 】
题解

emm,一开始看这题感觉很难的样子

然后看了好久才看明白题意

看懂题意后其实做法其实并不难

就是先Dfs染一遍色

黑节点的儿子是白点,白点的儿子是黑点

然后用 f[i][j] 来表示i这个点为j方赢时最少控制的关键节点数

怎么求关键节点数目 ?

以黑方为例 :

  • 如果该点是白点,则只有其所有的儿子都是黑节点

  • 如果该点是黑点,则只需要有一个儿子是黑点

最后再Dfs一遍把黑方白方的关键节点书都求出来,最后统计答案时就将黑白关键节点取个并集就好辣


#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
const int M = 200005 ;
const int INF = 2147483646 ;
using namespace std ;
inline int read(){
    char c = getchar() ;int x=0,w=1;
    while(c>'9'||c<'0'){ if(c=='-') w=-1; c = getchar() ;}
    while(c>='0'&&c<='9'){ x = x*10+c-'0';c = getchar() ;}
    return x*w ;
}
struct E{
    int nex,to;
}edge[M<<1];
int hea[M] , num ;
inline void add_edge(int from,int to){
    edge[++num].nex = hea[from] ; 
    edge[num].to = to ;
    hea[from] = num ;
}
int n ;
int col[M] , f[M][2] ;
bool Control[M][2] , Son[M] ;
int MinAns = INF , Ansnum , Anstot ;

void Dye(int u){
    if(!Son[u]) f[u][0] = f[u][1] = 1 ;
    for(int i=hea[u];i;i=edge[i].nex){
        int v = edge[i].to ;
        col[v] = col[u]^1 ;
        Dye(v) ;
    }
}
void Dfs(int u,int j){
    if(j == col[u] && !f[u][j] ) f[u][j] = INF ; 
    for(int i=hea[u];i;i=edge[i].nex){
        int v = edge[i].to ;
        Dfs(v,j) ;
        if(j == col[u]) f[u][j] = min(f[u][j] , f[v][j]) ;
        else f[u][j] += f[v][j] ;
    }
}
void Ldfs(int u,int j){
    int tmp = INF ;
    for(int i=hea[u];i;i=edge[i].nex){
        int v = edge[i].to ;
        if(j==col[u]) tmp = min(tmp,f[v][j]) ;
        else Ldfs(v,j) ;
    }
    if(j==col[u]&&Son[u])
      for(int i=hea[u];i;i=edge[i].nex){
        int v = edge[i].to ;
        if(f[v][j]==tmp)
          Ldfs(v,j) ;
      }
    if(!Son[u]) Control[u][j] = 1 ;
}
int main(){
    n = read() ;
    for(int i=2;i<=n;i++){
        int x = read();
        Son[x] = 1 ;
        add_edge(x,i) ;
    }
    col[1] = 1 ;
    Dye(1) ;
    Dfs(1,1) ; Dfs(1,0) ;
    Ldfs(1,1) ; Ldfs(1,0) ;
    for(int i=1;i<=n;i++)
      if(Control[i][0]&Control[i][1]){
        MinAns = min(MinAns,i) ;
        Ansnum++ ;
        Anstot ^= i ;
      }
    printf("%d %d %d\n",MinAns,Ansnum,Anstot) ;
    return 0;
}
评论