CF1611E2 Escape The Maze (hard version)

Lacrymabre · 2021-11-28 11:34:01 · 题解

题目简述：现在有一棵树，其中1号节点是树根，树上边都是双向边。树上有 n 个点，您有 k 位朋友。每个时刻，您和您的朋友都会顺着树上的边走向另一个节点。

您会获胜当且仅当你走到了叶子节点。

您会输当且仅当您被一个朋友在您获胜之前在任何房间或走廊遇到。

问：至少在树中保留多少个朋友才能使您在游戏中失败？

和 Escape The Maze (easy version) 一样的是，如果能够判断您获胜，也就是说 k 个朋友一起出动都不能使你失败，那么直接输出 -1

否则，当您不能前往一个节点时，这个节点至少需要1个朋友来封锁。

void getime(ll now,ll fa){  
    ll len=s[now].size();
    for(int i=0;i<len;i++){
        ll y=s[now][i];
        if(y==fa) continue;
        dep[y]=dep[now]+1;
        getime(y,now);
        tline[now]=min(tline[now],tline[y]+1);
    }
}

void cheak(ll now,ll fa){
    ll len=s[now].size();
    if(len==1&&s[now][0]==fa){// had been arrived
        flag=1;
        return;
    }
    for(int i=0;i<len;i++){
        ll y=s[now][i];
        if(y==fa) continue;
        if(tline[y]>dep[y]) cheak(y,now);
        else need++;
    }
    //if(res==0) flag=1;
}

void clear(ll n,ll k){
    for(int i=1;i<=n;i++) s[i].clear(),tline[i]=1e9;
    for(int i=1,d;i<=k;i++) d=read(),tline[d]=0;
    for(int i=1,u,v;i<n;i++) u=read(),v=read(),s[u].push_back(v),s[v].push_back(u);
}

int main(){
    t=read();
    while(t-->0){
        n=read();k=read();
        clear(n,k);
        getime(1,0);
        flag=0;
        need=0;
        cheak(1,0);
        if(flag) cout<<-1<<"\n";
        else cout<<need<<"\n";
    }
    return 0;
}