33OJ
登录 注册

1 条题解

  • 0
    @ 2026-11-8 22:08:28精华

    这道题是一个树上DP,详解看注释

    #include<iostream>
    #include<vector>
    using namespace std;
    const int N = 6*1e3+10; // 题目最大值
    int n,a[N],dp[N][2]; // dp[i][0/1] 表示第i好节点选/不选
    vector<int> e[N];
    bool fa[N]; // 用来找根节点,表示第x个节点有没有父节点
    void dfs(int x) { // 树上dp
    	dp[x][0] = a[x]; // 如果选,那就自身有这只笔的价值
    	dp[x][1] = 0; // 如果不选,那就没有价值 
    	for(int i = 0;i<e[x].size();i++) { // 枚举子节点
    		int y = e[x][i]; // 子节点
    		dfs(y); // 寻找子节点
    		dp[x][0]+=dp[y][1]; // 如果选了,那下面的子节点就一定不能选
    		dp[x][1]+=max(dp[y][0],dp[y][1]); // 因为这个节点没选,所以下面的子节点可以选或不选
    	}
    }
    int main() {
    	cin>>n;
    	for(int i = 1;i<=n;i++) {
    		cin>>a[i];
    	}
    	for(int i = 1;i<n;i++) {
    		int x,y;
    		cin>>x>>y;
    		e[y].push_back(x); // 这里用有向边,就可以不用判定父节点
    		fa[x] = true; // x有了父节点
    	}
    	int root = 1; // 寻找根节点
    	while(fa[root]) { // 便利每个节点
    		root++;
    	}
    	dfs(root); // dp开始
    	cout<<max(dp[root][0],dp[root][1]); // 根节点选/不选的最大值
    	return 0;
    }
    
    

    信息

    ID
    10
    时间
    1000ms
    内存
    256MiB
    难度
    显示难度普及
    标签
    递交数
    2
    已通过
    2
    上传者