有一棵树，q个询问，每次询问，指定一个点做树根，再给定k个点，要求把这些点分成不超过ｍ组的方案数，分配的限制是任意两个有祖先关系的点不能分在同一组。题目还保证了所有的询问的ｋ加起来不超过1e5。
如果直接在原树上DP计数，那么ｑ次询问下的DP总复杂度是平方级别的，显然不对。
由于询问点数的总和很少，所以考虑在虚树上计数。（不了解虚树的可以先学习一下，大概思想是根据询问的点来重新建一颗包含关键信息，但是规模较小的树）于是多次询问的问题就解决了。
难点转到考虑虚树上的dp计数。我们按照dfs序来dp，定义f[i][j]表示遍历到的前i个点分成j组的方案数，cnt[i]表示点i到根有多少个询问点。
那么对于f[i][j]：
①如果j<=cnt[i],也就说明光是把i的祖先们分开就需要用到j个组了，那么此时点i必然无组可放，也就是说此时没有方案行得通，于是f[i][j]=0；
②否则，f[i][j]=f[i-1][j-1]+f[i-1][j]*(j-cnt[i]).这个应该不难理解，我们是按照dfs序来dp的,dp到点i时其祖先一定已经更新完了。那么对于新来的点i，它要么新开一组，方案数为f[i-1][j-1]，要么加入到已有的组中，方案数为f[i-1][j]*(j-cnt[i]),（即从已有的组中扣去那些祖先所在的组）。
考虑到空间有点吃紧，可以滚动dp，当然精打细算一点，开二维数组来DP的空间也正好够。
#include<bits/stdc++.h>
#define dd(x) cout<<#x<<" = "<<x<<" "
#define de(x) cout<<#x<<" = "<<x<<endl
#define sz(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define All(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef priority_queue<int> BQ;
typedef priority_queue<int,vector<int>,greater<int> > SQ;
const int maxn=1e5+10,INF=0x3f3f3f3f,mod=1e9+7;
vector<int> G[maxn],g[maxn];
int fa[maxn][32],dep[maxn],dfn[maxn],id;
void dfs(int u,int f)
{
dep[u]=dep[f]+1;
dfn[u]=++id;
fa[u][0]=f;
for (int i=1;i<=25;++i)
fa[u][i]=fa[fa[u][i-1]][i-1];
for (auto& v:G[u])
{
if (v==f)
continue;
dfs(v,u);
}
}
int LCA(int x,int y)
{
if (dep[x]<dep[y])
swap(x,y);
int d=dep[x]-dep[y];
for (int i=0;i<=25;++i)
if ((d>>i)&1)
x=fa[x][i];
if (x==y)
return x;
for (int i=25;i>=0;--i)
if (fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int s[maxn],top;
int a[maxn];
bool isqry[maxn];
void build(int n)
{
top=0;
for (int i=0;i<n;++i)
{
if (i-1>=0&&a[i]==a[i-1])
continue;
int u=a[i];
if (!top)
{
s[++top]=u;
continue;
}
int lca=LCA(u,s[top]);
while (top>1&&dfn[lca]<=dfn[s[top-1]])
g[s[top-1]].pb(s[top]),g[s[top]].pb(s[top-1]),--top;
if (lca!=s[top])
g[lca].pb(s[top]),g[s[top]].pb(lca),s[top]=lca;
s[++top]=u;
}
while (top>1)
g[s[top-1]].pb(s[top]),g[s[top]].pb(s[top-1]),--top;
}
ll f[500];
void cal(int u,int ff,int cnt,int m)
{
if (isqry[u])
{
for (int i=m;i>=0;--i)
{
if (i<=cnt)
f[i]=0;
else
f[i]=(f[i-1]+f[i]*(i-cnt)%mod)%mod;
}
}
for (auto& v:g[u])
{
if (v==ff)
continue;
cal(v,u,cnt+isqry[u],m);
}
g[u].clear();
isqry[u]=0;
}
int main()
{
int n,q;
cin>>n>>q;
for (int i=1;i<n;++i)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].pb(v);
G[v].pb(u);
}
dfs(1,0);
while (q--)
{
int k,m,rt;
scanf("%d%d%d",&k,&m,&rt);
a[0]=rt;
for (int i=1;i<=k;++i)
{
scanf("%d",&a[i]);
isqry[a[i]]=1;
}
sort(a,a+k+1,[&](int x,int y){return dfn[x]<dfn[y];});
build(k+1);
memset(f,0,sizeof(f));
f[0]=1;
cal(rt,0,0,m);
ll ans=0;
for (int i=1;i<=m;++i)
ans=(ans+f[i])%mod;
printf("%lld\n",ans);
}
return 0;
}Codeforces 1111 E. Tree（虚树，DP）
原文：https://www.cnblogs.com/orangee/p/10543208.html