*張浩威老師授課*

樹形DP：即在樹上DP，用dp[i][]...表示以i為根的子樹....。常從根DFS，遞歸轉(zhuǎn)移dp數(shù)組。

沒有上司的舞會--

給定一棵有點權(quán)的二叉樹，選擇若干點，使得選出的點任意兩個點都不相連，且選出的點權(quán)和最大。

n<=100000。

狀態(tài)：dp[i][0/1]表示以i為根的子樹滿足條件時選出的最大點權(quán)和，i節(jié)點選1/不選0。

轉(zhuǎn)移方程：

i不選，則i的兒子可選可不選。

dp[i][0]+=max{dp[l[i]][0],dp[l[i]][1]}+max{dp[r[i]][0],dp[r[i]][1]};

i選：則i的兒子一定都不能選。別忘了加上i的點權(quán)。

dp[i][1]=dp[l[i]][0]+dp[r[i]][0]+a[i];

dfs(root);

ans=max{dp[root][0],dp[root][1]};

沒有上司的舞會

給定一棵有點權(quán)的樹，選擇若干點，使得選出的點任意兩個點都不相連，且選出的點權(quán)和最大。

n<=100000。

只需將轉(zhuǎn)移方程轉(zhuǎn)換一下即可。其中v表示i的兒子節(jié)點

i不選，則i的兒子可選可不選。

dp[i][0]+=max{dp[v][0],dp[v][1]};

i選：則i的兒子一定都不能選。別忘了加上i的點權(quán)。

dp[i][1]=∑{dp[v][0]}+a[i];

dfs(root);

ans=max{dp[root][0],dp[root][1]};

沒有上司的舞會++

給定一個樹套環(huán)，選擇若干點，使得選出的點任意兩個點都不相連，且選出的點權(quán)和最大。

n<=100000。

對于簡單樹套環(huán)題目，可以DFS找環(huán)上的一條邊（即樹的DFS遍歷，沒有遍歷到的邊一定就是環(huán)上的一條邊），然后把該邊的一個端點作為根，把原圖拉成一個樹+邊（u,v）。然后分情況討論。

對于該題：我們以環(huán)上的邊（u,v）的端點u為根，將原圖拉成一棵樹+（u，v）。

當u不選時，v可選可不選，沒有影響。此時邊（u，v）沒有任何意義。

當u選時，v必須不選。我們可以將dp[v][1]=-INF，即答案絕不會從選v的情況dp[v][1]轉(zhuǎn)移。

分別對兩種情況做DFS，最后得出答案。

void dfs1(int x) {

??for(int i=head[x];i;i=e[i].nxt){

int v=e[i].to; ?????

dfs1(v);

}

??for(int i=head[x];i;i=e[i].nxt){

int v=e[i].to;

??????dp[x][0]+=max(dp[v][0],dp[v][1]),

??????dp[x][1]+=dp[v][0];

??}

??dp[x][1]+=a[x];

}

fa[u]=-1;

dfs1(u);

ans=dp[u][0];

dp.clear(); fa.clear();//清空dp與fa數(shù)組

void dfs2(int x)

{

??for(int i=head[x];i;i=e[i].nxt){

int v=e[i].to;

??????dfs2(v);

}

??for(int i=head[x];i;i=e[i].nxt){

??????int v=e[i].to;

dp[x][0]+=max(dp[v][0],dp[v][1]),

??????dp[x][1]+=dp[v][0];

??}

??dp[x][1]+=a[x];

??if (x==V) dp[x][1]=-INF;

}

fa[u]=-1;

dfs2(u);

ans=max(ans,max(dp[u][0],dp[u][1]))

//dfs2使v一定不能被選，所以u是否選擇無所謂

電子眼--

給定一棵二叉樹， 選擇其中若干節(jié)點，設(shè)為特殊節(jié)點，使得每個節(jié)點最近的特殊節(jié)點距離<=1，要求選擇最少的節(jié)點。

n<=100000。

如果一個點離它最近的特殊點距離<=1，則是合法的

dp[i][0/1] 以i為根這棵子樹且合法，且i這個點不設(shè)/設(shè)特殊點，最少需要設(shè)置多少特殊點

dp[i][2] 以i為根的子樹，i的所有子孫都是合法的，并且i不合法，最少需要設(shè)置多少特殊點

考慮三種情況：

dp[x][0] x不是特殊點，但x的兒子中至少有一個是特殊點，其他都合法（x能被兒子照顧到)

