题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
类似于启发式合并思路,
先解决怎么统计方法会不重不漏
以子树为统计单位,且一定要经过根节点
因为质数只能有一个
如果当前根节点是质数,只能找子树中不是质数的路径的点(设为0)
如果不是质数,那么可以找子树中是质数的路径点(设为1)
如果当前根节点是质数,那么当前子树的节点如果是质数,那么就会多与2,且由于统计一定要经过根节点,
所以为了不超过1个质数,那么直接把当前子树的质数节点路径都全部不要就可以了
要边合并边统计
不能合并完再统计,不然就会重复算子树的路径
时间复杂度
参考文献
C++ 代码
class Solution {
public:
bool check(int n){
if(n<=3) return n>1;
if(n%6!=1&&n%6!=5) return false;
for(int i=5;i<=n/i;i+=6){
if(n%i==0||n%(i+2)==0) return false;
}
return true;
}
long long countPaths(int n, vector<vector<int>>& edges) {
long long res=0;
unordered_map<int,vector<int>> g;
for(auto e:edges){
int a=e[0],b=e[1];
g[a].push_back(b);
g[b].push_back(a);
}
map<int,int> f[n+1];
function<void(int,int)> dfs=[&](int x,int fa)
{
bool flag=false;
if(check(x)) flag=true;
if(flag) f[x][1]++;
else f[x][0]++;
for(auto y:g[x])
{
if(y==fa) continue;
dfs(y,x);
if(flag){
res+=f[y][0]*f[x][1];
f[x][1]+=f[y][0];
}
else{
res+=f[y][0]*f[x][1];
res+=f[y][1]*f[x][0];
f[x][0]+=f[y][0];
f[x][1]+=f[y][1];
}
}
};
dfs(1,-1);
return res;
}
};
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla