A49077.树 题解

根据定义，根节点没有父亲。

所以，首先可以排除父子关系里的儿子；

其次，儿子的儿子也可以排除；

再其次，儿子的儿子的儿子也可以排除……

所以，以儿子为根的子树全部排除。

Code:

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+16;
int n,q,u,v,ans;
vector<int> gra[MAXN];
bool vis[MAXN];
inline void dfs(const int &idx,const int &fath){
    if(vis[idx]) return;
    vis[idx]=true;
    ans++;
    for(auto &i:gra[idx]){
        if(i==fath) continue;
        dfs(i,idx);
    }
    return;
}
int main(){
    cin>>n>>q;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        gra[u].push_back(v);
        gra[v].push_back(u);
    }
    for(int i=1;i<=q;i++){
        cin>>u>>v;
        dfs(v,u);
    }
    cout<<n-ans;
    return 0;
}