首页 > 代码库 > CSU 1126 DFS前缀和
CSU 1126 DFS前缀和
在一棵树上找影响最小的某个点,某个点的影响是等于其他点到他的距离*其他点的权值 的和
我一开始也找不到什么好的方法,只能想到每个点暴力去判断,但是这样肯定会超时(10^5个点),又有点想用类似前缀和,但是这是在树上,不是很好搞
不过最后还是得用到前缀和,先dfs1把从0号节点出发的整个值算出来,并且沿途记录权值前缀和。之后再用一个dfs2从0号节点开始转移,因为有之前预处理的前缀和以及总和,每次转移只要O(1)复杂度就可以算出来。整个两次dfs都仅仅对每个点搜索了一遍,不会超时
代码不是我写的 用来参考
#include <iostream>#include <vector>using namespace std; int N;long long cost[1<<17], cows[1<<17], down[1<<17], up[1<<17];vector<vector<long long> > e, w; long long dfs1(int cur, int prev) { down[cur] = cows[cur]; long long c = 0; for(int i = 0; i < e[cur].size(); i++) { if(e[cur][i] == prev) continue; c += dfs1(e[cur][i], cur); c += down[e[cur][i]]*w[cur][i]; down[cur] += down[e[cur][i]]; } return c;} long long dfs2(int cur, int prev) { long long c = cost[cur]; for(int i = 0; i < e[cur].size(); i++) { if(e[cur][i] == prev) continue; cost[e[cur][i]] = cost[cur]-down[e[cur][i]]*w[cur][i]+up[e[cur][i]]*w[cur][i]; c = min(c, dfs2(e[cur][i], cur)); } return c;} int main() { //FILE* in = fopen("red.in", "r"); //FILE* out = fopen("red.out", "w"); scanf("%d", &N); e.resize(N); w.resize(N); for(int i = 0; i < N; i++) scanf("%lld", &cows[i]); for(int i = 0; i < N-1; i++) { long long a, b, c; scanf("%lld %lld %lld", &a, &b, &c); a--; b--; e[a].push_back(b); w[a].push_back(c); e[b].push_back(a); w[b].push_back(c); } cost[0] = dfs1(0, -1); for(int i = 0; i < N; i++) up[i] = down[0] - down[i]; printf("%lld\n", dfs2(0, -1)); //fclose(in); //fclose(out);}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。