首页 > 其他分享 >Codeforces Round #787 F

Codeforces Round #787 F

时间:2022-10-13 15:37:29浏览次数:48  
标签:787 return int Codeforces son fa path Round const

F. Vlad and Unfinished Business

和一般的求多个点都到达的最小距离不同
这里规定了终点 这样我们首先x-y这条链可以确定
当然我们这条链可以通过让path[y]等于1 因为树中两点距离确定所以链一定 我们直接通过return时就可以确定链
然后我们还要确定的就是这个子树中有没有关键点
要是没有显然不用进入的
然后我们可以基于这条链把整颗树补全
然后就好做了 我们只需求这条链上每一个子树get到点的最小距离即可
这里可以直接贪心 直接返回距离即可

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int n,k,x,y,a[N],path[N],son[N];
vector<int>g[N];
int dfs1(int u,int fa){
    for(auto v:g[u]){
        if(fa==v)continue;
        son[u]+=dfs1(v,u);
        path[u]|=path[v];
    }
    return son[u];
}
int dfs2(int u,int fa){
    int res=0;
    for(auto v:g[u]){
        if(fa==v)continue;
        if(!path[v]&&son[v])res+=dfs2(v,u)+2;
    }
    return res;
}
void solve() {
    cin>>n>>k>>x>>y;
    for(int i=1;i<=n;i++)son[i]=path[i]=0,g[i].clear();
    for(int i=1;i<=k;i++){
        cin>>a[i];
        son[a[i]]=1;
    }
    path[y]=1;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(x,0);
    int ans=0;
    for(int u=1;u<=n;u++){
        if(path[u])ans+=dfs2(u,0);
    }
    cout<<ans+count(path+1,path+n+1,1)-1<<endl;
}
signed main(){
    fast
    int t;t=1;cin>>t;
    while(t--) {
        solve();
    }
    return ~~(0^_^0);
}

标签:787,return,int,Codeforces,son,fa,path,Round,const
From: https://www.cnblogs.com/ycllz/p/16788276.html

相关文章