[数据结构与算法]CSP 202112-5 极差路径12分暴力代码

原题链接：CSP 202112-5 极差路径

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAX=5e5+10;
const int INF=1e9;

int n,k1,k2;
vector<int> g[MAX];
int vis[MAX];
int p[MAX];
int num=1;
set<pair<int,int> > pa;

void dfs(int s,int u,int num)
{
    vis[s]=1;
    //cout<<"s:"<<s<<endl;
    int minn=INF,maxn=-INF;
    int minx=min(u,s)-k1;
    int maxx=max(u,s)+k2;
    for(int i=0;i<num;i++)
    {
        minn=min(p[i],minn);
        maxn=max(p[i],maxn);

        //cout<<p[i]<<" ";
    }
    //cout<<endl;
    if(minx<=minn && minn<=maxn && maxn<=maxx)
    {
       int a=min(u,s);
       int b=max(u,s);
       pair<int,int> tmp(a,b);
       pa.insert(tmp);
    }
    if(g[s].size()==1)
    {
        int tmp=g[s][0];
        if(vis[tmp]==1)
            return;
    }
    for(int i=0;i<g[s].size();i++)
    {
        int v=g[s][i];
        if(vis[v]==0)
        {
           p[num]=v;
           dfs(v,u,num+1);
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin>>n>>k1>>k2;
    int n1=n-1;
    while(n1--)
    {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        memset(p,0,sizeof(p));
        memset(vis,0,sizeof(vis));
        p[0]=i;
        dfs(i,i,1);
        //cout<<"---------------"<<endl;
    }
    ll sum=0;
    sum=pa.size();
    cout<<sum<<endl;
    return 0;
}