同事裁员被赔了 30w，结果他当场大哭!一问才知道，他在深圳每月要还30000房贷，还有孩子补习班每月15000，中年人太难了

那天晚上快下班了，我正准备关电脑点外卖，群里突然有人丢一句：“东哥，那个均匀树划分你会写不？在线等，挺急。” 我脑子里第一反应是：又是树，又要“均匀”，这听着就不像能早点下班的题。

你们先把题目脑补一下啊，大概意思就是：有一棵树，每个节点有个权值，让你把树的某些边砍掉，砍成几块小树，每一块小树的权值和都一样，问最多能砍成多少块。就特别像公司年会分水果，HR 拿一大箱苹果，说每桌必须一样重，你负责切，切坏了还得重来那种感觉。

我当时下意识想法特朴素：既然要均匀，那我就算个平均值嘛，对吧，总和 / n 之类的。后来一想不对，节点权值乱七八糟，你根本不知道能分几块，只能先算出整棵树的总和 sum，然后去猜：这棵树是不是能被分成「若干块，每块和 = 某个因子 d」。这个味道就来了，有点算发题那味儿了。

说实话，这感觉跟我当年拿 Postgres 和 MySQL 压测一样，看着都差不多，真跑起来差别大的离谱。直觉这东西真的不能信。

你看我们先干几件死板但必须干的事儿：

1. 把树存成邻接表，别每次都 for 全数组瞎找父子。
2. 算一遍所有节点权值的总和 total。
3. 把 total 的所有因子找出来，倒着试——因为我们想要块数尽量多，相当于每块的 sum 越小越好，但试的时候从「每块 sum 大」往下试更稳，先找到一个能成的就收工。

随手写个找因子的代码，你们感受下语音转文字现场感，变量名就那回事儿，能看懂就行：

private List<Integer> getDivisors(int sum){
    List<Integer> res = new ArrayList<>();
for (int x = 1; x * x <= sum; x++) {
if (sum % x == 0) {
            res.add(x);          // 每块和 = x
if (x * x != sum) {
                res.add(sum / x); // 对应的另外一个因子
            }
        }
    }
// 为了方便“从大到小试”
    res.sort((a, b) -> b - a);
return res;
}

有人肯定要问：为啥要试因子？你想啊，如果最后能切成 k 块，那每块和 = total / k，这玩意儿一定是 total 的一个因子，不是因子你拿啥均匀，分瓜呢。

重点来了，DFS 怎么写。核心思路其实特别生活化：你从叶子往上加权值，加着加着一看，哎，这一坨刚好等于 target，那这坨就可以当一块完整小树了，直接把这一坨“打包寄走”，返回 0 给上面。要是超过 target，那就直接宣告：这个 target 不行。

我当时写 DFS 的时候，就跟在排查 SpringBoot 默认配置那些坑一样，凡是“默认”就先不要信，凡是“以为不会出事”就一定要多打几个日志。所以 DFS 里我一般都留个 debug sum，看一眼有没有比 target 大。

上点核心代码，精简版的，真实比赛肯定外面再包一层 main 啥的，这里就只放算发核心了：

classTreePartition{
    List<Integer>[] g;
int[] w;
int n;
int target;
int cnt;

publicintsolve(int n, int[] weight, int[][] edges){
this.n = n;
this.w = weight;
        g = new ArrayList[n];
for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
for (int[] e : edges) {
int u = e[0], v = e[1];
            g[u].add(v);
            g[v].add(u);
        }

int sum = 0;
for (int x : w) sum += x;
        List<Integer> ds = getDivisors(sum);

for (int d : ds) {
            target = d;
            cnt = 0;
if (dfs(0, -1) == 0 && cnt == sum / d) {
// 能切成 cnt 块，每块和 = d
return cnt;
            }
        }
return1; // 最惨情况，谁也切不了，就整棵树一块
    }

privateintdfs(int u, int fa){
int cur = w[u];
for (int v : g[u]) {
if (v == fa) continue;
            cur += dfs(v, u);
        }
if (cur == target) {
            cnt++;
return0; // 打包寄走
        }
if (cur > target) {
// 这里其实可以直接抛个异常或者标记失败
// 为了省事，返回一个不可能被“合并”掉的大值
return Integer.MAX_VALUE / 2;
        }
return cur;
    }

// getDivisors 同上，就不重复贴了
}

这段代码有几个小细节，顺便吐槽一下我自己踩过的坑：

• 我早期把 dfs(0, -1) 写成从 1 开始，结果一通 NPE，半天才想起来节点编号是 0 开始的，那一瞬间真的比生产环境 TCP 包卡在 1024 字节还想砸电脑。
• cur > target 这块，如果你不做处理，继续往上加，最后会发现根的 sum 远远大于 target，然后你还在那儿数 cnt，感觉自己好像切成功了一样，其实全错。
• cnt == sum / d 这个校验别偷懒不写，有时候 DFS 里虽然凑齐了好几块 target，但是还有一坨残渣在根上，这种其实是失败案例。

你会发现，这题跟写业务很像： 你不知道最后要拆成多少个微服务（多少块子树），但你知道整套系统的总复杂度（total），只能先猜“每个服务大概多重”（target），然后自底向上看哪里可以切开。切得好的架构叫“均匀树划分”，切坏了的那个，叫“线上事故复盘”。