题解 CF1795F 【Blocking Chips】

Transparent · 2023-02-20 17:11:49 · 题解

题目大意

• 给定一颗 n 个节点的树，在 k 个节点（ a_1 , a_2 , a_3 \dots ）上分别有一个棋子

• 这 k 个点最初是黑色的，其它的是白色的。你需要按 a_1,a_2 \dots a_k,a_1,a_2,\dots 的顺序依次移动这 k 个棋子

• 棋子每次移动一格，移动的目标点不能是黑色，棋子经过的的点会被染成黑色

• 求至多能移动多少步

• 1 \leq k \leq n \leq 2 \times 10^5

题解

正向考虑不方便，因为我们无法确定一个点到底应该向上走更优还是向下走更优。但是如果我们知道一个点需要移动多少步，就会好解决得多。

假设我们已知每个点的目标步数，那么可以任选一点作为根节点，对树进行 dfs，对于每个节点，统计这个节点向下走至多能走多少步。

在递归返回时，如果当前节点有棋子，就进行如下判断：

• 如果向下走能走的最大步数大于当前棋子还需要走的步数，就直接向下走

• 否则就尝试向上走到父节点，如果父节点已经是黑色或当前节点已经是树根，则表明这颗棋子不可能完成目标

优先向下走的贪心一定是正确的，因为递归返回时，一定是按照深度从大到小处理，即走到当前节点时，其子树中没有棋子，或者子树中的棋子都已经达成要求，而向下走只会影响子树中的节点，而对未处理的节点没有影响，所以能向下走时，向下走一定最优。

显然步数越多，要求越难以实现，二分答案即可。

时间复杂度 O(n \log n)

代码：

#include<bits/stdc++.h>
using namespace std;
template<typename T>
void read(T &res) {
    res=0;bool f=false;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=true; ch=getchar();}
    while(ch>='0'&&ch<='9') res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
    res=f?-res:res;
}
template<typename T,typename ...Args>
void read(T &res,Args &...args) {read(res); read(args...);}
template<typename T>
void write(T x) {if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0');}
template<typename T>
inline void writeln(T x) {write(x);putchar('\n');}
template<typename T,typename ...Args>
void write(T x,Args ...args) {write(x); putchar(' '); write(args...);}
template<typename T,typename ...Args>
void writeln(T x,Args ...args) {write(x); putchar('\n'); writeln(args...);}
#define MAXN 200001
class Edge {
public:
    Edge() {
        to=next=len=0;
    }
    int to,next,len;
};
class Graph {
public:
    Graph() {
        memset(g,0,sizeof(g));
        memset(head,0,sizeof(head));
        tot=0;
    }
    inline void clear(int n) {
        memset(head,0,sizeof(int)*(n+1));
        memset(g,0,sizeof(Edge)*(tot+1));
        tot=0;
    }
    inline void addEdge(int from,int to,int len) {
        g[++tot].to=to;g[tot].next=head[from];g[tot].len=len;head[from]=tot;
        g[++tot].to=from;g[tot].next=head[to];g[tot].len=len;head[to]=tot;
    }
    Edge g[MAXN<<1];
    int head[MAXN],tot;
}g;
int n,k,need[MAXN],dep[MAXN],a[MAXN];
bool vis[MAXN];
bool dfs(int u,int fa) {
    dep[u]=0;
    for(int i=g.head[u];i;i=g.g[i].next) {
        int v=g.g[i].to;
        if(v==fa) continue;
        if(!dfs(v,u)) return false;
        if(!vis[v]) dep[u]=max(dep[u],dep[v]+1);
    }
    if(dep[u]>=need[u]) {
        return true;
    }
    if(dep[u]<need[u]) {
        if(!fa||vis[fa]) return false;
        vis[fa]=true;
        need[fa]=need[u]-1;
        need[u]=0;
    }
    return true;
}
inline bool check(int len) {
    memset(vis,0,sizeof(bool)*(n+1));
    memset(need,0,sizeof(int)*(n+1));
    vis[0]=1;
    for(int i=1;i<=k;i++) {
        need[a[i]]=len/k;
        vis[a[i]]=true;
    }
    for(int i=1;i<=len%k;i++) {
        ++need[a[i]];
    }
    return dfs(1,0);
}
inline void solve() {
    read(n);
    for(int i=1;i<n;i++) {
        int u=0,v=0;
        read(u,v);
        g.addEdge(u,v,1);
    }
    read(k);
    for(int i=1;i<=k;i++) {
        read(a[i]);
    }
    int l=0,r=n,res=0;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(check(mid)) {
            res=mid;
            l=mid+1;
        } else {
            r=mid-1;
        }
    }
    g.clear(n);
    writeln(res);
}
int main() {
    int T=0;
    read(T);
    while(T--) solve();
    return 0;
}