题解 P3942 【将军令】

· · 题解

此题有O(n)做法。

把驿站看做节点，则整张图就是一颗树，假设1号节点为根节点。

令f(x)表示编号为x的节点与以其为根节点的子树中最近一个未被控制的节点的距离+k，如果没有这样的节点，则f(x)表示编号为x的节点与以其为根节点的子树中最近一个驻有军队的节点的距离。

这意味着当f(x)>k时，在以x为根节点的子树中，存在不被控制当节点。f(x)>2k时，节点x必须驻扎军队。于是，我们可以求出每一个节点的f(x)值，从而贪心求出最优方案下需要的军队数量。

核心代码：

int dfs(int node)
{
    vis[node]=1;
    int res1=-1,temp=-1;
    int res2=99999999;      res1表示最大值，res2表示最小值。
    for(int i=first[node];i!=-1;i=next[i]){
        if(vis[to[i]]==1)
            continue;
        temp=dfs(to[i]);
        遍历子节点，求最大最小值。
        if(res1<temp)
            res1=temp;
        if(res2>temp)
            res2=temp;
    }
    if(res1==2*k||(node==1&&res1+res2>=2*k)){
        ans++;
        return 0;       如果不驻扎军队，则有节点控制不到。
    }
    if(temp==-1)
        return k+1;     该节点是叶子节点。
    if(res1+res2<2*k)
        return res2+1;
    return res1+1;
    在这里计算f(x)值，并返回。
    具体的计算方法请读者自己思考。
    f(x)的意义比较难理解，即使理解了，写起来也很容易出错。
    在考场上遇到这种题还是不要尝试O(n)算法。
    毕竟O(nk)算法也能过。
}