个人如何免费建网站,网站会员系统怎么做模版,做网站表示时间的控件用哪个,中学网站建设工作实施方案原题链接#xff1a;2867. 统计树中的合法路径数目
题目描述#xff1a;
给你一棵 n 个节点的无向树#xff0c;节点编号为 1 到 n 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges #xff0c;其中 edges[i] [ui, vi] 表示节点 ui 和 vi 在树中有一条边。
…原题链接2867. 统计树中的合法路径数目
题目描述
给你一棵 n 个节点的无向树节点编号为 1 到 n 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges 其中 edges[i] [ui, vi] 表示节点 ui 和 vi 在树中有一条边。
请你返回树中的 合法路径数目 。
如果在节点 a 到节点 b 之间 恰好有一个 节点的编号是质数那么我们称路径 (a, b) 是 合法的 。
注意
路径 (a, b) 指的是一条从节点 a 开始到节点 b 结束的一个节点序列序列中的节点 互不相同 且相邻节点之间在树上有一条边。路径 (a, b) 和路径 (b, a) 视为 同一条 路径且只计入答案 一次 。
输入输出描述
示例 1 输入n 5, edges [[1,2],[1,3],[2,4],[2,5]]
输出4
解释恰好有一个质数编号的节点路径有
- (1, 2) 因为路径 1 到 2 只包含一个质数 2 。
- (1, 3) 因为路径 1 到 3 只包含一个质数 3 。
- (1, 4) 因为路径 1 到 4 只包含一个质数 2 。
- (2, 4) 因为路径 2 到 4 只包含一个质数 2 。
只有 4 条合法路径。示例 2 输入n 6, edges [[1,2],[1,3],[2,4],[3,5],[3,6]]
输出6
解释恰好有一个质数编号的节点路径有
- (1, 2) 因为路径 1 到 2 只包含一个质数 2 。
- (1, 3) 因为路径 1 到 3 只包含一个质数 3 。
- (1, 4) 因为路径 1 到 4 只包含一个质数 2 。
- (1, 6) 因为路径 1 到 6 只包含一个质数 3 。
- (2, 4) 因为路径 2 到 4 只包含一个质数 2 。
- (3, 6) 因为路径 3 到 6 只包含一个质数 3 。
只有 6 条合法路径。提示
1 n 105edges.length n - 1edges[i].length 21 ui, vi n输入保证 edges 形成一棵合法的树。
解题思路 首先数据量有1e5那么我们可以先预处理线性筛筛出所有质数便于后续处理题目说了合法路径指的是路径上包含刚好一个质数点那么我们dfs的同时枚举每一个质数点考虑每一个质数点的贡献下面画个图描述一下 由于我们需要记录某个点出发在不经过质数点的情况最多经过多少个点我们可以用sz[x]记录从x出发在不经过质数点的情况下最多会经过几个点类似记忆化的思想所以枚举每一个质数贡献的时候如果遇到某个点的sz[y]已经被计算过了直接拿来用即可避免重复搜索。 时间复杂度不考虑预处理线性筛的时间由于采取了记忆化思想每个点只会访问一次所以时间复杂度为O(n)。 空间复杂度O(n)。 cpp代码如下
const int N1e510;
typedef long long LL;
int primes[N],cnt0;
bool st[N];
int init[](){ //线性筛预处理所有质数st[1]true;for(int i2;iN;i){if(!st[i])primes[cnt]i;for(int j0;primes[j](N-1)/i;j){st[primes[j]*i]true;if(i%primes[j]0)break;}}return 0;
}();
class Solution {
public:long long countPaths(int n, vectorvectorint edges) {vectorvectorintg(n1);vectorintsz(n1);for(auto t:edges){int xt[0],yt[1];g[x].push_back(y);g[y].push_back(x);}vectorintnodes;//dfs遍历在不经过指数的情况下最多经过多少个点也就是非质数连通块大小functionvoid(int,int)dfs[](int x,int fa){ nodes.push_back(x);for(auto y:g[x]){if(y!fa st[y]){dfs(y,x);}}};LL ans0;for(int x1;xn;x){if(st[x])continue; //只需要枚举质数非质数跳过int sum0;for(int y:g[x]){if(!st[y])continue; //y是质数不需要在搜索if(sz[y]0) //没有被搜索过搜索一下{nodes.clear();dfs(y,-1);for(int x:nodes){ //对于这个连通块中所有点都要标记一下连通块大小避免重复计算sz[x]nodes.size();}}ans(LL)sz[y]*sum; //计算贡献sumsz[y]; //sum记录左边的子树大小之和}anssum; //这个也是贡献的一部分}return ans;}
};
