正題

題目鏈接:https://www.luogu.com.cn/problem/P4096

---

題目大意

一個(gè)博弈樹，黑方先手。定義一個(gè)最小的葉子節(jié)點(diǎn)集為黑勝狀態(tài)為黑方勝利集合，白色亦然。求所有既屬于黑方勝利集合有屬于白方勝利集合的點(diǎn)。

---

解題思路

設(shè)$f_{i,0/1}$表示$i$子樹中的最小黑發(fā)/白方勝利集和，然后可以根據(jù)這個(gè)求出所有的勝利集合點(diǎn)。

時(shí)間復(fù)雜度$O(n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2e5+10; struct node{int to,next; }a[N]; int n,tot,ls[N],f[N][2]; bool con[N][2]; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(int x,int j,int k){if(!ls[x]){f[x][k]=1;return;}if(j!=k)f[x][k]=2147483647;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;dfs(y,j^1,k);if(j!=k)f[x][k]=min(f[x][k],f[y][k]);else f[x][k]+=f[y][k];}return; } void solve(int x,int j,int k){if(!ls[x])con[x][k]=1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(j!=k&&f[y][k]!=f[x][k])continue;solve(y,j^1,k);}return; } int main() {scanf("%d",&n);for(int i=2;i<=n;i++){int x;scanf("%d",&x);addl(x,i);}dfs(1,0,0);dfs(1,0,1);solve(1,0,0);solve(1,0,1);int ans1=2147483647,ans2=0,ans3=0;for(int i=1;i<=n;i++)if(con[i][1]&&con[i][0])ans1=(ans1<2147483647)?ans1:i,ans2++,ans3^=i;printf("%d %d %d\n",ans1,ans2,ans3); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的P4096-[HEOI2013]Eden的博弈树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。