首先一看题 死死的认为树不就是图吗，最短路算法套上去不就得了吗 然后写了一个spfa和djstla
int spfa(int x,int N){//SPAF queue<int> q; for(int i=0;i<N;++i){ dis[i]=inf; vis[i]=0; } q.push(x); vis[x]=1;dis[x]=0; while(!q.empty()){ int u = q.front();q.pop();vis[u]=0; for(int i =e[u].first;i!=0;i=e[i].next){ int v=e[i].v,w=e[i].w; if(dis[v]>dis[u]+w){ dis[v]=dis[u]+w; if(!vis[v]){ q.push(v); vis[v]=1; } } } } int tem_ans=0; for(int nums:dis){ tem_ans+=nums; } return tem_ans; } ///Djstla// template <class Compare> int Djstl(int x,int N, Compare comp) { priority_queue<int, vector<int>, Compare> q(comp); for(int i=0;i<N;++i){ dis[i]=inf; vis[i]=0; } dis[x]=0; q.push(x); while(!q.empty()) { int u=q.top();q.pop(); if(!vis[u]) { vis[u]=1; for(int i=e[u].first;i;i=e[i].next) { int v=e[i].v,w=e[i].w; dis[v]=min(dis[v],dis[u]+w); q.push(v); } } } int tem_ans=0; for(int i=0;i<N;++i) tem_ans+=dis[i]; return tem_ans; }全部死在了第64个点… 题解来自于leetcode 题目 一看题解又是要命的dp，还是树形dp，打比赛遇到我绝对甩给我队友
dp为初始 通过dfs解决 换根优化时间复杂度
class Solution { int[] ans; int[] sz; int[] dp; List<List<Integer>> graph; public int[] sumOfDistancesInTree(int N, int[][] edges) { ans = new int[N]; sz = new int[N]; dp = new int[N]; graph = new ArrayList<List<Integer>>(); for (int i = 0; i < N; ++i) { graph.add(new ArrayList<Integer>()); } for (int[] edge: edges) { int u = edge[0], v = edge[1]; graph.get(u).add(v); graph.get(v).add(u); } dfs(0, -1); dfs2(0, -1); return ans; } //对根节点0 执行树状dp //u：当前节点，f：当前节点的“根”节点 public void dfs(int u, int f) { sz[u] = 1; dp[u] = 0; for (int v: graph.get(u)) { // 邻接点不允许为u的根节点 if (v == f) { continue; } dfs(v, u); dp[u] += dp[v] + sz[v]; sz[u] += sz[v]; } } //执行换根操作 public void dfs2(int u, int f) { // 记录节点u的结果 ans[u] = dp[u]; // 对u的相邻边进行换根 for (int v: graph.get(u)) { // 邻接点不允许为u的根节点 if (v == f) { continue; } // 暂时储存 等待u换为v之后再还原 // 因为u有很多v要换 这些值需要重复使用 int pu = dp[u], pv = dp[v]; int su = sz[u], sv = sz[v]; //换根递推式 dp[u] -= dp[v] + sz[v]; sz[u] -= sz[v]; dp[v] += dp[u] + sz[u]; sz[v] += sz[u]; // 记录v的值 并且对v的邻边进行换根 dfs2(v, u); // 还原 dp[u] = pu; dp[v] = pv; sz[u] = su; sz[v] = sv; } } }