题目理解

我们有一棵 $n$ 个节点的树，现在要把每条边定向（变成有向边）。定向后，如果存在一条从 $u$ 到 $v$ 的有向路径，就称 $u$ 可达 $v$。

我们需要求出：

• 最小可达城市对数量：无论怎么定向，最少能有多少对 $(u,v)$ 满足 $u$ 可达 $v$（$u \neq v$）
• 最大可达城市对数量：通过精心设计边的方向，最多能有多少对 $(u,v)$ 满足 $u$ 可达 $v$

关键观察

1. 最小值分析

最小值总是 $n-1$

为什么？

• 树有 $n-1$ 条边，定向后至少能保证每个节点能到达它的"下一个"节点
• 最坏情况：把树定向成一条链，这样只有相邻节点间可达
• 因此最小值 = $n-1$

2. 最大值分析

核心思路：为了最大化可达对，我们希望构造尽可能多的"连通块"，在块内所有节点互相可达。

对于以 $r$ 为根的树，如果所有边都指向远离根的方向（或都指向根），那么：

• 从根 $r$ 可以到达所有节点
• 但其他节点间可能不可达

更好的策略：选择一个根，让它的各个子树大小尽可能均衡，这样能最大化可达对。

算法步骤详解

步骤1：寻找树的重心

void dfs(int x, int fa) {
    sz[x] = 1;
    int flg = 1;

    for (int y : h[x]) {
        if (y == fa) continue;
        dfs(y, x);
        sz[x] += sz[y];
        flg &= sz[y] <= n / 2;  // 所有子树大小都不超过n/2
    }

    if (!rt && flg && n - sz[x] <= n / 2)  // 父节点方向也不超过n/2
        rt = x;
}

重心性质：删除重心后，所有连通分量大小不超过 $n/2$

步骤2：计算基础可达对

for (int i = 1; i <= n; i++)
    ans += sz[i] - 1;

这计算的是树中固有的可达对（父子关系）

步骤3：处理子树大小分布

for (int y : h[rt])
    w[sz[y]]++;  // 记录各子树大小出现次数

for (int i = 1; i <= n; i++)
    while (w[i] > 2)
        w[i] -= 2, w[i << 1]++;

这里用了一个二进制分组技巧：

• 如果某个大小的子树出现超过2次，就把它们合并
• 这样可以用较少的物品表示所有可能的子树组合

步骤4：背包DP找最优分配

f[0] = 1;
for (int i = 1; i <= n; i++)
    while (w[i]--)
        f |= f << i;

for (int i = n >> 1; i >= 1; i--)
    if (f[i]) {
        ans += 1ll * i * (n - i - 1);
        break;
    }

背包思想：

• f[j] 表示能否选出一些子树，使它们的大小和为 $j$
• 我们找最接近 $n/2$ 的 $i$，使得 $f[i] = 1$
• 额外可达对 = $i \times (n-i-1)$

为什么这样计算？

• 如果我们能把树分成两个部分，大小分别为 $i$ 和 $n-i-1$（-1是因为根）
• 在每个部分内部，所有节点互相可达
• 额外的可达对就是两部分节点间的可达对：$i \times (n-i-1)$

举例说明

样例1：n=4

  1
 /|\
2 3 4

• 重心是1
• 子树大小：[1,1,1]
• 最优分配：无法均分，最大可达对 = 基础值3 + 额外值2 = 5
• 输出：3 5

样例2：n=8（链）

1-2-3-4-5-6-7-8

• 重心在4或5
• 子树相对均衡，能获得较多额外可达对
• 输出：7 28

复杂度分析

• 两次DFS：$O(n)$
• 背包DP：$O(n \cdot \text{物品数})$，由于二进制分组，物品数是 $O(\log n)$
• 总复杂度：$O(n \log n)$，能处理 $n=250000$

总结

这道题的关键在于：

1. 理解树定向后的可达性特征
2. 发现重心在最大化可达对中的作用
3. 使用背包DP找到最优的子树分配方案
4. 利用二进制分组优化多重背包