题解

问题分析

题目要求找到最短的灯泡序列，使得所有灯泡最终都亮着。序列中相邻灯泡必须直接相连，每次到达灯泡时会按一次开关（切换状态）。核心挑战是：在树形结构中，通过路径遍历切换灯泡状态，确保所有灯泡从初始状态（0或1）变为1，且路径长度最短。

核心思路

灯泡的状态切换次数需满足：初始为0的灯泡需被按奇数次，初始为1的灯泡需被按偶数次（包括0次）。由于灯泡构成树，可通过树形动态规划（DP） 处理每个节点及其子树，定义状态记录“处理完子树后节点的状态”和“当前所在位置”，从而计算最短路径。

此外，若某子树的所有灯泡初始均为1（无需处理），可直接忽略该子树，减少计算量。

状态定义与转移

通过三个二维数组 f[2][u]、g[2][u]、h[2][u] 记录状态，其中 s ∈ {0,1} 表示节点 u 的当前状态（0为灭，1为亮），u 为当前节点：

• f[s][u]：处理完 u 的所有子树后，u 的状态为 s，且当前位置在 u 时的最短序列长度。
• g[s][u]：处理完 u 的所有子树后，u 的状态为 s，且当前位置在 u 的某个子节点时的最短序列长度。
• h[s][u]：处理完 u 的所有子树后，u 的状态为 s，且当前位置可在 u 或其任意子节点时的最短序列长度（即 f 和 g 的最小值）。

预处理：忽略全亮子树

通过第一次DFS（dfs函数）标记 chk[u]：若以 u 为根的子树中所有灯泡初始均为1，则 chk[u] = 1（无需处理），后续DP可跳过该子树。

树形DP转移（dfs1函数）

1. 初始化：对于节点 u，初始状态为 l[u]（0或1），故 f[l[u]][u] = 0（未处理子树时，长度为0）。

2. 子树合并：对于每个非全亮子树的子节点 v，将 v 的状态转移到 u：

   • f 的转移：考虑从 u 到 v 往返（路径长度+2），结合 v 的状态更新 u 的状态。
   • g 的转移：考虑处理完 v 后停留在 v（无需返回 u），路径长度可能减少1。
   • h 的转移：综合 f、g 及子节点的 h 状态，取最小值。

3. 最终状态：h[1][rt] 即为答案，其中 rt 是初始为0的节点（确保至少处理一个节点），表示处理完所有子树后，根节点状态为1（亮）的最短序列长度。

代码实现解析

1. 输入与初始化：读入灯泡数量、初始状态及树的边，构建邻接表。
2. 预处理全亮子树：通过 dfs 标记 chk 数组，忽略无需处理的子树。
3. 树形DP：通过 dfs1 计算 f、g、h 数组，转移时考虑子树的状态合并。
4. 输出结果：h[1][rt] 即为最短序列长度。

复杂度分析

• 时间复杂度：O(n)。两次DFS均遍历所有节点一次，每个节点的转移操作是常数级（遍历邻接表，总边数为 O(n)）。
• 空间复杂度：O(n)。存储邻接表、状态数组及标记数组，均为线性空间。

示例说明

以样例1为例：

