首页 > 试题广场 >

路径和

[编程题]路径和

有一棵n个节点的树，每个节点都有一个价值p[i]，对于某一条路径，定义路径的价值为路径上所有点的价值在二进制下按位与的值。求所有树上路径的价值和为多少

注意，单独的一个点也算一条路径。

示例1

输入

4,[0,1,2],[1,2,3],[1,2,2,1]

共有5条路径对答案有贡献，(1->2)贡献为2，(0)贡献为1，(1)贡献为2，(2)贡献为2，(3)贡献为1，所以答案为2+1+2+2+1=8。

算法知识视频讲解

旭日东升BJFU

发表于 2020-12-18 21:06:27

王者场ABC题解反思一下:简单题没想好就急着敲，浪费时间，难的题反而做的快，因为想好了后代码是不会出问题的。所以还是要先想清楚过程确定没问题在敲代码，主要是想的时间。 A:奇怪的排序问题想清楚每次操作的过程就好做了：肯定是从高往低去处理，(因为无论你怎么动矮的，都不会让高的人往后走) 对展开全文

多动手

发表于 2020-12-19 11:09:08

牛牛的路径和思路：要求计算二进制按位与下的结果，在二进制下只有连续的1会有值，所以记录点权二进制下的0/1信息，树形dp求值，树形dp求值（好笼统呀): 即当前节点可以产生的贡献就是当前结点第i为上连续1的数量与其儿子第i为连续1的数量乘积乘对应位置的值(即1<<i) 展开全文

树

难度：

2条回答 2收藏 1599浏览

查看代码

扫一扫，把题目装进口袋