TPS

作者: 徐海珂
关键词: 树形动态规划

题目简述

• Treeland有$n$个城市,标号从$0...n-1$。有$n-1$条双向道路连接了$n$个城市构成一颗树。 Treeland的居民想要建造一套 TPS系统(Treeland Positioning System)。TPS是一个能帮助人定位他在哪个城市的系统。系统由$k$个信标构成，每个信标被安放在一个城市。当一个人打开他的TPS接收器的时候他能得到他与每一个信标的距离 (这里距离指树上两点之间经过的边的数量) 。 显然只有当在不同的城市打开TPS接收器接受到的信息不一样的时候TPS系统才能正常工作。（也就不存在两个不同的城市使得在他们那里接收到的信号相同）注意不同的信标之间是可以区分的。求最少安放多少信标才能使TPS系统正常工作。

约定与限制

• $n\in [1,50]$
• 时间限制: $2$s
• 空间限制: $64$MB

算法

• 首先发现$n=1$时答案为$0$。否则至少要放一个信标，不妨枚举一个必须放信标的位置作为树根$root$。这样所有和$root$距离不同的节点都能被区分出来了。
• 约定几个记号
• $dep[x]$为$x$的深度（假设已知根），$dis(x,y)$为$x$,$y$在树上的距离,$lca(x,y)$为$x$,$y$在树上的最近公共祖先。
• 结论1：i为某个节点，只要i子树内有一个信标，那么可以区分出一个节点是否在i子树内。

  证明： 假设$i$子树内节点$p$处有一个信标,$x$为任意一个节点,利用$p$和$root$处的信标我们可以区分出$x$是否在$i$子树内。 首先查看$x$和$root$的距离，得到$dep[x]$,再查看$x$和$p$的距离$dis(x,p)$，因为有$dis(x,p)=dep[x]+dep[p]-dep[lca(x,p)]$，其中$dis(x,p)$,$dep[x]$,$dep[p]$都是已知，所以可以得到$dep[lca(x,p)]$的值。如果$x$在$i$子树内，那么$lca(x,p)$在$i$子树内$dep[lca(x,p)]>=dep[i]$,如果$x$不在$i$子树内，那么$lca(x,p)$是$i$的祖先，$dep[lca(x,p)]\lt dep[i]$。这样就能区分$x$是否在$i$子树内了。

• 还有一个小结论
• 结论2：如果节点$i$两个不同的儿子$ch1$,$ch2$,在$ch1$,$ch2$子树内部均没有信标，那么这两个子树内部相同深度的节点无法区分。
• 这个结论比较显然，就不严格证明了。
• 接下来就可以开始动态规划了。
• 设$f[i]$为区分$i$子树内部的节点最少需要在$i$内部设多少个信标（这里假设已经能区分一个节点是否在$i$子树内）
• 由结论2得到节点$i$最多只能有一个儿子满足其子树内一个信标都没有，而且要保证这个儿子子树即使没有信标其内部节点也能够区分。其他儿子即使不需要信标也能够区分其子树内节点，仍然要在他子树内加一个信标,为了方便就加载这个儿子节点上就好了。
• 下面是转移方程的伪代码

    f[i]=inf;
    for(j是i的儿子)
    {   s=0;
        for(k是i的儿子)
            if(j!=k)
                s+=max(1,f[k]);
            else
                s+=f[k];
        f[i]=min(f[i],s);
    }
  

• 一个时间复杂度更优的伪代码写法如下

    f[i]=0;
    for(j是i的儿子) f[i]+=max(1,f[j]);
    flag=0;
    for(j是i的儿子)
        if(f[j]==0)
        {   flag=1;
            break;
        }
    f[i]-=(flag==1);
  

• $f[root]+1$就是枚举这个$root$时的答案，不同的$root$取最优解就好了。

• 整理一下，先枚举$root$为一个必放信标的节点，然后利用结论1,结论2进行树形动态规划求出$f[root]$,然后不同$root$取最优解作为答案。

• 时间复杂度: $O(n^2)$

• 空间复杂度: $O(n)$ ^footnote1

总结

• 先枚举$root$,这样可以降低区分两个节点的难度，然后证明结论1取消了后面动态规划的后效性，使得问题能够分割成一个个小的子问题，结论2便于推导出动态规划的具体方程。最后做一遍动态规划就好了。

参考资料

• SRM598 - TopCoder Wiki

^footnote1. 作者由于为了实现方便导致了参考代码中的空间复杂度为$O(n^2)$，但是$O(n)$的空间复杂度是可以做到的。 ↩