dp[x][1] x是特殊點，x的兒子中可以有不是特殊點，也可以有不合法的(x可以照顧兒子)

dp[x][2] x不是特殊點，并且x的兒子都不是特殊點，但都合法(x必須被父親照顧)

dp[x][0]=min{dp[l[x]][1]+dp[r[x]][0],dp[l[x]][0]+dp[r[x]][1],dp[l[x]][1]+dp[r[x]][1]}

dp[x][1]=min{dp[l[x]][0],dp[l[x]][1],dp[l[x]][2]}+min{dp[r[x]][0],dp[r[x]][1],dp[r[x]][2]}+1;

dp[x][2]=dp[l[x]][0]+dp[r[x]][0];

電子眼

給定一棵樹， 選擇其中若干節(jié)點，設(shè)為特殊節(jié)點，使得每個節(jié)點最近的特殊節(jié)點距離<=1，要求選擇最少的節(jié)點。

n<=100000。

dp[x][1]=∑min{dp[v][0],dp[v][1]，dp[v][2]}+1;

dp[x][2]=∑dp[v][0];

dp[x][0]的轉(zhuǎn)移較為麻煩，需要枚舉哪個為特殊點。但我們可以采用一種更為巧妙的做法：dp[x][0]=∑min{dp[v][0],dp[v][1]};

