现在有一棵树,每条边的长度为 ,定义 为结点 之间的距离,定义结点 的权值为 ,现在求 到 所有点的权值。
返回 个整数,分别为
5,[(2,5),(5,3),(5,4),(5,1)]
[7,7,7,7,4]
第一个参数为整数 。
第二个参数为大小为 n-1n−1 的点对 (u_i, v_i)(ui,vi) 的集合 EdgeEdge ,其中 (u_i, v_i)(ui,vi) 表示结点 u_iui 与结点 v_ivi 之间有一条边,1leq u_i, v_i leq n1≤ui,vi≤n
/** * struct Point { * int x; * int y; * }; */ class Solution { public: /** * * @param n int整型 点的数量 * @param edge Point类vector Point.x , Point.y 边所连接的两个点 * @return long长整型vector */ vector<int> G[100001]; vector<int> s; vector<long> r; int DFS1(int u, int p, int d){ int cnt=1; for(auto &v: G[u]) if(v != p) cnt += DFS1(v, u, d+1); r[0] += d; s[u] = cnt; return cnt; } void DFS2(int u, int p, int n){ for(auto &v: G[u]){ if(p != v){ r[v] = r[u] + n - 2*s[v]; DFS2(v, u, n); } } } vector<long> solve(int n, vector<Point>& edge) { s.resize(n); r.resize(n); for(auto &e: edge){ G[e.x-1].push_back(e.y-1); G[e.y-1].push_back(e.x-1); } DFS1(0, -1, 0); DFS2(0, -1, n); return r; } };
void depth_first_search_algorithm(int* g, const int n, int cur, int prev, long* total, int step) { int v; *total += step; for (v = 1; v <= n; ++v) if (*(g + cur * (n + 1) + v) == 1 && v != prev) depth_first_search_algorithm(g, n, v, cur, total, step + 1); } long* solve(int n, struct Point* edge, int edgeLen, int* returnSize) { long* ans = (long*) malloc(n * sizeof(long)); if (!ans) { *returnSize = 0; return NULL; } int g[n + 1][n + 1]; // 图的邻接矩阵表示法 memset(g, 0x0000, sizeof g); int i, u, v; for (i = 0; i < edgeLen; ++i) { u = edge[i].x, v = edge[i].y; g[u][v] = 1; g[v][u] = 1; } for (u = 1; u <= n; ++u) { long total = 0; depth_first_search_algorithm((int*) g, n, u, -1, &total, 0); *(ans - 1 + u) = total; } *returnSize = n; return ans; }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 点的数量 * @param edge Point类vector Point.x , Point.y 边所连接的两个点 * @return long长整型vector */ vector<long> solve(int n, vector<Point>& edge) { vector<long> ans(n); vector<vector<int>> g(n + 1); for (const auto& e : edge) { g[e.x].emplace_back(e.y); g[e.y].emplace_back(e.x); } for (int i = 1; i <= n; ++i) ans[i - 1] = bfs(g, n, i); return ans; } private: int bfs(vector<vector<int>>& g, int n, int start) { deque<int> q{{start}}; vector<int> seen(n + 1); seen[start] = 1; long total = 0; int steps = 0; while (not q.empty()) { size_t s = q.size(); while (s--) { const int cur = q.front(); q.pop_front(); total += steps; for (const int nxt : g[cur]) { if (seen[nxt]++) continue; q.emplace_back(nxt); } } ++steps; } return total; } };
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 点的数量 * @param edge Point类一维数组 Point.x , Point.y 边所连接的两个点 * @return long长整型一维数组 */ long count; // 记录某个点到其他点的距离 // bfs 做法 public long[] solve (int n, Point[] edge) { // write code here int[][] path = new int[n][n]; for (Point e : edge) { path[e.x - 1][e.y - 1] = 1; path[e.y - 1][e.x - 1] = 1; } long[] result = new long[n]; for (int i = 0; i < n; i++) { boolean[] visited = new boolean[n]; visited[i] = true; count = 0; bfs(i, visited, path, 1); result[i] = count; } return result; } private void bfs(int node, boolean[] visited, int[][] path, int step) { ArrayList<Integer> nextNodes = new ArrayList<>(); for (int i = 0; i < path[node].length; i++) { if (path[node][i] == 1 && !visited[i]) { nextNodes.add(i); visited[i] = true; count += step; } } for (int nextNode : nextNodes) { bfs(nextNode, visited, path, step + 1); // 随着递归的推进,距离越来越远,每次加一 } } }