题目分析

给定无向图，每个点有颜色，求所有长度 ≥ 2 且颜色互不相同的简单路径数量。

算法思路：状态压缩DP

状态设计

定义 $dp[x][sta]$：以节点 $x$ 结尾，使用颜色集合为 $sta$ 的路径数量。

关键观察

• 路径长度 ≥ 2 等价于颜色数 ≥ 2
• 状态 $sta$ 记录已使用的颜色集合
• 按颜色数从小到大进行DP转移

算法流程

1. 初始化

for(int i=1; i<=n; i++) {
    cin >> col[i];
    col[i]--;  // 转为0-indexed
    dp[i][1<<col[i]] = 1;  // 单点路径
}

2. 状态转移

枚举所有状态 $sta$，对每个节点 $x$：

• 如果颜色数 ≥ 2，累加到答案
• 向邻居 $y$ 转移，要求 $y$ 的颜色不在 $sta$ 中

for(int sta=1; sta<(1<<k); sta++) {
    int cnt = __builtin_popcount(sta);  // 颜色数
    
    for(int x=1; x<=n; x++) {
        if(cnt >= 2) ans += dp[x][sta];  // 长度≥2的路径
        
        for(int i=head[x]; i!=-1; i=nxt[i]) {
            int y = ver[i];
            if(sta >> col[y] & 1) continue;  // 颜色重复
            
            dp[y][sta|(1<<col[y])] += dp[x][sta];
        }
    }
}

复杂度分析

• 状态数：$O(2^K)$
• 节点数：$O(N)$
• 总复杂度：$O(2^K \cdot (N+M))$
• 可行性：$K \leq 5$ 时 $2^K=32$，完全可行

样例验证

样例1：

• $N=4, K=3$，颜色：1,2,1,3
• 通过DP计算所有颜色不重复的路径
• 输出：10，与样例一致

算法优势

• 避免重复计数：状态压缩确保颜色不重复
• 高效计算：利用位运算快速判断颜色冲突
• 完整覆盖：枚举所有可能的颜色组合

该解法通过状态压缩DP高效解决了颜色约束下的路径计数问题。