本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-19 11:16:11

题目
目标：在以最小的遍历次数通关地图的前提下，从地图内刷到的药水最多，输出药水数量。
下面我们开始分析。

最小的遍历次数：

在最优策略下，我们到达任意一点后，如果他有子节点，那么我们会继续向下遍历。
故最小的遍历次数为子树内叶结点的数量，我们可以用一遍 dfs 来统计以 $u$ 点为根节点的子树内叶结点的数量，我们用 $g_u$ 表示。
设 $v$ 点为 $u$ 点的子结点，易得转移方程：
$$g_u=\sum g_v$$

最大药水数量：

在以 $u$ 点位根节点的子树内能拾取到的药水数量我们用 $f_u$ 表示，其必然由其子结点转移而来，设其子结点为 $v$ 点。
在遍历之后出现的药水自然无法捡到，那设 $u$ 点能捡到的药水的数量为 $a_u$，那么在任意一颗子树内，它最多遍历 $g_u$ 次，最多能拾取到的药水数量为 $(\sum f_v)+a_u$，易得转移方程：
$$f_u=\max(g_u,(\sum f_v)+a_u)$$ $f_1$ 便为答案。
代码：

#include<bits\/stdc++.h>
#define INF 2147483647
#define int long long
#define endl '\n'
#define inl inline
#define reg register
using namespace std;
const int N=1e5+5;
vector<int>g[N];
int n,p[N],u,v,ye[N],yao[N];
bool flag[N],vis[N];
\/*
n,p如题所述，g,u,v为了建树，ye,yao等同于上述g,f,a(yao代替了f,a)
*\/
inl int read(){\/\/快读
	reg int f=1,x=0;
	reg char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
inl void write(int x){\/\/快写
	if(x<0) x=-x;
	if(x>=10) write(x\/10);
	putchar(x%10^48);
}
inl void dfs1(int now){\/\/求叶结点数
	flag[now]=true;
	for(reg int i=0;i<g[now].size();++i)
		if(!flag[g[now][i]]){
			dfs1(g[now][i]);
			ye[now]+=ye[g[now][i]];
		}
	flag[now]=false;
	return;
}
inl void dfs2(int now){\/\/求拾取药水数
	flag[now]=true;
	for(reg int i=0;i<g[now].size();++i)
		if(!flag[g[now][i]]){
			dfs2(g[now][i]);
			yao[now]+=yao[g[now][i]];
		}
	yao[now]=min(yao[now],ye[now]);
	flag[now]=false;
	return;
}
signed main(){
	n=read();
	for(reg int i=1;i<=n;++i) p[i]=read();
	for(reg int i=1;i<n;++i){
		u=read();
		v=read();
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(reg int i=2;i<=n;++i)
		if(g[i].size()==1) ye[i]+=1;
	dfs1(1);
	for(reg int i=1;i<=ye[1];++i) ++yao[p[i]];
	dfs2(1);
	write(yao[1]);
	return 0;\/\/结束
}