题解 CF2207D Boxed Like a Fish

· · 题解

题解 CF2207D Boxed Like a Fish

其他题（几天后完工）

自评：下位蓝\~中位蓝。

题意

给定一棵 n 个点的树，S 和 C 两个人在树上玩游戏，C 从 v 点出发，每回合可以走一格，但是 S 每回合前可以选一条边 ban 掉不让 C 走，选择后 k 回合内不能再换，新换的边会覆盖原来选的边，即同时只能 ban 一条边。求双方都最优操作的前提下，C 是否能走到某个叶子。

数据范围：多测，t\le 10^4,\sum n\le 5\times 10^5。

做法

观察最后两组样例，发现它们之间仅 k 有区别。于是考虑为啥 k=4 C 就可以获胜了。

由于有 CD，所以最好的选择是干脆不预判，等对面差一格到叶子了再跳上去，这样尽可能让对面多跑。样例中当 k=3 时，S 可以先防 (5,6)，然后等 C 到 8 的时候刚好 CD 结束 S 跳到 (8,9)，如果 C 想去 2 也同理。而 k=4 时等 CD 结束人家 C 已经跳到 9 或者 1 了。

也就是换句话说，C 从一个距离叶子为 1 的点跳到另一个距离叶子为 1 的点的用时不能少于 k，否则 C 就能跑掉。

进一步地，这样的两个叶子路径上的所有点全部都是危险的，因为 C 一旦跳上去就立刻符合上一句话的条件从而跑掉。为了方便我们取起点为根（特判起点就是叶子的情况）这样所有的叶子都是在子树内的，直接拿深度减一减就能判断当前点是否是危险的。然后必然能跑到危险的点上的点也全都是危险的，即最终危险的点的定义为：一个点 u 是危险的当且仅当其是叶子，或者其子树内（不含 u 本身）存在两个危险的点，使得其树上路径经过 u 且路径边数小于 k+2。

这显然是个递归的过程，维护每个点子树内最浅的危险的点即可。单组时间复杂度 O(n)。

//Please ignore those headfiles.I write them just because
//DEV-C++ won't support completion if i use <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<cctype>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<queue>
#define ll long long
#define ull unsigned long long
#define lf double
#define ld long double
#define LL __int128
#define ui unsigned int
using namespace std;
ll T,n,m,s,u,v,low[500010],dep[500010];
vector<ll> a[500010];
void dfs(ll now,ll lst){
    dep[now]=dep[lst]+1;
    ll mn=999999,sec=999999;
    for(int i=0;i<a[now].size();i++){
        if(a[now][i]!=lst){
            dfs(a[now][i],now);
            if(low[a[now][i]]<mn){
                sec=mn;
                mn=low[a[now][i]];
            }
            else if(low[a[now][i]]<sec){
                sec=low[a[now][i]];
            }
        }
    }
    if(a[now].size()<=1||sec!=999999&&mn-dep[now]+sec-dep[now]<m+2){
        low[now]=dep[now];
    }
    else{
        low[now]=mn;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--){
        cin>>n>>m>>s;
        for(int i=1;i<n;i++){
            cin>>u>>v;
            a[u].push_back(v);
            a[v].push_back(u);
        }
        if(a[s].size()>1){
            dfs(s,0);
        }
        if(a[s].size()<=1||low[s]==1){
            cout<<"YES\n";
        }
        else{
            cout<<"NO\n";
        }
        for(int i=1;i<=n;i++){
            a[i].clear();
        }
    }
    return 0;
}