用C语言编写我们在玩战略性游戏时，可能会遇到这样的情形：为了探测是否有来自敌人的进攻，我们不得不在若干路口安排士兵放哨。假设把道路看成边，路口看成节点，则道路和路口在某次游戏中构成了一棵抽象的“树”。现在的问题是：如何安排最少的士兵并观测到所有边的情况？有多组测试集，每组测试集都是如下一棵树的输入： 首先输入树的节点个数n，接着用n行描述节点之间的关系。节点关系描述为：节点编号:(连接该节点边的数目m) 和该节点相邻的m个节点的编号；如果某节点没有边相连，则描述为: 节点编号:(0)。同一条边只在输入数据中输入一次输出士兵的数量。

这是一个经典的问题，可以使用贪心算法来解决。具体步骤如下：

1. 任选一个节点作为根节点，并将其标记为已覆盖。
2. 对于根节点的每个子节点，选择一个士兵放在该子节点上，并将其标记为已覆盖。
3. 对于每个未被覆盖的节点，选择其未被覆盖的子节点中深度最大的那个，放置一个士兵在该子节点上，并将其标记为已覆盖。
4. 重复步骤3，直到所有的边都被覆盖。

代码实现如下：

#include <stdio.h>
#include <stdlib.h>

#define MAXN 100005

int n, ans;
int head[MAXN], cnt;

struct Edge {
    int to, nxt;
} e[MAXN << 1];

inline void addEdge(int u, int v) {
    e[++cnt] = (Edge){v, head[u]};
    head[u] = cnt;
}

int dfs(int u, int fa) {
    int maxDepth = 0;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == fa) continue;
        int depth = dfs(v, u);
        if (depth > maxDepth) maxDepth = depth;
    }
    if (maxDepth == 0) return 1;
    else if (maxDepth == 1) {
        ans++;
        return 0;
    } else return maxDepth - 1;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v, m;
        scanf("%d:(%d)", &u, &m);
        while (m--) {
            scanf("%d", &v);
            addEdge(u, v);
            addEdge(v, u);
        }
    }
    dfs(1, 0);
    printf("%d\n", ans);
    return 0;
}

时间复杂度为 $O(n)$。