樹上游戲

給定一棵 $n$ 個(gè)節(jié)點(diǎn)的樹，點(diǎn)從 $1$ 到 $n$ 編號，點(diǎn)有點(diǎn)權(quán)，邊有邊權(quán)， $\text{Alice}$ 和 $\text{Bob}$ 兩人在做游戲。

棋子以某一個(gè)點(diǎn) $s$ 為起點(diǎn)，玩家移動該棋子，有以下兩條規(guī)則：

移動時(shí)不能經(jīng)過已經(jīng)走過的邊

能移動則必須移動，不能在可移動時(shí)停留在原地

由 $\text{Alice}$ 開始，輪流移動棋子，最終的得分為經(jīng)過的點(diǎn)權(quán)之和減去經(jīng)過的邊權(quán)之和。

$\text{Alice}$ 想要最大化得分， $\text{Bob}$ 想要最小化得分，假設(shè)兩人都采取最優(yōu)策略，那么最終得分是多少呢？

請你對于每個(gè)點(diǎn)為起點(diǎn)都輸出一個(gè)答案。
$1\le n\le 10^5,|v_i|,|w_i|\le 10^9$

---

不難發(fā)現(xiàn)當(dāng)起點(diǎn)確定時(shí)可以通過如下樹形dp確定結(jié)果：

狀態(tài)表示：$f_{u,0/1}$以$u$為起點(diǎn)向子樹中移動，當(dāng)前該$\text{Alice}/\text{Bob}$最終的值
狀態(tài)轉(zhuǎn)移：
下面${\text{val}}_u$表示$u$的點(diǎn)權(quán)，$w_i$表示$u\to v$的邊權(quán)

• $\text{Alice}$需要讓結(jié)果盡可能大：$f_{u,0}={\max }_{v\in {\text{son}}_u}(f_{v,1}+{\text{val}}_u?w_i)$
• $\text{Bob}$需要讓結(jié)果盡可能小：$f_{u,1}={\min }_{v\in {\text{son}}_u}(f_{v,0}+{\text{val}}_u?w_i)$

注意：在葉子節(jié)點(diǎn)進(jìn)行初始化

由于存在換根操作，不難發(fā)現(xiàn)只要記錄$f_{u,0}$的最大次大值以及$f_{u,1}$的最小次小值即可從父節(jié)點(diǎn)更新子節(jié)點(diǎn)實(shí)現(xiàn)換根操作。

---

注意這種情況：
當(dāng)前根是$u$，準(zhǔn)備換根到$v$，我們需要讓$u$的信息去更新$v$的信息，如果$v$在樹中是葉子節(jié)點(diǎn)，需要特殊地將$u$的信息直接賦給$v$而不是更新，因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$v$是葉子節(jié)點(diǎn)，在以$u$為根時(shí)走到$v$就會停止，而在以$v$為根時(shí)，并不會停止并且一定會向$u$移動！！！

還有在第一遍dfs時(shí)不能以入度為1的點(diǎn)為根進(jìn)行dfs，因?yàn)檫@個(gè)點(diǎn)在其他點(diǎn)為根的時(shí)是葉子節(jié)點(diǎn)，某些信息會錯(cuò)誤更新比如下面數(shù)據(jù)

5 2147483647 2147483647 2147483647 2147483647 -2147483647 1 2 2147483647 2 3 2147483647 3 4 2147483647 4 5 2147483647

總的來說需要注意葉子節(jié)點(diǎn)的信息的更新

#include<cstring> #include<iostream> #include<algorithm> using namespace std; using ll=long long; constexpr int N=100010; constexpr ll INF=0x3f3f3f3f3f3f3f3f; int h[N],e[2*N],ne[2*N],w[2*N],idx; void add(int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;} int val[N],n; ll f[N][2],g[N][2],ans[N];// f[u][0/1]表示u子樹 該A/B移動 int fr[N][2]; int d[N]; bool leaf[N]; void update(int u,int k,int v,ll x)// 更新 最大次大/最小次小 {if(k==0){if(x>f[u][k]) {g[u][k]=f[u][k];f[u][k]=x;fr[u][k]=v;}else if(x>g[u][k]) g[u][k]=x;}else{if(x<f[u][k]){g[u][k]=f[u][k];f[u][k]=x;fr[u][k]=v;}else if(x<g[u][k]) g[u][k]=x;} } void dfs1(int u,int fa) {leaf[u]=1;for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa) continue;leaf[u]=0;dfs1(v,u);for(int k=0;k<=1;k++)update(u,k,v,f[v][k^1]+val[u]-w[i]);}if(leaf[u]) f[u][0]=f[u][1]=val[u];//葉子節(jié)點(diǎn)初值 } void dfs2(int u,int fa) {ans[u]=f[u][0];for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa) continue;for(int k=0;k<=1;k++){if(leaf[v])//葉子節(jié)點(diǎn)特殊處理{if(fr[u][k]==v) f[v][k^1]=g[u][k]+val[v]-w[i];else f[v][k^1]=f[u][k]+val[v]-w[i];}else//換根{if(fr[u][k]==v) update(v,k^1,u,g[u][k]+val[v]-w[i]);elseupdate(v,k^1,u,f[u][k]+val[v]-w[i]);}}dfs2(v,u);} } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n;memset(h,-1,sizeof h);for(int i=1;i<=n;i++) cin>>val[i];for(int i=1;i<=n;i++) f[i][0]=g[i][0]=-INF,f[i][1]=g[i][1]=INF;for(int i=1;i<n;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c),add(b,a,c);d[a]++,d[b]++;}int rt=1;while(d[rt]==1) rt++;//找一個(gè)度數(shù)不為1的為根dfs1(rt,0);dfs2(rt,0);for(int i=1;i<=n;i++) cout<<ans[i]<<'\n'; }

這題我一共寫了4次
第一次：比賽口胡
第二次：賽后寫代碼沒過懶得調(diào)了
第三次：2021/01/04剛放寒假重新寫，沒注意葉子的細(xì)節(jié)一直沒過
第四次：2021/02/25快開學(xué)了準(zhǔn)備吧收藏夾的題補(bǔ)一補(bǔ)，有看見這個(gè)題，造了造特?cái)?shù)數(shù)據(jù)發(fā)現(xiàn)了代碼問題，注意到葉子細(xì)節(jié)成功AC（經(jīng)歷2.5h）

終于把這題干掉了！！！
要加油哦~

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的OpenJudge1043 树上游戏（换根dp+细节处理）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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