其中必定有一個兒子v'從dp[v'][0]轉(zhuǎn)移到了dp[v'][1]，這一過程一定會產(chǎn)生差值。

我們可以枚舉這一最小差值，然后加入答案中。注意最小差值可能為負數(shù)，因此最小差值需要與0取一個max。

void dfs(int x) {

??for (int i=head[x]; i; i=e[i].nxt){

???? int v=e[i].to;

dfs(v);

}

??// 枚舉哪個兒子是特殊點

??for (int i=head[x]; i; i=e[i].nxt){

???? int v=e[i].to;

??????dp[x][0]+=min(dp[v][0],dp[v][1]);

}

??int MIN=10000000;

for (int i=head[x]; i; i=e[i].nxt){

???? int v=e[i].to;

??????MIN=min(MIN,dp[v][1]-dp[v][0]);

}

??dp[x][0]+=max(0,MIN);//答案累加最小差值

??for (int i=head[x]; i; i=e[i].nxt){

???? int v=e[i].to;

??????dp[x][1]+=min(dp[v][0],dp[v][1],dp[v][2]);

}

??dp[x][1]++;

??for (int i=head[x]; i; i=e[i].nxt){

???? int v=e[i].to;

??????dp[x][2]+=dp[v][0];

}

電子眼++

給定一個樹套環(huán)， 選擇其中若干節(jié)點，設(shè)為特殊節(jié)點，使得每個節(jié)點最近的特殊節(jié)點距離<=1，要求選擇最少的節(jié)點。

n<=100000。

同樣將原圖拉成一個根為u的樹+邊（u，v）

當u為特殊點 v可以為特殊點，也可以不是，也可以不合法。

將dp[u][0]和dp[u][2]的方案設(shè)為不合法，即dp[u][0]=dp[u][1]=INF

ans=min(ans,dp[v][0],dp[v][1],dp[v][2]);

找到環(huán)上的邊(u,v)

把v當做根拉成一棵樹+(u,v)

當u不是特殊點

把u當做根拉成一棵樹=(u,v)

v是特殊點

dp[v][0]=dp[v][2]=INF;

ans=max(ans,dp[u][0],dp[u][2]);

v不是特殊點

dp[v][1]=INF;

ans=min(ans,dp[u][0])

?

最遠距離--

給定一棵帶邊權(quán)的二叉樹，求最遠的兩個點距離是多少。

樹上兩個點的距離一定能分成一段向上走的路徑和經(jīng)過某點后一段向下走的路徑。即

從折點向左子樹走的距離+從折點向右子樹走的距離。

令dp[i]表示以i為根的子樹，從i出發(fā)到達葉子的最遠路徑。

轉(zhuǎn)移方程：dp[i]=max{dp[l[i]]+len[i][l[i],dp[r[i]]+len[i][r[i]]};

//相當于以i為折點的半個路徑

ans=max{ans,dp[l[i]]+len[i][l[i]]+dp[r[i]]+len[i][r[i]]};

//最終直徑為max{ans,左右到葉子的最長路徑加起來}

最遠距離

給定一棵帶邊權(quán)的樹，求最遠的兩個點距離是多少。

同樣令dp[i]表示以i為根的子樹，從i出發(fā)到達葉子的最遠路徑。

只不過狀態(tài)轉(zhuǎn)移方程要換一下。

考慮直徑是由兩段路徑組成，因此我們可以記錄從i出發(fā)的最長路徑與次長路徑，答案由這兩段路徑更新。

void dfs(int x){

??for (int i=head[x]; i; i=e[i].nxt){

???? int v=e[i].to;

dfs(v);

}

for (int i=head[x]; i; i=e[i].nxt){

???? int v=e[i].to;

dp[x]=max(dp[x],dp[v]+len[v]);

}

// len[v] v到它父親的邊的長度

??以x為轉(zhuǎn)折點，最長+次長來更新答案

??int MAX=0,MAX2=0;

for (int i=head[x]; i; i=e[i].nxt){

???? int v=e[i].to;

??????if (dp[v]+len[v]>MAX) {MAX2=MAX; MAX=dp[v]+len[v];}

? else if (dp[v]+len[v]>MAX2)

?MAX2=dp[v]+len[v];

????}

??ans=max(MAX+MAX2,ans);

}

快餐店---

給定一棵帶邊權(quán)有n個點的樹，要求以每個點出發(fā)，最遠能走到哪里，距離是多少。

n<=1000。

可以枚舉每個點DFS找距離最遠的點，時間復(fù)雜度為O(n^2)。

快餐店--

給定一棵帶邊權(quán)有n個點的樹，要求以每個點出發(fā)，最遠能走到哪里，距離是多少。

n<=100000。

不能O（n）枚舉結(jié)點分別DFS，只能一次DFS算出答案。

dp1[i] 表示以i為根的子樹，從i走到葉子的最遠距離

g1[i] dp1[i]是往哪個兒子走的。

dp2[i] 表示以i為根的子樹，從i走到葉子的次長距離。

g2[i] dp2[i]是往哪個兒子走的。

up[i] 表示i先往上再往下的最遠走的長度。

ans[i]=max{dp1[i],up[i]};

?

?

?

葉子的染色-

給定一棵n個節(jié)點的樹，給每個節(jié)點染黑色或者白色或者透明。選擇一個點作為根，已知每個葉子到根最近的有色節(jié)點的顏色是黑色還是白色的。構(gòu)造方案使得有色節(jié)點盡可能少。

n<=1000。

令dp[i][0/1]表示以i為根的子樹中所有葉子滿足條件時，節(jié)點i被染成白色0/黑色1 時的最少有色節(jié)點數(shù)。

不考慮節(jié)點i為透明的原因：仔細思考可以發(fā)現(xiàn)，一定存在一種最優(yōu)解i不是透明的，即節(jié)點i一定被染色。

對于i被染成白色：

若i的兒子v被染成了白色，那么i為白色時，把v褪色不會使答案變得更差，因此從 ?dp[v][0]-1轉(zhuǎn)移而來。

若v為黑色，則v不能去掉，否則不滿足要求。

dp[i][0]=∑min{dp[v][0]-1,dp[v][1]}+1;

同理，i被染成黑色：

dp[i][1]=∑min{dp[v][1]-1,dp[v][0]}+1;

最終ans=min{dp[root][0],dp[root][1]};

root 為我們枚舉的根

葉子的染色

給定一棵n個節(jié)點的樹，給每個節(jié)點染黑色或者白色或者透明。選擇一個點作為根，已知每個葉子到根最近的有色節(jié)點的顏色是黑色還是白色的。構(gòu)造方案使得有色節(jié)點盡可能少。

n<=100000。

我們發(fā)現(xiàn)根其實是不必枚舉的。

u=原來的根，v=現(xiàn)在的根

通過dp轉(zhuǎn)移，可知u與v一定是異色的或有一個是透明的。

當u與v異色時，換根后以u,v為根的子樹中葉子的位置不會改變，因此對答案無影響。

當u與v中有一個為透明時，換根后相當于將兩個點調(diào)換了位置，原來在u上的子樹與原來在v上的子樹互換，答案仍然不變。

因此我們隨便選一個非葉子的結(jié)點為根進行DFS就行了。

轉(zhuǎn)載于:https://www.cnblogs.com/Loi-Brilliant/p/8998161.html

總結(jié)

以上是生活随笔為你收集整理的QBXT 2018春季DP图论班 2018.5.4 --- 树形DP的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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