louisfghbvc的部落格

題目大意:  問說不取相鄰的點，每個點都有權重。怎麼取能夠讓總和最大。

思路:  樹dp。定義dp[u][0] 表示u這個點不取。dp[u][1] 表示i這個點取值。

用遞迴。先算出子點，再推上父母節點。那麼有2種Case.

首先。 對於 dp[u][0] 來說。我能夠選擇dp[v][1] 或者 dp[v][0] 對吧? 其中v表示u的子節點

如果是dp[u][1] 來說。 那麼只能選擇 子點不取。就是dp[v][1]。

所以說最後答案就會在dp[根][0]或dp[根][1]之間選擇值較大者

看程式碼比較好懂。程式碼這邊cost表示點的權重。最後函式結束記得如果節點取值要加上權重

解這題的先輩知識: 圖的觀念，遞迴，深度優先，動態規劃

時間複雜度 O(N)

代碼: 

#include <bits/stdc++.h>  
  
#define louisfghbvc int t; cin >> t; while(t--)  
using namespace std;  
 
const int N = 1e3+5;  
vector<int> g[N];  
int cost[N];  
int n;  
int dp[N][2];  
   
void dfs(int u, int p = -1){  
    for(int v : g[u]){  
        if(v != p){  
            dfs(v, u);  
            dp[u][1] += dp[v][0];  
            dp[u][0] += max(dp[v][1], dp[v][0]);  
        }  
    }  
    dp[u][1] += cost[u];  
}  
   
void solve(){  
    cin >> n >> cost[1];  
    for(int i = 1; i <= n; ++i) g[i].clear();  
    memset(dp, 0, sizeof dp);  
   
    for(int i = 2; i <= n; ++i){  
        int a;  
        cin >> a >> cost[i];  
        g[a].push_back(i);  
        g[i].push_back(a);  
    }  
   
    dfs(1);  
    cout << max(dp[1][0], dp[1][1]) << "\n";  
}  
   
int main()  
{  
    louisfghbvc
        solve();
    return 0;  
}