• 灯泡初始状态为 010（节点1：0，节点2：1，节点3：0），树结构为 1-2-3。
• 需处理节点1和3（初始为0），节点2初始为1（需偶数次按动）。
• 最优路径 1→2→3→2：按动1（变亮）、按动2（变暗）、按动3（变亮）、按动2（变亮），总长度4，符合 h[1][rt] 的计算结果。

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline void read(int &u) {
    u = 0;
    int v = 1;
    char ch = getchar();

    while (ch < '0' || ch > '9') {
        if (ch == '-')
            v = -1;

        ch = getchar();
    }

    while (ch >= '0' && ch <= '9') {
        u = u * 10 + ch - '0';
        ch = getchar();
    }

    u = u * v;
}
const int N = 500010;
int n, l[N], chk[N], f[2][N], g[2][N], h[2][N];
struct node {
    int to, nxt;
} e[N << 1];
int cnt, head[N];
inline void add(int u, int v) {
    e[++cnt].nxt = head[u];
    e[cnt].to = v;
    head[u] = cnt;
}
char s[N];
void dfs(int u, int fa) { //dfs预处理出全是1的子树
    if (l[u])
        chk[u] = 1;

    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;

        if (v == fa)
            continue;

        dfs(v, u);

        if (!chk[v])
            chk[u] = 0;
    }
}
inline int Min(int A, int B, int C, int D, int E, int F) {
    return min(A, min(B, min(C, min(D, min(E, F)))));
}
void dfs1(int u, int fa) { //树形dp
    f[l[u]][u] = 0; //初值

    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;

        if (v == fa || chk[v])
            continue;

        dfs1(v, u);
        int f0 = f[0][u], f1 = f[1][u], g1 = g[1][u], g0 = g[0][u], h1 = h[1][u], h0 = h[0][u];
        f[1][u] = min(f0 + f[0][v] + 2, f1 + f[1][v] + 4); //正常转移
        f[0][u] = min(f1 + f[0][v] + 2, f0 + f[1][v] + 4);
        g[1][u] = min(min(g0 + f[0][v] + 2, g1 + f[1][v] + 4), min(f0 + g[1][v] + 1, f1 + g[0][v] + 3));
        g[0][u] = min(min(g1 + f[0][v] + 2, g0 + f[1][v] + 4), min(f1 + g[1][v] + 1, f0 + g[0][v] + 3));
        h[1][u] = Min(f0 + h[0][v] + 2, f1 + h[1][v] + 4,
                      g0 + g[0][v] + 2, g1 + g[1][v],
                      h0 + f[0][v] + 2, h1 + f[1][v] + 4);
        h[0][u] = Min(f1 + h[0][v] + 2, f0 + h[1][v] + 4,
                      g1 + g[0][v] + 2, g0 + g[1][v],
                      h1 + f[0][v] + 2, h0 + f[1][v] + 4);
    }

    g[0][u] = min(g[0][u], f[1][u] + 1); //以u为根转移
    g[1][u] = min(g[1][u], f[0][u] + 1);
    h[0][u] = min(h[0][u], g[0][u]);
    h[1][u] = min(h[1][u], g[1][u]);
    //  int u=u;
    // cerr<<"u="<<u<<"\n";
    // cerr<<"f[0]["<<u<<"]:" <<f[0][u]<<"\n";
    // cerr<<"f[1]["<<u<<"]:" <<f[1][u]<<"\n";
    // cerr<<"g[0]["<<u<<"]:" <<g[0][u]<<"\n";
    // cerr<<"g[1]["<<u<<"]:" <<g[1][u]<<"\n";
    // cerr<<"h[0]["<<u<<"]:" <<h[0][u]<<"\n";
    // cerr<<"h[1]["<<u<<"]:" <<h[1][u]<<"\n";
    // cerr<<"\n";
}
signed main() {
    //  freopen("lihtg.in","r",stdin);//教练让我们练习打乱七八糟的文件名emm
    //  freopen("lihtg.out","w",stdout);
    read(n);
    scanf("%s", s + 1);

    for (int i = 1; i <= n; i++)
        l[i] = s[i] - '0';

    for (int i = 1, u, v; i <= n - 1; i++) {
        read(u), read(v);
        add(u, v), add(v, u);
    }

    int rt = 1;

    for (int i = 1; i <= n; i++)
        if (l[i] == 0)
            rt = i; //找一个初始为0的点

    dfs(rt, 0);
    memset(f, 0x3f, sizeof(f)); //初值
    memset(g, 0x3f, sizeof(g));
    memset(h, 0x3f, sizeof(h));
    dfs1(rt, 0);
    printf("%lld\n", h[1][rt]);
    return 0;//完结撒花
}