问题分析

我们需要在树上找到一条路径（可能带分支），使得：

• 在奇数天访问的城市不重复
• 偶数天可以在任意城市（写作日）
• 访问城市的吸引力总和最大

这实际上是一个树上最大权独立集的变种，但路径可以有分支结构。

核心算法

算法框架：动态规划 + 路径重构

使用两次动态规划：

1. 第一次：假设偶数层城市权值为0，奇数层有权值
2. 第二次：假设奇数层城市权值为0，偶数层有权值 取两次中的最大值作为答案

关键数据结构

• w[u]：处理后的城市权值（根据奇偶层设置）
• f[u]：以u为根的子树的最大权值和
• g[u]：记录达到f[u]时u下一步走向哪个儿子
• d[u]：记录父节点

算法步骤

1. 预处理：设置权值

void color(int u, int fa, int k) {
    if (k) w[u] = val[u];
    else w[u] = 0;
    // 递归处理子树
}

根据当前深度奇偶性设置城市权值。

2. 树形DP计算最大权值

void dfs(int u, int fa) {
    f[u] = w[u];
    int sum = w[u];  // u及其所有直接儿子的权值和
    
    for (auto v : p[u]) {
        if (v == fa) continue;
        sum += w[v];
        dfs(v, u);
    }
    
    // 更新f[u]和记录路径
    for (auto v : p[u]) {
        if (v == fa) continue;
        if (f[v] + sum - w[v] > f[u]) {
            f[u] = f[v] + sum - w[v];
            g[u] = v;  // 记录最优路径
        }
    }
}

3. 路径重构

void get_ans(vector<int> &c) {
    // 从from到id再到to重构完整路径
    // 处理分支情况，确保满足"不连续两天在同一城市"的条件
}

算法标签

• 树形动态规划 (Tree DP)
• 路径重构 (Path Reconstruction)
• 最大权独立集 (Maximum Weight Independent Set)
• 贪心策略 (Greedy)

复杂度分析

• 时间复杂度：$O(n)$
  • 两次DFS遍历：$O(n)$
  • 路径重构：$O(n)$
• 空间复杂度：$O(n)$
  • 存储树结构：$O(n)$
  • DP数组：$O(n)$

关键技巧

1. 奇偶层分别处理

color(1, 0, 0);  // 偶数层有权值
dfs(1, 0);
color(1, 0, 1);  // 奇数层有权值  
dfs(1, 0);

通过两次计算确保找到全局最优解。

2. 路径记录机制

使用g[u]数组记录每个节点的最优后继，便于后续路径重构。

3. 分支处理

在get_ans函数中巧妙处理路径分支，通过在路径中插入"往返"移动来满足约束条件：

if (!w[pos]) 
    for (auto v : p[pos])
        if (v != d[pos] && v != g[pos]) {
            c.push_back(v);
            c.push_back(pos);  // 往返移动
        }

样例验证

对于样例1：

城市权值: [3,8,5,4,1,2,1,1]
最优路径: 3→2→1→2→4→6→7
访问城市: 3,1,4,7 (第1,3,5,7天)
权值和: 5+3+4+1=13

该路径满足：

• 奇数天访问不同城市
• 偶数天通过移动到达下一个访问城市
• 总权值最大

正确性证明

1. 完备性：通过两次DP（奇偶层分别作为访问层）确保找到所有可能的访问模式。

2. 最优性：DP状态f[u]正确计算了以u为根的子树的最大权值，通过路径重构得到具体方案。

3. 可行性：重构的路径满足"不连续两天在同一城市"的约束，通过插入往返移动处理分支情况。

这种解法巧妙地利用了树的结构性质和动态规划，在线性时间内解决了这个复杂的路径规划问题。