CF1675F Vlad and Unfinished Business 题解

· · 题解

超级简单题。

令起点为 St，终点为 Ed。既然是从 St 出发，那么就令 St 作为树的根去处理。

对每个点 u 设置一个 vis 标记。如果这个点是 Ed，标记 vis_u = 2；如果这个点不是 Ed，但是某个 a_i，标记 vis_u = 1；如果这个点不是 Ed 也不是 a_i，标记 vis_u = 0。

考察点 u 与其父节点 fa 之间的边在最优情况下会经过多少次。这显然与 u 点的子树内的标记情况相关。

如果子树内存在某个 vis_v = 2，说明最终会停留在该子树内，那么最优情况下肯定只会从 fa 进入 u 一次，不会再出来了。因此这条边的贡献为 1。

如果子树内不存在 2，但是有若干个 vis_v = 1，说明需要进入该子树，但因为最终不会停留，所以还会出去一次。最优情况下肯定是从 fa 进入 u 一次，再从 u 出去 fa 一次。因此这条边的贡献为 2。

如果子树内不存在 2 也不存在 1，说明这个子树根本没有进去的必要，最优情况下肯定也不会选择进去。因此这条边的贡献为 0。

DFS 即可。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2e5+5;
int T,n,k,St,Ed,flag[N];
LL Ans;
vector<int> g[N];
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
void DFS_init(int u,int fa){
    for(int v:g[u])if(v^fa)
        DFS_init(v,u),flag[u]=max(flag[u],flag[v]);
    return;
}
void DFS_sol(int u,int fa){
    for(int v:g[u])if(v^fa){
        if(flag[v]==1)DFS_sol(v,u),Ans+=2;
        if(flag[v]==2)DFS_sol(v,u),Ans+=1;
    }return;
}
int main(){
    T=read();
    while(T--){
        n=read(),k=read();
        St=read(),Ed=read();
        for(int i=1;i<=n;i++)g[i].clear(),flag[i]=0;
        for(int i=1;i<=k;i++)flag[read()]=1;
        flag[Ed]=2;
        for(int i=1;i<n;i++){
            int x=read(),y=read();
            g[x].pb(y),g[y].pb(x);
        }
        Ans=0;
        DFS_init(St,0);DFS_sol(St,0);
        cout<<Ans<<"\n";
    }
    return 0;
}

::::

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！