题解【CF1695D2 Tree Queries (Hard Version)】

· · 题解

分享一个做法。

题意：

给你一棵树，你可以询问一些点 v_1,\dots,v_k（仅一次），你可以获得它们到一个神秘节点的距离 d_1,\dots,d_k。

问至少询问多少个节点，可以在神秘节点是任意节点时，将其推断出来。

以下 d_i 表示神秘节点到 i 的距离。

首先我们考虑选了两个点可以知道那些信息：

假设我们当前选了 7,9 两个点，如果 d_7+d_9=dis(7,9)（dis(x,y) 表示 x,y 间的最短距离），那么这个点可以被唯一确定（如上图若 d_7=3,d_9=2，那么神秘节点一定是 1）。

那么如果 d_7+d_9>dis(7,9)（显然 d_7+d_9\ge dis(7,9)），可以考虑把这两点路径上每一个点附带部分分成一组（看图，蓝圈代表一组），若神秘点在某个组内，那么 7,9 都是先走到该组内的红色节点（7,9 路径上的点），再从红色点往下走。可以发现 7,9 在神秘点所在组内走的路径都是相同的，即红色点到神秘点的最短路径。

所以，

我们可以通过不断将 d_7,d_9 分别减 1，直到 d_7+d_9=dis(7,9) 来确定红色点；

再通过减了几次 1 来确定：这组内以红色节点为根的树，神秘节点的深度。

如上图若 d_7=5,d_9=4，那么我们先化为 d_7=3+2,d_9=2+2，确定红色点是 1，并且神秘点的深度为 2，因为在 \{1,3,10\} 内，深度为 2 的节点只有 10，所以神秘点是 10。

若我们已经选了两个点，那么什么情况下不能问出全部神秘节点？ 我们发现，这两个点确定了这条路径上所有点，因此我们可以将这条路径上的所有边看做“虚化”了，一条边虚化后，不计入度数。若此时有一个点度数 \ge3，神秘节点若在这个点的子树内，则有可能无法唯一确定。

如图，如果我们仅仅是知道了走到红色节点 1 并且深度为 2，那么有可能是 8,9 中的任意一个。

利用虚化的思想拓广：三个点时会怎么样，仔细思考后就会发现，虚化的边集即为三个点两两间路径边集的并，也就是说，把三个点两两间路径上的边全部虚化。

在虚化过程中，选择度为 2 的点，一定不如选择其连接至的度为非 2 的节点。否则不是选了没用，就是两边都得选别的点，但是两边都得选，不就覆盖其本身了吗？所以度为 2 的点可以直接删除，并不影响结果（不影响别的点的度数）。

具体的，对于一个度为 2 的点，我们直接将其连到的两个点连边，并删除其。

删完度为 2 的点后，场上还剩下这些东西：一些度 \ge3 的节点，构成一个树形结构（称之为新树），每个点上带了一些度为一的点（称为附属点）。接下来我们要选点，使得所有度 \ge3 的点变小。

贪心选择，选择新树上所有度为 1 的点中的一个附属点，这样就可以把整个新树边全部虚化并且花费最小。若连非附属点，则比连附属点少虚化一条边。若连度非 1 的节点，则度为 1 的还要单独处理，至少不劣。

至于最后剩下的附属点，那只能暴力选了，注意可以留一个不选。

复杂度 O(n\log n)

代码：

//赛时的，由于一些原因可能有一些神秘操作
//其实不是赛时的，赛时的代码由于两个小问题 wa on 2了
int n,m,d[200005],vis[200005];
set<int>E[200005]; 
inline void work(){
    for(int i=1;i<=n;i++){
        E[i]=set<int>();
        d[i]=vis[i]=0;
    }
    n=read();
    if(n==1)return pus("0"); 
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        E[x].insert(y);E[y].insert(x);
    }
    if(n==2)return pus("1");
    for(int i=1;i<=n;i++){
        if(E[i].size()==2){//删度为 2 的点
            int u=*E[i].begin(),v=*--E[i].end();
            vis[i]=1;
            E[u].erase(i);E[v].erase(i);
            E[u].insert(v);E[v].insert(u);
        }
    }
    for(int i=1;i<=n;i++)d[i]=E[i].size();
    int cnt=0;
    for(int i=1;i<=n;i++){
        cnt+=(E[i].size()==1);
        if(E[i].size()==1)vis[i]=2;
    }
    if(cnt==2)return pus("1");
    for(int i=1;i<=n;i++){
        if(vis[i]==2){//找新树
            vis[i]=1;
            int u=*E[i].begin();
            E[u].erase(i);E[i].erase(u);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(E[i].size()==1){d[i]-=2;ans++;}
        else d[i]-=(int)E[i].size();
        //如果在新树上度为 1，那就是其中一条上出边，与一条连到附属点的边虚化
        //否则减新树上所有出边
        if(!vis[i])ans+=max(d[i]-1,0);//还有剩下的附属点
    }
    write(ans,'\n');
}