首页 > 代码库 > 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);}