# 树的重心

## 定义¶

（这里以及下文中的“子树”都是指无根树的子树，即包括“向上”的那棵子树，并且不包括整棵树自身。）

## 求法¶

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20``` ``````// 这份代码默认节点编号从 1 开始，即 i ∈ [1,n] int size[MAXN], // 这个节点的“大小”（所有子树上节点数 + 该节点） weight[MAXN], // 这个节点的“重量” centroid; // 用于记录树的重心（存的是节点编号） void GetCentroid(int cur, int fa) { // cur 表示当前节点 (current) size[cur] = 1; weight[cur] = 0; for (int i = head[cur]; i != -1; i = e[i].nxt) { if (e[i].to != fa) { // e[i].to 表示这条有向边所通向的节点。 GetCentroid(e[i].to, cur); size[cur] += size[e[i].to]; weight[cur] = max(weight[cur], size[e[i].to]); } } weight[cur] = max(weight[cur], n - size[cur]); if (weight[cur] <= n / 2) { // 依照树的重心的定义统计 centroid[centroid != 0] = cur; } } ``````

## 参考¶

https://blog.csdn.net/weixin_43810158/article/details/88391828

https://www.cnblogs.com/zinthos/p/3899075.html
{"ft_lang_label":"__label__zh","ft_lang_prob":0.89063746,"math_prob":0.9971204,"size":800,"snap":"2022-27-2022-33","text_gpt3_token_len":608,"char_repetition_ratio":0.03768844,"word_repetition_ratio":0.0,"special_character_ratio":0.30125,"punctuation_ratio":0.13076924,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9888614,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-06-28T08:53:30Z\",\"WARC-Record-ID\":\"<urn:uuid:b8129896-fcb3-443c-a306-648c339b8afa>\",\"Content-Length\":\"103675\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:e5241f0d-fdb0-4189-9664-d2837311144c>\",\"WARC-Concurrent-To\":\"<urn:uuid:4d29ee25-d2ce-40b7-ae59-0decad53cf06>\",\"WARC-IP-Address\":\"15.197.234.144\",\"WARC-Target-URI\":\"http://oiwiki.net/graph/tree-centroid/\",\"WARC-Payload-Digest\":\"sha1:MG7BFJE3INEX4PS4NW7WWNLVD57IRNDA\",\"WARC-Block-Digest\":\"sha1:VJJTOAZI2L23AT3VNLMJIJHKQ62ABOLB\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-27/CC-MAIN-2022-27_segments_1656103360935.27_warc_CC-MAIN-20220628081102-20220628111102-00262.warc.gz\"}"}