36分求助
查看原帖
36分求助
188278
lonLonlon楼主2024/11/26 19:43

求大佬帮助

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
//Tree
vector<int> depth(maxn+1, -1); 
vector<int> father(maxn+1, -1);
vector<vector<int>> adj(maxn+1, vector<int>());//adj[x] includes father[x]

int dp[maxn];
int star[maxn];
int ans=0;
int leaves[maxn];
int CountLeaves(int node){
    if(adj[node].size()==1){
        leaves[node]=1;
        return 1;
    }
    int re=0;
    for(auto &neighbor : adj[node]){
        if(neighbor!=father[node]){
            re+=CountLeaves(neighbor);
        }
    }
    leaves[node]=re;
    return re;
}
void SearchStars(int node){ //returns the number of stars in given root
    for(auto &neighbor : adj[node]){
        if(neighbor!=father[node]){
            SearchStars(neighbor);
            dp[node]+=dp[neighbor];
        }
    }
    dp[node]=min(dp[node],leaves[node]);
}
int a[maxn];
int main(){
    ios::sync_with_stdio(false);
    memset(leaves,0,sizeof(leaves));
    memset(dp,0,sizeof(dp));
    memset(star,0,sizeof(star));
    cin.tie(0);
    int N, K=1;
    cin >> N ;
    for(int i=1;i<=N;i++){
        cin>>a[i];// wait for n leaves
    }
    for(int i=0; i<N-1; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    //let k be root of the whole tree
    // BFS 
    queue<int> q;
    q.push(K);
    depth[K] = 0;
    father[K] = K;
    while(!q.empty()){
        int current = q.front(); q.pop();
        for(auto &neighbor : adj[current]){
            if(depth[neighbor] == -1){
                depth[neighbor] = depth[current] + 1;
                father[neighbor] = current;
                q.push(neighbor);
            }
        }
    }
    CountLeaves(K);

    //for(int i=1;i<=N;i++){
        //cout<<leaves[i]<<' ';
    //}
    for(int i=1;i<=leaves[K];i++){
        dp[a[i]]++;
    }
    SearchStars(K);
    cout<<dp[K];
    
}
2024/11/26 19:43
加载中...