daily 2

CF 1774E

我们可以知道，除了这些必须走的点之外，其余还要走的点包括了a和b经过的点距离正好为d的点，我们可以在每次深搜的时候++now，然后回溯的时候—now,这样可以保证正好为d

void solve(){
  int n,d;
  cin>>n>>d;
  vector<vector<int>>E(n+1);
  for(int i=0;i<n-1;++i){
    int u,v;
    cin>>u>>v;
    E[u].push_back(v);
    E[v].push_back(u);
  }
  int m1,m2;
  cin>>m1;
  vector<int>vis1(n+1),vis2(n+1),must1(n+1),must2(n+1);
  for(int i=0;i<m1;++i){
    int x;cin>>x;
    vis1[x]=1;
  }
  cin>>m2;
  for(int i=0;i<m2;++i){
    int x;cin>>x;
    vis2[x]=1;
  }
  int num1=0,num2=0;
  vector<int>ids(n+1);
  int cnt=0;
  function<void(int,int)>dfs=[&](int x,int f){
    ids[++cnt]=x;//use for optimization,make sure that now-d is always the points that has distance d
    for(int v:E[x]){
        if(v==f)continue;
        dfs(v,x);
        if(must1[v])must1[x]=1;
        if(must2[v])must2[x]=1;
    }
    int last_d_dep;
    if(cnt-d<=0)last_d_dep=1;
    else last_d_dep=ids[cnt-d];
    --cnt;//make sure it is the nearest d dep point
    if(vis1[x])vis2[last_d_dep]=1,must1[x]=1;
    if(vis2[x])vis1[last_d_dep]=1,must2[x]=1;
    if(must1[x])++num1;
    if(must2[x])++num2;
  };  
  dfs(1,0);  
  cout<<2*(num1+num2-2)<<'\n';
  return;
}

CF 1540B
现在还没有完全理解，看这个(https://www.luogu.com.cn/problem/solution/CF1540B)

#define int ll
const int INV=500000004;
ll quick_pow(ll x,ll exp,int p)
{
      ll ans=1;
      while(exp)
      {
        if(exp&1)ans=ans*x%p;
        exp>>=1;
        x=x*x%p;
      }
      return ans;
}
void solve(){
  int n;
  cin>>n;
  vector<vector<int>>E(n+1),fa(n+1,vector<int>(32));
  vector<int>dep(n+1);
  for(int i=1;i<=n-1;++i){
    int u,v;
    cin>>u>>v;
    E[u].push_back(v);
    E[v].push_back(u);
  }
  function<void(int,int)>dfs=[&](int x,int f){
    fa[x][0]=f;
    dep[x]=dep[f]+1;
    for(int i=1;i<20;++i)fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int v:E[x]){
        if(v==f)continue;
        dfs(v,x);
    }
  };
  function<int(int,int)>LCA=[&](int x,int y){
    if(dep[x]<dep[y])swap(x,y);//x is deeper
    for(int i=19;i>=0;--i){
        if(dep[x]-(1<<i)>=dep[y]){
            x=fa[x][i];
        }
    }
    if(x==y)return x;
    for(int i=19;i>=0;--i){
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i],y=fa[y][i];
        }
    }
    return fa[x][0];
  };
  vector dp(n+1,vector<int>(n+1));
  for(int i=1;i<=n;++i){
    dp[0][i]=1;
  }
  for(int i=1;i<=n;++i){
    for(int j=1;j<=n;++j){
        dp[i][j]=(dp[i-1][j]+dp[i][j-1])*INV%MOD;
    }
  }
  int ans=0;
  for(int i=1;i<=n;++i){
    dfs(i,0);
    for(int j=1;j<=n;++j){
        for(int k=1;k<j;++k){
            int lca=LCA(j,k);
            ans=(ans+dp[dep[j]-dep[lca]][dep[k]-dep[lca]])%MOD;
        }
    }
  }
  cout<<ans*quick_pow(n,MOD-2,MOD)%MOD<<'\n';
  return;
}