#4738. 「KTSC 2019 R1」树 题解

题目理解

给定一棵树，每个节点有整数权值（可为负）。需要选择两个不相交的连通子图 $T_a$ 和 $T_b$，使得它们的节点权值之和 $sum(T_a) + sum(T_b)$ 最大。

约束条件：

1. 两个子图都非空且连通
2. 子图之间没有边连接（即删除某些边后两个子图分离）

核心算法

算法标签：树形动态规划 换根DP 最大连通子图和 次大值维护

1. 问题转化

观察：最优解中 $T_a$ 和 $T_b$ 实际上是树删除某条边后形成的两个连通分量中的最大权连通块。

因此问题转化为：枚举树中的边，删除后得到两棵树，在两棵树中分别找最大权连通块，求和取最大值。

2. 算法框架

第一次DFS：计算子树信息

void dfs1(const int &u, const int &fa, const vector<int> &C) {
    sonsm[u] = C[u];        // 包含u的连通块最大和（可包含多个子树）
    dp[u] = LLONG_MIN;      // 以u为根的子树中的最大连通块和
    
    for (const int &v : g[u]) {
        if (v == fa) continue;
        dfs1(v, u, C);
        dp[u] = max(dp[u], dp[v]);  // 继承子树的最大值
        
        if (sonsm[v] > 0LL)
            sonsm[u] += sonsm[v];   // 贪心：正贡献才合并
    }
    dp[u] = max(dp[u], sonsm[u]);   // 可能u自身的连通块更大
}

关键变量：

• sonsm[u]：包含节点u的连通块的最大权值和（类似最大子段和思想）
• dp[u]：以u为根的子树中的最大连通块权值（可能不包含u）

第二次DFS：换根计算

void dfs2(const int &u, const int &fa) {
    // 找u的子树中dp值的最大值和次大值
    long long mx = LLONG_MIN, se = LLONG_MIN;
    for (const int &v : g[u])
        se = (dp[v] > mx ? exchange(mx, dp[v]) : max(se, dp[v]));
    
    // 用最大和次大更新答案（对应删除u与某个子节点之间的边）
    if (se != LLONG_MIN)
        ans = max(ans, mx + se);
    
    // 保存当前状态，用于恢复
    long long dpu = dp[u], tmpsmu;
    
    // 换根：尝试将u作为v的子树
    for (const int &v : g[u]) {
        if (v == fa) continue;
        
        // 临时移除v对u的影响
        dp[u] = dpu, tmpsmu = sonsm[u];
        if (sonsm[v] > 0) tmpsmu -= sonsm[v];
        
        // 更新u的dp值（去掉v子树后的最大值）
        if (dp[v] == mx)
            dp[u] = max(se, tmpsmu);
        else
            dp[u] = max(mx, tmpsmu);
        
        // 更新v的信息（加入u所在分支）
        if (tmpsmu > 0)
            dp[v] = max(dp[v], sonsm[v] += tmpsmu);
        
        dp[v] = max(dp[v], dp[u]);
        dfs2(v, u);  // 递归处理
    }
}

算法正确性分析

为什么这样能找到最优解？

1. 枚举所有可能的分割：通过换根DP，实际上枚举了删除每条边的情况
2. 最大连通块计算：dp[u] 保证存储子树中的最大连通块权值
3. 次大值技巧：维护最大值和次大值，可以快速找到删除某边后两边的最大连通块

关键技巧

• 贪心合并：只有正权值的子树才被合并到 sonsm[u] 中
• 状态保存与恢复：在换根时临时修改父节点信息，递归后恢复
• 次大值维护：用 exchange 技巧高效维护最大和次大值

复杂度分析

• 时间复杂度：$O(N)$，两次DFS遍历
• 空间复杂度：$O(N)$，存储树结构和DP数组

算法标签总结

主要标签

• 树形DP - 核心算法框架
• 换根DP - 关键技术
• 最大连通子图和 - 问题本质

技术标签

• 次大值维护 - 优化技巧
• 状态转移 - DP设计
• 贪心选择 - 正权值才合并

树论标签

• 子树处理 - 自底向上计算
• 父节点更新 - 自顶向下传播
• 边枚举 - 通过DFS隐式枚举

优化标签

• $O(N)$算法 - 线性复杂度
• 记忆化 - DP避免重复计算
• 交换技巧 - 高效维护极值

样例验证

对于样例：

节点权值: [3, -5, -1, 4, 2, 5, 3]
边: (0,1),(0,2),(2,3),(2,4),(4,6),(5,6)

算法过程：

1. 第一次DFS计算每个子树的最大连通块
2. 第二次DFS枚举删除每条边的情况
3. 找到删除边(4,6)时，两边最大连通块为{0,2,3}和{5,6}，和为14

这个解法通过巧妙的树形DP设计和换根技术，高效解决了树上的最大双连通块和问题。