题解：小杨寻宝 [GESP202406]

题目等价于要判断是否存在一条最长的链，使得所有宝物都在这条链上
发现题目是一棵树，而树上找一条链的走法是相对唯一的。根据题目要求，我们从树的“一端”走起，如果遇到一个点它的父亲和>=2个叶子都有宝物，那么肯定不行，因为走到叶子后回不来了

进一步抽象，发现只要图中出现下面这个模型那么就无法走到所有宝藏：（假设每个o都代表某个子树）
o-o-o
.... |
....o

判断标准：有一个节点有大于等于三条边都直接或间接地连接到了有宝物的节点，那么就无法得到所有宝物
考虑统计出某个结点x，以x为根节点的子树所包含的宝物数量为f[x]，以x的子节点为根的子树中有宝物的子树数量为s[x]

• 如果s[x]>=3显然不合法
• 如果s[x]>=2，且在其父亲方向存在宝藏（如果 总宝藏数-f[x]>0），那么不合法

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;

int n, a[maxn], f[maxn], s[maxn], sum;
vector<int> T[maxn];
bool flag;

void dfs(int u, int fa){
    f[u] = a[u]; // 初始化
    for(int v : T[u]){
        if(v == fa) continue;
        dfs(v, u);
        f[u] += f[v]; s[u] += (f[v]!=0);
    }
    if(s[u]>=3 || (s[u]>=2 && sum-f[u]>0)) flag = false;
}

void solve()
{
    cin >> n; flag = true; sum = 0;
    for(int i = 1; i <= n; i ++){
        cin >> a[i]; 
        sum += a[i];
        T[i].clear(); f[i] = s[i] = 0;
    }
    for(int i = 1; i <= n - 1; i ++){
        int u, v; cin >> u >> v;
        T[u].push_back(v), T[v].push_back(u);
    }
    dfs(1, 0);
    cout << (flag? "Yes" : "No") << '\n';
}

signed main()
{
    ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T; cin >> T;
    while(T --) solve();
    return 0;
}

---

大神解法：

题目显然等价于问所有宝箱是否在一条链上。

稍微转化一下题意，即我们现在要找到一条链，使得这条链上有宝物的节点数量尽可能多。

想到这里我们发现这个和树的直径比较相似，那么我们直接大胆将深度定义为从根到这个节点上有宝箱节点的数量，然后做一遍树的直径。最后判断直径长度是否等于所有有宝箱节点的数量即可。

做完以后我们发现这道题过了，其实证明也很简单。我们考虑把价值转到边上，即对于所有有宝箱的节点，让它所连的所有边长度都加上一。因为如果一条路径经过这条边，那么它一定也经过这个点，所以这样给边赋权后跑树的直径是对的，即上述思路正确。

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define int long long							
using namespace std;
//using namespace  __gnu_pbds;
//tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> tr;//从小到大
//int findnum(int k){auto it=tr.find_by_order(k-1);return ((it!=tr.end())?(*it):1e9+7);}//查元素
//int findrank(int x){return tr.order_of_key(x)+1;}//查排名
inline int read()
{
	int w=1,s=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
	return w*s;
}
const int maxn=3e5+10;
const int mod=998244353;
const int inf=1e9+7;
int n,a[maxn],dep[maxn];
vector<int> G[maxn];
void dfs(int x,int fa)
{
	dep[x]=dep[fa]+(a[x]==1);
	for(auto y : G[x])
	{
		if(y==fa)continue;
		dfs(y,x);
	}
}
void Main()
{
	n=read();
	for(int i=1;i<=n;i++)dep[i]=0,G[i].clear();
	int sum=0;
	for(int i=1;i<=n;i++)a[i]=read(),sum+=a[i];
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1,0);
	int ma=-1,id=0;
	for(int i=1;i<=n;i++)
	{
		if(dep[i]>ma)
		{
			ma=dep[i];
			id=i;
		}
	}
	for(int i=1;i<=n;i++)dep[i]=0;
	dfs(id,0);
	ma=-1;
	for(int i=1;i<=n;i++)
	{
		ma=max(ma,dep[i]);
	}
	puts(ma==sum?"Yes":"No");
}
signed main()
{
#ifdef Lydic
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
	int T=read();
	while(T--)Main();
    return 0;
}