本文共 1107 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要找到一条边，将树分割成两部分，使得两部分的节点数的乘积最大。我们可以通过深度优先搜索（DFS）来计算每个节点的子树大小，并在每次DFS返回时计算分割后的乘积，记录最大的乘积。

方法思路

解决代码

import syssys.setrecursionlimit(1 << 25)def main():    n = int(sys.stdin.readline())    if n == 1:        print(0)        return    adj = [[] for _ in range(n + 1)]    for _ in range(n - 1):        a, b = map(int, sys.stdin.readline().split())        adj[a].append(b)        adj[b].append(a)        siz = [0] * (n + 1)    max_product = 0    def dfs(u, parent):        siz[u] = 1        for v in adj[u]:            if v == parent:                continue            siz[u] += dfs(v, u)            # 计算分割后的乘积            current = siz[v] * (n - siz[v])            if current > max_product:                max_product = current        return siz[u]        dfs(1, -1)    print(max_product)if __name__ == "__main__":    main()

代码解释

这种方法通过DFS遍历每个子树，高效地计算了每条边分割后的乘积，确保了算法的正确性和效率。

转载地址：http://uopyz.baihongyu.com/