Description

给一棵 m 个结点的无根树, 你可以选择一个度数大于 1 的结点作为根, 然后给一些结点 (根、部结点和叶子均可) 着以黑色或白色. 你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点 (哪怕是这个叶子本身). 对于每个叶结点 u, 定义 c [u] 为从 根结点从 U 的简单路径上最后一个有色结点的颜色. 给出每个 c [u] 的值, 设计着色方案, 使得 着色结点的个数尽量少.

Input

第一行包含两个正整数 \(m, n\), 其中 \(n\) 是叶子的个数,\(m\) 是结点总数. 结点编号为 \(1, 2, ..., m\), 其中编号 \(1, 2, ..., n\) 是叶子. 以下 \(n\) 行每行一个 \(0\) 或 \(1\) 的整数 (0 表示黑色, 1 表示白色), 依次为 \(c[1], c[2], ..., c[n]\). 以下 \(m-1\) 行每行两个整数 \(a, b (1 \leq a \lt b \leq m)\), 表示结点 \(a\) 和 \(b\) 有边相连.

Output

仅一个数, 即着色结点数的最小值.

Sample Input

5 3
0
1
0
1 4
2 5
4 5
3 5

Sample Output

2

Data Range

对于 100% 的数据, 保证 \(m \leq 10000, n \leq 5021\)

Solution

这是第一道不检验标准题解就 1A 的题目好开心~

就是一个树形 DP, 但是这颗树形 DP 有一些神奇的性质......

首先我们可以给一个节点 \(p\) 打一个标记或状态 \(dp[p][0 ... 2]\), 分别有:

  1. \(dp[p][0]\) 为该节点及子树不需要限定颜色所最少涂的节点数.
  2. \(dp[p][1]\) 为该子树需要最近节点为白色所最少涂的节点数.
  3. \(dp[p][2]\) 为该子树需要最近节点为黑色所最少涂的节点数.

其中转移方程可以直接看代码, 这里就不会说第二遍了 (反正也比较好推 233)

但是现在就有一个问题. 每一次整棵树的树形 DP 需要的时间复杂度是 \(O(m)\) 的, 算上所有 需要的次数复杂度应该是 \(O(m^2 - m \cdot n)\). 这样可能就会被卡常或险些 TLE 滚粗......

但是当你用上大一点的数据后就会发现无论以哪一个节点作为根结点最后的结果都是一样的 (也就是说只需要 DP 一遍就可以了 666).

感性证明就是: 你发现将这一个当前的根节点挪向它的邻居以后发现, 只有这一些 (几个) 节点 (应该是两个) 的 DP 状态改变了, 然后瞎搞一下就会发现 DP 方程的表达式并不会发生什么变化, 然后感性证明就变成了理性证明

然后大概树上瞎搞一发就可以了~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define WHITE 1
#define BLACK 0
using namespace std;
typedef long long lli;
const int maxn = 10010, maxm = 30010;

template <typename _T>
_T min_3(_T __x, _T __y, _T __z) { return min(min(__x, __y), __z); }

int n, m;
int req[maxn];

class TreeDP
{
public:
    struct edge
    {
        int u, v;
        edge *next;
    };
    int root, ecnt;
    edge *edges[maxn], epool[maxm];
    int par[maxn];
    void add_edge(int u, int v)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v;
        p->next = edges[u]; edges[u] = p;
        q->u = v; q->v = u;
        q->next = edges[v]; edges[v] = q;
        return ;
    }
    int dp[maxn][3]; // 0: Requires no colour, 1: requires white, 2: requires black
    void dfs(int p)
    {
        // Edge detection
        if (p <= m) {
            dp[p][0] = 1;
            dp[p][1] = dp[p][2] = 1;
            if (req[p] == WHITE)
                dp[p][1] = 0;
            else if (req[p] == BLACK)
                dp[p][2] = 0;
            // printf("dfsing %d (%d, %d, %d)\n", p, dp[p][0], dp[p][1], dp[p][2]);
            return ;
        }
        // Serving as non-leaf node
        dp[p][0] = 0;
        dp[p][1] = 0;
        dp[p][2] = 0;
        for (edge *ep = edges[p]; ep; ep = ep->next)
            if (ep->v != par[p]) {
                par[ep->v] = p;
                dfs(ep->v);
                // Requires no colour, meaning all colours are resolved hitherto.
                dp[p][0] += min_3(dp[ep->v][0], dp[ep->v][1] + 1, dp[ep->v][2] + 1);
                // Requires white at this point
                dp[p][1] += min_3(dp[ep->v][0], dp[ep->v][1], dp[ep->v][2] + 1);
                // Requires black at this point
                dp[p][2] += min_3(dp[ep->v][0], dp[ep->v][1] + 1, dp[ep->v][2]);
            }
        // printf("dfsing %d (%d, %d, %d)\n", p, dp[p][0], dp[p][1], dp[p][2]);
        return ;
    }
    int eval(void)
    {
        root = n;
        dfs(root);
        return min_3(dp[root][0], dp[root][1] + 1, dp[root][2] + 1);
    }
} graph;

int main(int argc, char** argv)
{
    // n nodes, m leaves
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d", &req[i]);
    for (int i = 1, a, b; i <= n - 1; i++) {
        scanf("%d%d", &a, &b);
        graph.add_edge(a, b);
    }
    int res = graph.eval();
    printf("%d\n", res);
    return 0;
}