\u539f\u9898\u94fe\u63a5<\/a><\/p>\n\u8fd9\u6bb5c++\u7684\u4ee3\u7801\u5199\u7684\u5f88\u4f18\u96c5\uff1a<\/p>\n
#include "bits\/stdc++.h"\nusing namespace std;\n#define For(i, j, n) for(int i=j;i<=n;i++)\n#define Fol(i, j, n) for(int i=j;i>=n;i--)\ntypedef long long LL;\nconst int N = 2e3 + 5;\nstruct node {\n int w;\/\/\u81ea\u8eab\u6743\u91cd\n LL wt;\/\/\u81ea\u5df1\u4e0e\u540e\u4ee3\u7684\u6743\u91cd\n unordered_set<int> son;\/\/\u5b69\u5b50\u4eec\n} tr[N];\nbool st[N];\/\/\u5224\u65ad\u8fd9\u4e2a\u7c7b\u522b\u662f\u5426\u88ab\u53bb\u9664\nset<int> seg;\/\/\u5f85\u67e5\u8be2\u7684\u7c7b\u522b\u96c6\u548c\n\n\/\/\u66f4\u65b0\u4ee5root\u4e3a\u6839\u7684\u6811\u4e0a\u6240\u6709\u8282\u70b9\u7684wt\nLL dfs(int root, set<int> &seg) {\n seg.insert(root);\n LL res = 0;\n for (auto child: tr[root].son) {\n if (st[child]) continue;\n res += dfs(child, seg);\n }\n tr[root].wt = res + tr[root].w;\n return tr[root].wt;\n}\n\/\/\u67e5\u8be2wsigma\u6700\u5c0f\u7684\u8282\u70b9\nint query(int root, set<int> &seg) {\n LL wmin = LONG_LONG_MAX, pos = -1;\n for (auto x: seg) {\n LL wsigma = abs(tr[root].wt - 2 * tr[x].wt);\n if (wmin > wsigma) {\n wmin = wsigma;\n pos = x;\n }\n }\n return pos;\n}\n\/\/\u7528\u6237\u8be2\u95ee\u5224\u65adch\u662f\u5426\u88ab\u5f52\u7c7bfa\u6216\u8005fa\u7684\u540e\u4ee3\nbool judge(int fa, int ch) {\n if (fa == ch) return true;\n bool flag = false;\n for (auto x: tr[fa].son) {\n flag |= judge(x, ch);\n if(flag) break;\n }\n return flag;\n}\nint main() {\n int n, m, fa;\n scanf("%d %d", &n, &m);\n For(i, 1, n) scanf("%d", &tr[i].w);\n For(i, 2, n) {\n scanf("%d", &fa);\n tr[fa].son.insert(i);\n }\n For(i, 1, m) {\n memset(st, false, sizeof st);\n int root = 1, x;\n scanf("%d", &x);\n while (1) {\n seg.clear();\n dfs(root, seg);\n if (seg.size() == 1)break;\/\/\u76f4\u5230\u53ea\u5269\u4e0b\u4e00\u4e2a\u7c7b\u522b\uff0c\u6b64\u65f6\u5373\u53ef\u786e\u5b9a\u540d\u8bcd\u7684\u7c7b\u522b\n int id = query(root, seg);\n printf("%d ", id);\n if (judge(id, x)) root = id;\/\/\u5982\u679c\u7528\u6237\u56de\u7b54\u662f\uff0c\u4fdd\u7559\u8be5\u7c7b\u522b\u53ca\u5176\u540e\u4ee3\u7c7b\u522b\n else st[id] = true;\/\/\u5426\u5219\u4ec5\u4fdd\u7559\u5176\u4f59\u7c7b\u522b\n }\n puts("");\n }\n return 0;\n}<\/code><\/pre>\n\u53e6\u5916\u8d34\u4e00\u4e2aJava\u7684\uff1a<\/p>\n
\u4e5f\u5199\u7684\u4e0d\u9519\uff0c\u4e0d\u8fc7\u6709\u5c11\u91cf\u4f18\u5316\u7a7a\u95f4\uff1a<\/p>\n
import java.util.ArrayList;\nimport java.util.List;\nimport java.util.Scanner;\n\npublic class Main {\n public static void main(String[] args) {\n Scanner sc = new Scanner(System.in);\n int n = sc.nextInt(), m = sc.nextInt();\n int[] weigth = new int[n + 1];\n int[] father = new int[n + 1]; \/\/ \u5b58\u50a8\u5f53\u524d\u8282\u70b9\u7684father\u662f\u8c01\n List<Integer>[] son = new List[n + 1]; \/\/\u5b58\u50a8\u5f53\u524d\u8282\u70b9\u7684\u513f\u5b50\u8282\u70b9\u6709\u4ec0\u4e48\n for (int i = 1; i <= n; i++) {\n weigth[i] = sc.nextInt();\n son[i] = new ArrayList<>();\n }\n for (int i = 2; i <= n; i++) {\n father[i] = sc.nextInt();\n son[father[i]].add(i);\n }\n for (int i = 0; i < m; i++) {\n int j = sc.nextInt();\n int head = 1;\n ArrayList<Integer> removed = new ArrayList<>();\n do{\n long[] currentWeight = new long[n + 1];\n getWeight(weigth, son, removed, head, currentWeight);\n long[] w = new long[n + 1]; \/\/\u5b58\u50a8\u6700\u7ec8\u7684\u6743\u91cd\u503c\uff0c\u4e5f\u5c31\u662f\u9898\u76ee\u8981\u6c42\u7684\u6743\u91cd\n long minValue = Long.MAX_VALUE;\n int minIndex = 0;\n for (int k = 1; k <= n; k++) {\n if (removed.contains(k))continue;\n w[k] = Math.abs(2 * currentWeight[k] - currentWeight[head]);\/\/ \u6839\u636e\u9898\u76ee\u8981\u6c42\u5f97\u51fa\u7684\u6700\u7ec8\u6743\u91cd\u516c\u5f0f\n if (minValue > w[k]){\n minValue = w[k];\n minIndex = k;\n }\n }\n if (isSon(father, minIndex, j, head)){\n head = minIndex;\n }else {\n removed.add(minIndex);\n }\n System.out.print(minIndex + " ");\n }while (hasTwo(son, removed, head));\n System.out.println(" ");\n }\n }\n\n \/\/\u83b7\u53d6\u6240\u6709\u8282\u70b9\u7684\u6743\u91cd\u503c\uff0c\u6b64\u6743\u91cd\u4e3a \u5b83\u548c\u5176\u5168\u90e8\u540e\u4ee3\u7c7b\u522b\u7684\u6743\u91cd\u4e4b\u548c\uff0c \u7528res\u627f\u63a5\u7b54\u6848\n public static long getWeight(int[] weight, List<Integer>[] son, List<Integer> removed, int root, long[] res){\n if (removed.contains(root))return 0;\n long ans = weight[root];\n for (Integer temp : son[root]) {\n ans += getWeight(weight, son, removed, temp, res);\n }\n res[root] = ans;\n return ans;\n }\n\n \/\/\u5224\u65adj\u8282\u70b9\u662f\u5426\u662fmin\u8282\u70b9\u7684\u5b69\u5b50\n public static boolean isSon(int[] father, int min ,int j, int head){\n if (min == head)return true;\n while (j != head){\n if (j == min)return true;\n j = father[j];\n }\n return false;\n }\n\n \/\/\u5224\u65ad\u5f53\u524d\u6811\u7ed3\u6784\u662f\u5426\u6709\u4e24\u4e2a\u53ca\u4ee5\u4e0a\u8282\u70b9\u5b58\u5728\n public static boolean hasTwo(List<Integer>[] son, List<Integer> removed,int head){\n for (Integer temp : son[head]) {\n if (!removed.contains(temp))return true;\n }\n return false;\n }\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"ccf\u6811\u4e0a\u641c\u7d22 \u539f\u9898\u94fe\u63a5 \u8fd9\u6bb5c++\u7684\u4ee3\u7801\u5199\u7684\u5f88\u4f18\u96c5\uff1a #include "bits\/stdc++.h" us …<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[11,5,9],"class_list":["post-263","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-c","tag-java","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts\/263","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/comments?post=263"}],"version-history":[{"count":1,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts\/263\/revisions"}],"predecessor-version":[{"id":264,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts\/263\/revisions\/264"}],"wp:attachment":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/media?parent=263"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/categories?post=263"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/tags?post=263"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}