南昌企业建站系统模板,云商城之歌,36kr是用wordpress吗,大门户wordpress主题门户新闻读题就读趋势了#xff0c;还以为是每个深度都可以选一个#xff0c;然后深度升序就可以了#xff0c;以为是个按深度的01背包。
但是前面还说了是一条路径#xff0c;路径是不能断开的。那就从每个点开始爆搜一次就好了。
看了一下范围n1e5#xff0c;n^2爆搜理论上… 读题就读趋势了还以为是每个深度都可以选一个然后深度升序就可以了以为是个按深度的01背包。
但是前面还说了是一条路径路径是不能断开的。那就从每个点开始爆搜一次就好了。
看了一下范围n1e5n^2爆搜理论上是不行的但是这道题实在是淼。正解看dfs下方。 伪AC代码dfs
#include bits/stdc.h
using namespace std;inline int read(){int x0;char cgetchar();while(c48 or c57)cgetchar();while(c48 and c57)x(x3)(x1)(c xor 48),cgetchar();return x;
}const int N1e55;
int n,s,w[N],ans;//有多少节点权值深度为s
vectorinte[N];void dfs(int now,int sum){if(sums)return;if(sums){ans;return;}for(auto i:e[now])dfs(i,sumw[i]);
}
int main(){ios::sync_with_stdio(false);nread(),sread();for(int i1;in;i)w[i]read();for(int i1,x,y;in-1;i){xread(),yread();e[x].push_back(y);}for(int i1;in;i)dfs(i,w[i]);coutansendl;return 0;
} 思路
因为是树所以每个节点仅有1个父节点存下每个节点到根节点的前缀和以倍增的形式往上跳把所有小于s的都跳了如果等于s就路径1。
每个点倍增一次复杂度nlogn此题正解 代码
无爆搜能过还要什么倍增暴论
