${}_{{}^{{}_{謹以此文表達筆者個人觀點，如有冒犯官解，可在評論區訴說}}}$

題面

原題

天體風暴中的氣象瞬息萬變。

風暴中的道路構成一棵 $n$ 個結點的無根樹，第 $i$ 個結點有初始權值 $w_i$（$w_i$ 為 $0$ 或 $1$）和類型 $t_i$。

結點的類型分為兩種：$\text{AND}$ 型結點和 $\text{OR}$ 型結點。

對于 $\text{AND}$ 型結點，每一秒結束后它的權值將變為它與它所有鄰居上一秒權值的 $\text{AND}$ 和；

對于 $\text{OR}$ 型結點，每一秒結束后它的權值將變為它與它所有鄰居上一秒權值的 $\text{OR}$ 和。

現在，已知從某一時刻起，所有結點的權值都不再發生任何變化，將此時點 $i$ 的權值稱為 $a_i$。

現不知每個點的初始權值和類型，只知道最終每個點的權值 $a_i$，求出有多少種可能的初始權值和類型的組合，答案對 $998244353$ 取模。

$2\le n\le 2\times 10^5,1000\mathtt{m}\mathtt{s},256\mathtt{M}\mathtt{B}$ .

題解

我們可以發現，$\mathtt{A}\mathtt{N}\mathtt{D}$ 類型一但接觸到 0，就會保持 0 永久不變，$\mathtt{O}\mathtt{R}$ 類型一旦接觸到 1，就會保持 1 永久不變。所以，最終的情況，一定是由權值為 1 的 $\mathtt{O}\mathtt{R}$ 、權值為 0 的 $\mathtt{A}\mathtt{N}\mathtt{D}$ 、四周全是 1 的 $\mathtt{A}\mathtt{N}\mathtt{D}$ 和 四周全是 0 的 $\mathtt{O}\mathtt{R}$ 組成。

我講的盡量形象一點吧。

---

我們先看 0 和 1 的交界處，它們比較特別。

這些地方能一直保持這種 “劍拔弩張” 的狀態，想必交界處的兩個點不簡單。簡單假設推理一下就會發現，邊界處的 1 一定是 $\mathtt{O}\mathtt{R}$ 形，因為它們是 “親 1” 的，能守其 1，義不變 0，如果是 $\mathtt{A}\mathtt{N}\mathtt{D}$ 形就守不住 1 了，和緊挨著的 0 只用接觸一回合，就永遠變成 0 了。同理，0 那邊一定是 $\mathtt{A}\mathtt{N}\mathtt{D}$ 形的 0 了。

我們不妨把這兩種結點稱之為 “哨兵”，每一個 1 的連通塊、或者 0 的連通塊邊上（邊上指的是0,1交界處）都必須有哨兵把守。當然，這并不代表連通塊內部就沒有哨兵了。

類似的，1-連通塊內的 $\mathtt{A}\mathtt{N}\mathtt{D}$ 、0-連通塊內的 $\mathtt{O}\mathtt{R}$ 這兩種朝三暮四的結點，不妨把它們稱之為 “庶民” 。

一開始，并不一定每個哨兵都是自己應該的權值（1-連通塊內為 1，0-連通塊內為 0），它們可能 “未激活”（呈現為敵方的權值），一個未激活的哨兵是可以被身邊的 “親和權值” 給感染、然后激活的，這其中包括身邊的激活的友方哨兵(出于呼喚)或未激活的敵方哨兵(出于警覺)。

但是，庶民的搖擺不定就決定了，任何時刻，庶民和 “敵對勢力” 或者未激活的友方哨兵(畢竟帶有敵方的權值)中間都必須有激活的哨兵相隔。

---

這么想，那么最初就可能是這樣：每個連通塊內有若干個小塊，這些小塊周圍是一圈激活的哨兵，內部是哨兵或庶民，連通塊內除了這些小塊以外的地方，全是未激活的哨兵。隨著時間推移，未激活的哨兵漸漸全部激活，最終形成輸入中的模樣。

但對于每個連通塊，還有一種情況：一開始就全是未激活的哨兵！庶民不識抬舉，要他們何用 這種情況，連通塊四周一定得有至少一個敵方的未激活哨兵相鄰才行，不然會被圍剿死 不然就全都激活不了了。

---

好，接下來，就可以著手設計 DP 了。

同權值的連通塊一開始是已知的。每個點最初的狀態有三種 ：未激活的哨兵，激活的哨兵，庶民。分別用 1，2，3 型表示吧，我們設計 $dp1[i]$，$dp2[i]$，$dp3[i]$ 表示結點 $i$ 先不考慮父親的情況下為 1、2、3 型時，$i$ 子樹的方案數。

但是對于一開始就全是未激活哨兵的情況不好處理，于是我們就令 $dp1[i][1]$ 為原先的 $dp1[i]$ ，令 $dp1[i][0]$ 為 $i$ 結點所在連通塊（暫不考慮其父親）全是未激活哨兵、并被圍剿死的情況下，子樹的方案數，也就是不合法的方案數。

這四者初始值都為 1，因為要做乘法。最后 $dp1[i][1]$ 要減去 $dp1[i][0]$ ，即減去不合法。

如果掃描到某個兒子 $j$，與自己在同一個連通塊內（$a_i=a_j$），那么：

• $dp1[i][0]\leftarrow dp1[i][0]?dp1[j][0]$ ，這個很明顯，兒子也得被圍剿才行。
• $dp1[i][1]\leftarrow dp1[i][1]?(dp1[j][0]+dp1[j][1]+dp2[j])$ ，這是還未減去不合法情況下的 $dp1[i][1]$ ，所以當然要兼容并包，同時未激活的哨兵可以緊挨著激活的哨兵，所以要算上 $dp2[j]$ 。
• $dp2[i]\leftarrow dp2[i]?(dp1[j][0]+dp1[j][1]+dp2[j]+dp3[j])$ ，已經激活的哨兵在連通塊內，說明不符合“全是未激活哨兵” 這種假設了，兒子認為的被圍剿死的方案 ($dp1[j][0]$)，到父親這兒又行了。同時，激活的哨兵身邊什么人都可以有，自然就全盤轉移過來。
• $dp3[i]\leftarrow dp3[i]?(dp2[j]+dp3[j])$ ，庶民身邊只能是庶民或激活的哨兵，這個不必細說。

如果掃描到某個兒子 $j$ 與自己在不同連通塊的話（$a_i=a_j$）：

• $dp1[i][0]\leftarrow dp1[i][0]?dp2[j]$ ，既然被對方圍剿，那就是和激活的敵方哨兵相鄰了。
• $dp1[i][1]\leftarrow dp1[i][1]?(dp1[j][0]+dp1[j][1]+dp2[j])$ ，對方可以是激活或未激活的哨兵，這個不用說。主要是 $dp1[j][0]$ ，由于父親是未激活的哨兵，兒子認為的被圍剿死的方案，因父親放了生路，又行了。
• $dp2[i]\leftarrow dp2[i]?(dp1[j][1]+dp2[j])$ ，激活的哨兵，兒子被圍剿就是被圍剿，和上面相比，不能轉移過來。
• $dp3[i]\leftarrow 0$ ，庶民怎么能跑到邊境呢？直接清零。

最后再來一個 $dp1[i][1]\leftarrow (dp1[i][1]?dp1[i][0])$ 。

至此，轉移就理清了，最終答案是 $dp1[Root][1]+dp2[Root]+dp3[Root]$。時間復雜度 $O(n)$ 。

CODE

精煉的代碼

#include<map> #include<set> #include<stack> #include<queue> #include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define MAXN 200005 #define ENDL putchar('\n') #define LL long long #define DB double #define lowbit(x) ((-x) & (x)) LL read() {LL f = 1,x = 0;char s = getchar();while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}return f * x; } const int MOD = 998244353; int n,m,i,j,s,o,k; vector<int> g[MAXN]; int inv[MAXN]; int a[MAXN]; int dp1[MAXN][2],dp2[MAXN],dp3[MAXN]; // 1,2,3 void dfs(int x,int ff) {dp1[x][0] = dp2[x] = dp3[x] = 1;dp1[x][1] = 1;for(int i = 0;i < (int)g[x].size();i ++) {int y = g[x][i];if(y != ff) {dfs(y,x);if(a[y] == a[x]) { dp1[x][1] = (0ll+dp1[y][0] + dp1[y][1] + dp2[y]) % MOD *1ll* dp1[x][1] % MOD;dp1[x][0] = dp1[y][0] *1ll* dp1[x][0] % MOD;dp2[x] = (0ll+dp1[y][0]+dp1[y][1] + dp3[y] + dp2[y]) % MOD *1ll* dp2[x] % MOD;dp3[x] = (dp2[y] + dp3[y]) % MOD *1ll* dp3[x] % MOD;}else {dp1[x][1] = (0ll+dp1[y][1] + dp1[y][0] + dp2[y]) % MOD *1ll* dp1[x][1] % MOD;dp1[x][0] = (dp2[y]) % MOD *1ll* dp1[x][0] % MOD;dp2[x] = (dp1[y][1] + dp2[y]) % MOD *1ll* dp2[x] % MOD;dp3[x] = 0;}}}(dp1[x][1] += MOD-dp1[x][0]) %= MOD;return ; } int main() {n = read();for(int i = 1;i <= n;i ++) {a[i] = read();}inv[0] = inv[1] = 1;for(int i = 2;i <= n;i ++) {inv[i] = (MOD-inv[MOD % i]) *1ll* (MOD/i) % MOD;}for(int i = 1;i < n;i ++) {s = read();o = read();g[s].push_back(o);g[o].push_back(s);}dfs(1,0);int ans = (0ll+dp1[1][1]+dp2[1]+dp3[1]) % MOD;printf("%d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的P7727 风暴之眼 Eye of the Storm （树形 DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。