P11249 [GESP202409 七级] 小杨寻宝 题解

linjinkun · 2024-11-23 14:29:56 · 题解

提供一种没有在题解区出现的解题思路。

使用树形 dp。

设 f_x 表示以 x 为路径起点或终点最大能拿到多少宝藏。

那么状态转移是 f_x = \max(f_v+a_x)。v 指的是 x 的儿子，你以为这么简单？不不不，还没完，因为如果有条路径并非是 x 作为起点或终点怎办？所以我们还需要找到 x 的两个儿子 v1 和 v2，v1 \not= v2，f_{v1}+f_{v2}+a_x 就是 x 不作为路径起点或终点时的贡献，自然地，我们要使 f_{v1}+f_{v2}+a_x 最大化，也就是使 f_{v1}+f_{v2} 最大化，那就只需要找到 x 的儿子中 f 最大的和第二大的就行了。解释一下为什么是 f_{v1}+f_{v2}+a_x，请看下图：

假设 x 是 1，那么它作为中点（就是不是起点也不是终点），他只能用以 2 开头的路径中最大拿宝藏数量加上以 3 开头的路径中最大拿宝藏数量再加上当前节点是否有宝藏，因为它只能找到两个不同的儿子进行扩散，所以就是 f_{v1}+f_{v2}+a_x。

记得清空！！！

代码（有注释）：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int a[N];
vector<int>e[N];
int f[N];
int maxx;
void dfs(int x,int fa)
{
    f[x] = a[x];
    int maxxx = 0;
    int ans = 0;
    for(int i = 0;i<e[x].size();i++)
    {
        int v = e[x][i];
        if(v!=fa)
        {
            dfs(v,x);
            if(ans<f[v])//求最大的
            {
                ans = f[v];
                maxxx = v;
            }
            f[x] = max(f[x],f[v]+a[x]);
        }
    }
    int maxxxx = 0;
    int ans1 = 0;
    for(int i = 0;i<e[x].size();i++)
    {
        int v = e[x][i];
        if(v!=fa)
        {
            if(ans1<f[v]&&v!=maxxx)//求第二大的
            {
                ans1 = f[v];
                maxxxx = v;
            }
        }
    }
    maxx = max(maxx,max(f[x],ans+ans1+a[x]));
}
int main()
{
    int _;
    scanf("%d",&_);
    while(_--)
    {
        memset(f,0,sizeof(f));//记得清空！！！
        int num = 0;
        int flag = 0;
        int n;
        scanf("%d",&n);
        for(int i = 1;i<=n;i++)
        {
            e[i].clear();//这里也清空哦，很容易漏！！
            scanf("%d",&a[i]);
            if(a[i])
            {
                num++;
            }
        }
        for(int i = 1;i<n;i++)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            e[x].push_back(y);
            e[y].push_back(x);
        }
        maxx = 0;//这里也得重置
        dfs(1,0);
        printf("%s\n",maxx>=num?"Yes":"No");
    }
    return 0;
}