LA 3902网络【dfs】

这个题目，就放到树上分析。
对于每一个点。深搜他能覆盖到的点即可。

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
#define sc(x) scanf("%d",&x)
#define pf(x) printf("%d\n",x)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define fi first
#define se second
using namespace std;
const int mod=1e9+7;
typedef long long ll;
const int maxn=1e3+50;
const int inf=0x3f3f3f3f;
typedef pair <int,int> PII;
ll fpow(ll n,ll k,ll p =mod){ll r=1;for(;k;k>>=1){if(k&1)r=r*n%p;n=n*n%p;}return r;}
ll inv(ll n, ll p=mod) {return fpow(n,p-2,p);}
ll fact[maxn];
void init(){fact[0]=1;for(int i=1;i<maxn;i++)fact[i]=fact[i-1]*i%mod;}
ll C(ll n,ll m,ll p){ll r = fact[n]; r = r * inv(fact[m])%p; r = r*inv(fact[n-m])%p;return r;}
int fa[maxn];
vector<int>G[maxn];
int n,s,k;
void add_edge(int u,int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}
int vis[maxn];
vector<PII>v;
bool cmp(PII a,PII b)
{
    if(a.fi==b.fi) return a.se<b.se;
    else a.fi>b.fi;
}
void dfs(int x,int f,int d)
{
    fa[x]=f;
    if(G[x].size()==1&&d>k)v.push_back(PII(d,x));
    for(int i=0;i<G[x].size();i++)
    {
        int v = G[x][i];
        if(v!=f) {;dfs(v,x,d+1);}
    }
    return ;
}
void dfs2(int x,int f,int d)
{
   //cout<<x<<" "<<d<<endl;
   if(d<=k&&G[x].size()==1)vis[x]=1;
   for(int i=0;i<G[x].size();i++)
   {
       int w=G[x][i];
       if(w!=f&&d<k) dfs2(w,x,d+1);
   }
}
void solve(int m)
{
    int f=m;
    for(int i=1;i<=k;i++) f = fa[f];
    dfs2(f,-1,0);
}
int main()
{
    int t;
    sc(t);
    while(t--)
    {
        sc(n);cl(fa);
        v.clear();
        for(int i=0;i<=n;i++) G[i].clear();
        sc(s);sc(k);
        for(int i=0;i<n-1;i++)
        {
            int u,v;
            sc(u);sc(v);
            add_edge(u,v);
        }
        dfs(s,-1,0);
        sort(v.begin(),v.end());
        //rep(i,0,v.size()-1) cout<<v[i].fi<<" "<<v[i].se<<endl;
        cl(vis);
        int ans=0;
        for(int i=v.size()-1;i>=0;i--)
        {
            int m = v[i].se;
            int d = v[i].fi;
            if(!vis[m]) {solve(m);ans++;
            //cout<<m<<" "<<ans<<endl;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}