一道想着暴力骗分然后没有想到暴力直接AC的题

//方法一：暴力写法
#include<iostream>
#include<cstring>
using namespace std;
const int N=200010;
int h[N],e[N],ne[N],w[N],idx;
int d[N],n,m,st[N];
int u,v,ans;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int id,int dis)
{
    dis+=d[id];
  if(id==v||dis>=ans)
    {
        ans=min(ans,dis);
        return ;
    }
    for(int i=h[id];i!=-1;i=ne[i])
    {
        int b=e[i];
        if(!st[b])
        {
        st[b]=true;
        dfs(b,dis);
        st[b]=false;
       }
    }
}
int main()
{
    cin>>n>>m;
    memset(h,-1,(n+1)*4);
    for(int i=1;i<=n-1;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y),add(y,x);
        d[x]++,d[y]++;
    }
    while(m--)
    {
        ans=1e9;
        cin>>u>>v;
        dfs(u,0);
        cout<<ans<<endl;
    }
    return 0;
}

//堆优化版的dijistra，但是这道题好像还没有暴力解法快
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=200010;
typedef pair<int,int> PII;
int h[N],e[N],ne[N],w[N],idx;
int d[N],n,m,st[N],dist[N];
int u,v,ans;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dijistra()
{
  priority_queue<PII,vector<PII>,greater<PII>> heap;
  heap.push({0,u});
  memset(dist,0x3f3f3f,(n+1)*4);
  memset(st,0,(n+1)*4);
  dist[u]=d[u];//dist里面储存的是到u点的距离，这道题自己到自己也有距离；
  while(heap.size())
  {
    int t=heap.top().second;
    heap.pop();
    if(t==v) return ;
    if(st[t]) continue;
    else st[t]=true;
    for(int i=h[t];i!=-1;i=ne[i])
    {
      int b=e[i];
      if(dist[b]>dist[t]+d[b])//这里的入度相当于就是模板中的边权
      {
        dist[b]=dist[t]+d[b];
        heap.push({dist[b],b});
      }
    }
  }
}
int main()
{
    cin>>n>>m;
    memset(h,-1,(n+1)*4);
    for(int i=1;i<=n-1;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y),add(y,x);
        d[x]++,d[y]++;//两边的入度都要++；
    }
    while(m--)
    {
        cin>>u>>v;
        dijistra();
        cout<<dist[v]<<endl;
    }
    return 0;
}

简单改一下就是spfa

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=200010;
typedef pair<int,int> PII;
int h[N],e[N],ne[N],w[N],idx;
int d[N],n,m,st[N],dist[N];
int u,v,ans;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void spfa()
{
  priority_queue<PII,vector<PII>,greater<PII>> heap;
  heap.push({0,u});
  memset(dist,0x3f3f3f,(n+1)*4);
  memset(st,0,(n+1)*4);
  dist[u]=d[u];
  while(heap.size())
  {
    int t=heap.top().second;
    heap.pop();
    if(t==v) return ;
    for(int i=h[t];i!=-1;i=ne[i])
    {
      int b=e[i];
      if(dist[b]>dist[t]+d[b])
      {
        dist[b]=dist[t]+d[b];
        if(!st[b])
        {
          st[b]=true;
          heap.push({dist[b],b});
        }
      }
    }
  }
}
int main()
{
    cin>>n>>m;
    memset(h,-1,(n+1)*4);
    for(int i=1;i<=n-1;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y),add(y,x);
        d[x]++,d[y]++;
    }
    while(m--)
    {
        cin>>u>>v;
        spfa();
        cout<<dist[v]<<endl;
    }
    return 0;
}