詳解樹形DP
前言
給定一顆有N個節(jié)點的樹（一般是無根樹，就有N-1條無向邊），可以任選一個節(jié)點作為根節(jié)點
一般以節(jié)點從深到淺（子樹從小到大）的順序作為dp階段順序
dp的狀態(tài)表示中，第一維通常是節(jié)點編號（節(jié)點編號代表了以該節(jié)點為根的子樹）
對于每個節(jié)點x，先遞歸在它的每個子節(jié)點上進行dp，回溯時，從子節(jié)點向x進行狀態(tài)轉移
A - Anniversary part
N個員工，編號為1~N
他們之間有從屬關系，也就是說他們的關系就像一棵以校長為根的樹，父結點就是子結點的直屬上司?，F在有個宴會，宴會每邀請來一個員工 i 都會增加一定的快樂指數 Ri，但如果某個員工的直屬上司來了，那么這個員工就不會來。計算邀請哪些員工可以使快樂指數最大，輸出最大的快樂指數
設 dp [x] [0] 表示在 x 為根的子樹中邀請部分員工，并且 x 不參加時，快樂指數總和的最大值，此時 x 子節(jié)點（直接下屬）可以參加也可以不參加 (s表示x子節(jié)點)
設 dp [x] [1] 表示在 x 為根的子樹中邀請部分員工，并且 x 參加時，快樂指數總和的最大值，此時 x 子節(jié)點（直接下屬）都不能參加，H[x] 表示當前節(jié)點（x）的快樂指數 (s表示x子節(jié)點)
這個題給的是有根樹，就可以從根節(jié)點開始，dp目標就是 max(F[root,0] , F[root,1]) 時間復雜度ON
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> son[10010];
int dp[10010][2];//0不參加，1參加
int v[10010];//記錄有沒有父節(jié)點
int h[10010];//記錄快樂指數
int n;
void DFS(int x){
dp[x][0] = 0;
dp[x][1] = h[x];
for (int i = 0; i < son[x].size(); i++)
{
int y = son[x][i];
DP(y);
dp[x][0] += max(dp[y][0],dp[y][1]);
dp[x][1] += dp[y][0];
}
}
int main(){
cin>>n;
for (int i = 1; i <=n ; i++)
scanf("%d",&h[i]);
for (int i = 1; i <n ; i++)
{
int x,y;
cin>>x>>y;
v[x] = 1;//x有爸爸
son[y].push_back(x);//x是y的子節(jié)點
}
int root;
for (int i = 1; i <= n; i++)
if(!v[i]){ //i沒有爸爸
root = i;
break;
}
DFS(root);
cout << max(dp[root][0],dp[root][1]) << endl;
return 0;
}
B - Strategic game
有n個點，在某些點上放置哨兵，每個哨兵可以監(jiān)控和它有邊相連的點，問監(jiān)視所有的點需要的最少的哨兵數
也就是說一顆n個結點的樹，要求選出其中的一些頂點，使得對于樹中的每條邊(u, v)，u和v至少有一個被選中，要求給出選中頂點數最少的方案
設 dp [x] [0] 表示在不選擇節(jié)點 x 的情況下，以 x 為根節(jié)點的子樹，最少需要選擇的節(jié)點數
當i為葉子節(jié)點時
當i不為葉子節(jié)點時 (s表示x子節(jié)點)
設 dp [x] [1] 表示在選擇節(jié)點 x 的情況下，以 x 為根節(jié)點的子樹，最少需要選擇的節(jié)點數
當i為葉子節(jié)點時
當i不為葉子節(jié)點時 (s表示x子節(jié)點)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define maxn 1508
using namespace std;
int dp[maxn][2];
int soncnt[maxn];
int parent[maxn];
int n;
void DFS(int x) {
int i, d1=0, d0=0;
if (soncnt[x] == 0) {
dp[x][0] = 0;
dp[x][1] = 1;
return;
}
for (i=0; i < n; i++) {
if (parent[i] == x) {
DFS(i);
d1 += min(dp[i][0], dp[i][1]);
d0 += dp[i][1];
}
}
dp[x][1] = d1 + 1;
dp[x][0] = d0;
}
int main() {
int dad, son, m;
while (cin >> n) {
memset(soncnt, 0, sizeof(soncnt));
memset(parent, -1, sizeof(parent));
int root = -1;
for (int i = 0; i < n; i++) {
scanf("%d:(%d)", &dad, &m);
soncnt[dad] = m;
if (root == -1) {
root = dad;
}
while (m--) {
scanf("%d", &son);
parent[son] = dad;
}
}
DFS(root);
cout << min(dp[root][0], dp[root][1]) << endl;
}
return 0;
}
C - Tree Cutting
給一顆n個結點的樹，節(jié)點編號為1~n
問：刪除哪些結點后，剩余各個子樹的大小均小于原總結點數的一半
拆除一個節(jié)點后，剩余部分為其若干兒子的子樹以及該節(jié)點上層所連其余部分（n-size[i]），只要這些連接塊大小都不超過n/2，該節(jié)點就滿足條件。因而我們可以先求出每個節(jié)點所管轄的那棵樹的大小，自下而上地為每個節(jié)點求出其子樹規(guī)模（該點規(guī)模=其兒子的規(guī)模和+1）。
在建樹的時候可以直接用連接表（vector）儲存無向邊，這時由于無法區(qū)分與每個點相連的是其父節(jié)點還是子節(jié)點，會引發(fā)問題：在dfs的時候把父節(jié)點誤認作兒子節(jié)點，解決方法就是在遞歸的時候傳入父節(jié)點編號，然后在遞歸，計算規(guī)模，比較大小的時候避開它就可以了
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int root;
vector<int>G[10000+400];
vector<int>ans;
int sz[10000+400];
void dfs(int par,int u){
sz[u]=1;
for(int i=0;i<(int)G[u].size();i++){
if(G[u][i]!=par)
dfs(u,G[u][i]);
}
int piece=0;
for(int i=0;i<(int)G[u].size();i++)
if(par!=G[u][i]){
sz[u]+=sz[G[u][i]];
piece=max(piece,sz[G[u][i]]);
}
piece=max(piece,n-sz[u]);
if(piece<=n/2)
ans.push_back(u);
}
int main(){
while(cin>>n){
memset(sz,0,sizeof(sz));
int x,y;
for(int i=0;i<n-1;i++){
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs(0,1);
sort(ans.begin(),ans.end());
for(int i=0;i<(int)ans.size();i++)
cout<<ans[i]<<endl;
}
return 0;
}
LCA 最近公共祖先
倍增（基于二分的方法）
假如樹上的兩個點，處于同一深度時，對于往上跳mid步，顯然有單調性：
如果它們往上跳mid步是同一個點，則這個點是它們的共同祖先，但不一定是最近公共祖先
那么如果我們可以快速得到每個點往上跳若干步是誰，顯然我們可以利用二分來求LCA
這個可以用倍增來做。
倍增的思想其實非常簡單，就是利用二進制的思想。一個顯然的結論有：
節(jié)點u往上跳2^(k+1)的布的祖先 = （節(jié)點u往上跳2k布的祖先）往上跳2k布的祖先
用代碼表示就是：
fa[u][k + 1] = fa[ fa[u][k] ][k];
這個的預處理也非常簡單，我們只需要初始化每個fa[u][0]就可以了就可以了，因為接下來的部分都可以根據上面的公式遞推。
然后預處理好這個之后，我們就可以根據這個進行二分了，代碼如下：
int fa[maxn][20], dep[maxn];
void dfs(int u, int f, int d)
{
dep[u] = d;
fa[u][0] = f;
for(int i = 1; i < 20; ++i)
{
fa[u][i] = fa[fa[u][i - 1]][i] - 1;
}
for(int i = head[u]; ~i; i = nxt[i])
{
int t = to[i];
if(t != f)
{
dfs(t, u, d + 1);
}
}
}
int lca(int u, int v)
{
if(dep[u] < dep[v]) swap(u, v);
int k = dep[u] - dep[v];
for(int i = 0; i < k; ++i)
{
if((1 << i) & k) u = fa[u][i];
}
if(u == v) return u;
for(int i = 19; i >= 0; --i)
{
if(fa[u][i] != fa[v][i])
{
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][0];
}
以上就是詳解樹形DP的詳細內容，更多關于樹形DP的資料請關注腳本之家其它相關文章！
相關文章
和一維數組類似，C++?將二維數組名解釋為其第一個元素的地址，而二維數組的第一個元素為一維數組，下面詳細總結下二維數組名的性質,需要的朋友可以參考下2022-09-09
這篇文章主要介紹了C++實現LeetCode(52.N皇后問題之二),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了C語言實現掃雷游戲詳細代碼實例，有感興趣的同學可以借鑒參考下2021-02-02
C語言中開辟內存有很多種方式，目前我們最常用的也就是數組，但數組是在我們用到他之前就得設定好它的長度，有時很不方便。隨意我們來探究動態(tài)內存管理2021-11-11
這篇文章主要介紹了C語言 常量,變量及數據詳解的相關資料,需要的朋友可以參考下2016-10-10
本篇文章是對C++中的關鍵字typename進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了解析C++中派生的概念以及派生類成員的訪問屬性,是C++入門學習中的基礎知識,需要的朋友可以參考下2015-09-09
這篇文章主要給大家介紹了關于C++中對象&類的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-05-05
經典的求解最短路徑算法有這么幾種：廣度優(yōu)先算法、Dijkstra算法、Floyd算法。本文是對?Dijkstra算法的總結，該算法適用于帶權有向圖，可求出起始頂點到其他任意頂點的最小代價以及對應路徑，希望對大家有所幫助2023-03-03
Boost是為C++語言標準庫提供擴展的一些C++程序庫的總稱。Boost庫是一個可移植、提供源代碼的C++庫，作為標準庫的后備，是C++標準化進程的開發(fā)引擎之一，是為C++語言標準庫提供擴展的一些C++程序庫的總稱2022-11-11