牛客周赛 Round 15 D 游游的树上边染红(树形dp)

牛客周赛 Round 15 D 游游的树上边染红(树形dp)

一道很裸的树形dp，周日晚上看了一晚上看不懂，第二天突然就悟了。
题目跟没有上司从舞会很像，我们粗略的考虑，当前节点的状态为选/不选，然后根据此进行状态转移。

不选择当前点：$dp[u][0]$,表示我不选以节点 u 为上节点的边，那么对于 u 的所有子节点，我选择其状态的最大值即可。
即：
$$dp[u][0]+=max(dp[v][0],dp[v][1]),v为u的子节点$$

选择当前点：$dp[u][1]$,表示我选择了以节点 u 为上节点的边，则需要去对 u 与其所有子节点的边进行遍历，取最大值即可。

$$dp[x][1]=max(dp[x][1],dp[x][0]-max(dp[u][0],dp[u][1])+dp[u][0]+w)$$

该方程的状态转移解释为：我若是选择了该边，那么对于子节点 v ，我只能取其不选的状态，即$dp[v][0]$,而又因为我是选择的 $u-v_i$这条边，所以不影响 u 对于其他边的选择，我只需要对其他子节点的状态依旧取 max 即可。

#include 

using namespace std;
const int N = 2e6 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"

int n;
vector<pll> e[N];

void add(int u,int v,int w)
{
	e[u].push_back({v,w});
	e[v].push_back({u,w});
}
ll dp[N][2];

void dfs(int x,int f)
{
	ll sum=0;
	for(auto [u,w]: e[x]){
		if(u!=f){
            dfs(u,x);
			dp[x][0]+=max(dp[u][0],dp[u][1]);
			//sum+=max(dp[u][0],dp[u][1]);
		}
	}
	for(auto [u,w]: e[x]){
        if(u!=f)
		dp[x][1]=max(dp[x][1],dp[x][0]-max(dp[u][0],dp[u][1])+dp[u][0]+w);
	}
    //cout<
}

void solve()
{	
	cin>>n;
	for(int i=1;i<=n-1;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	dfs(1,-1);
	cout<<max(dp[1][0],dp[1][1])<<endl;
}

int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
	//cin>>t;
	while(t--){
		solve();
	}
    system("pause");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64