【TopCoder SRM598】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

思路

我们先假定选择了一个点为根,并且在根节点放置了信标。

设一个节点有 $c$ 个儿子,发现必须在其中至少 $c − 1$ 个儿子的子树中放置信标。证明如下:

  • 考虑如果不这样放,对于两棵都没有放的子树,他们汇集到 $lca$ 上以后距离都是相等的,所以 $lca$ 外的信标无法区分,而内部没有信标。所以不能存在两颗子树都不放,至少要放 $c − 1$ 个;

  • 由于在根节点放置了信标,可以只考虑深度相同的点。因为他们的 $lca$ 度数至少为 2,那么一定有一个信标在 $lca$ 包含这两个点的两支子树中。那么另一侧的点肯定要走更远的路,会被区分开。所以放 $c − 1$ 个足够区分。

所以,对于一个确定的根,我们可以贪心地放置信标,得到当前的答案。

如何选择这个根呢?找到任意一个度数大于 2 的节点,可以证明实际上这个点一定不需要放置信标,以这个点作根 $\Theta(n)$ 的贪心即可。证明如下:

对于深度相同的点,显然两个信标就可以区分它们,现在只考虑深度不同的点对。如果它们在一颗子树中,由于度数大于 2 所以一定有另一颗子树的一个信标把他们区分开。如果在不同的子树中,有两种情况:

  • 一个在没放信标的子树中,一个在放了的子树中。显然还存在另一个子树放了信标,由于深度不同他们会被这个信标区分开。

  • 两个都在放了信标的子树中。如果根的度数大于 3 则另一个子树的信标会区分它们同上。度数等于 3 时,如果他们没有被区分开,一定是他们先汇集到了一个节点,然后走到同一个信标上。这个点一定是一条奇链的中点,且不是根 (由于深度不同),是在两个子树之一中唯一的。那么他们走到另一个信标就一定有一个点走了更远的路,既另一个信标可以区分出他们。

所以最后的时间复杂度 $\Theta(n)$。

代码

#include <bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define maxn 1000100
struct ios{
    inline char read(){
        static const int IN_LEN=1<<18|1;
        static char buf[IN_LEN],*s,*t;
        return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
    }
    template <typename _Tp> inline ios & operator >> (_Tp&x){
        static char c11,boo;
        for(c11=read(),boo=0;!isdigit(c11);c11=read()){
            if(c11==-1)return *this;
            boo|=c11=='-';
        }
        for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
        boo&&(x=-x);
        return *this;
    }
}io;
struct Edge{
    int to,next;
    Edge(int a=0,int b=0){
        to=a,next=b;
    }
}l[maxn<<1];
int head[maxn],cnt,n,root;
int f[maxn],deg[maxn];
void Add(int a,int b){
    l[++cnt]=Edge(b,head[a]);
    head[a]=cnt;
}
void Dfs(int u,int fa){
    bool flag=0;
    for (register int i=head[u];i;i=l[i].next){
        int v=l[i].to;
        if (v==fa) continue;
        Dfs(v,u);
        f[u]+=max(1,f[v]);
        if (!f[v]) flag=1;
    }
    f[u]-=flag;
}
int main(){
    freopen("beacon.in","r",stdin);
    freopen("beacon.out","w",stdout);
    io>>n;
    if (n==1){puts("0");return 0;}
    for (register int i=1,a,b;i<n;++i){
        io>>a>>b;
        Add(a,b),Add(b,a);
        deg[a]++,deg[b]++;
    }
    for (register int i=1;i<=n;++i)
        if (deg[i]>2) {root=i;break;}
    if (!root){puts("1");return 0;}
    Dfs(root,0);
    printf("%d",f[root]);
}
Show Comments