《牛客》-D小红的二进制树

思路：

每个节点有0或1的权值，设f(i)为从i节点出发，向叶子节点走，可以中途停下，所形成的数字中奇数的个数，求所有f(i)。奇数显然就是最后一位为1，所以这实际上就是要求每个节点所在子树权值为1叶结点个数。但又特殊规定：单独的叶节点不服务器托管网能形成一个数，因此叶节点虽然对祖先的f(i)有贡献，但对自己的f(i)无贡献。

所以这个dfs不能写成无返回值，f(i)初始化为当前节点权值，每次都把儿子节点的f(i)加进当前节点f(i)中的形式从，这样会把叶节点的f(i)也算成1。而应该写成有返回值，f(i)初始化为0，f(i)加上子节点递归返回值，返回f(i)加当前节点权值的形式，这样可以保证叶子节点f(i)为0，但仍能向上传递贡献。

当然也可以有别的写法，比如在正常的求权值为1叶节点个数基础上，加上一个将叶节点f(i)记为0。

ACcode:

#include 
using namespace std;
#define int long long
const int N=1e5+10;
string s;
vectorv[N];
int n,f[N];
int dfs(int u,int fa) {
	for(au服务器托管网to x:v[u]) {
		if(x==fa)continue;
		f[u]+=dfs(x,u);
	}
	return f[u]+(s[u]-'0');//这样子就可以让当前节点只能享受到孩子的共享，不能拿到自己的 
}
void solve() {
	cin>>n>>s;
	s=" "+s;
	for(int i=1; i>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,0);
	for(int i=1; i>tt;
	while(tt--)	{
		solve();
	}
	return 0;
}

over~

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: sora会是AGI的拐点么？

作者|谢国斌 来源|神州问学 OpenAI近期发布的Sora是一个文本到视频的生成模型。这项技术可以根据用户输入的描述性提示生成视频，延伸现有视频的时间，以及从静态图像生成视频。Sora可以创建长达一分钟的高质量视频，展示出对用户提示的精准理解和视觉质量的高度…