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

· · 题解

思路

根据题意我们可以知道，不管寻宝的路线怎么安排，都不能走回头路。

也就是说，一个节点最多只会被访问一次，从这个节点出去了就不能回来了。

那么，如果有一个节点有大于等于三条边都直接或间接地连接到了有宝物的节点，那么就无法得到所有宝物，我们暂且称之为不幸点。

我们以下图为例：

显然 1 号节点是不幸点。假设四个节点都有宝物。

如果以 1 号节点为起点，那么不论下一步去哪个节点，都不可能再回来了，也就不可能获得另外两个节点的宝物。

如果以另外三个节点中的一个为起点，那么走到 1 节点后就会遇到岔路口，只能进行二选一的选择，也无法获得全部的宝物。

同理可得，如果 1 号节点连接了大于三条边，同样无法获得全部宝物。

如果 2、3、4 号节点连接了其他节点，那么不管其他节点与这三个节点怎么连接，最后都会在 1 号节点这里面临选择。

现在考虑如何 O(n) 求出一棵树上是否有不幸点。

我们记树上有宝物的节点的数量为 b，以 x 为根节点的子树所包含的宝物数量为 ans_x，以 x 的子节点为根的子树中有宝物的子树数量为 p_x。

当 p_x > 2 的时候，节点 x 为不幸点。

我们知道，除根节点和叶子节点之外，所有的节点都会有一条连接父亲节点的边和若干连接子节点的边。

那么，当 ans_x \ne b 的时候就说明节点 x 的父亲节点的方向的节点（即不属于以 x 为根的子树的节点）中一定有宝物。那么，当 p_x > 1 的时候，节点 x 为不幸点。

综上，当 p_x > 2 时，或者当 ans_x \ne b 且 p_x > 1 时，节点 x 为不幸点。

如何求 ans_x 呢？很简单，只需要把节点 x 的所有子节点的 ans 加起来，如果节点 x 有宝物的话再加 1。

由于无论哪个节点作为根节点都不会影响结果，所以我们可以从任意一个节点出发，在遍历整棵树的过程中进行求解。

代码

#include<bits/stdc++.h>
using namespace std;

bool flag;//记录能否获得全部宝物 
int t,n,b;//b 代表树上共有多少个节点有宝物 
int a[100005];
vector <int> vec[100005];

int search(int x,int f)//返回以 x 为根节点的树（子树）共有多少个结点有宝物。f 代表 x 的父亲节点。 
{
    if(vec[x].size()==1&&vec[x][0]==f)
    {
        return a[x];
    }
    int ans=0,p=0;//ans 记录所有以 x 为根节点的子树的宝物总数，p 记录以 x 的子节点为根的子树中有多少棵子树有宝物 
    for(int i:vec[x])//遍历节点 x 的所有边 
    {
        if(i!=f)
        {
            int l=search(i,x);
            if(l)
            {
                p++;
                ans+=l;
            }
        }
    }
    ans+=a[x];
    if((ans!=b&&p>1)||p>2)flag=false;//发现不幸点 
    return ans;
}

int main()
{
    cin>>t;
    while(t--)
    {
        flag=true;
        b=0;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            vec[i].clear();//多测要清空 
            cin>>a[i];
            if(a[i])b++;
        }
        for(int i=1;i<n;i++)
        {
            int x,y;
            cin>>x>>y;
            vec[x].push_back(y);
            vec[y].push_back(x);
        }
        search(1,0);//树的根节点可以随便取一个 
        if(flag)
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }
    }
}

拒绝抄袭，从我做起。