CF1611E1 Escape The Maze (easy version)

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

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

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

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

问：您是否会在这场游戏中获胜？

题解：维护一个时间数组，表示朋友到达这个点的最短时间，维护一个深度数组，表示您到达点的最段时间。

容易发现，您能到达一个点，当且仅当您到达这个点的时间比任何朋友都要早。

dfs即可。

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 res=0,len=s[now].size();
    for(int i=0;i<len;i++){
        ll y=s[now][i];
        if(y==fa) continue;
        res=1;
        if(tline[y]>dep[y]) cheak(y,now);
    }
    if(res==0) flag=1;
}

oid 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;
        cheak(1,0);
        if(flag) cout<<"yes\n";
        else cout<<"no\n";
    }
    return 0;
}