首页 > 代码库 > CSU 1126 DFS前缀和

CSU 1126 DFS前缀和

2024-07-14 20:06:12   221人阅读

在一棵树上找影响最小的某个点，某个点的影响是等于其他点到他的距离*其他点的权值 的和

我一开始也找不到什么好的方法，只能想到每个点暴力去判断，但是这样肯定会超时（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);}

 


联系
我们