题意：
给定一棵n个节点的树 有m条路径 问有多少种方案 使得 从m条路径里面选k条路径 这k条路径至少包含一个公共点
题解:
- 首先可以用树上差分求出 有多少条路径经过某个点
- 但是不能直接用该信息来统计答案 因为这k条路径可能包含多个公共点 会重复统计答案
- 为了避免多次重复统计 可以转化到lca上 利用lca的唯一性
- 所以当某个点为某条边 或几条边 的lca时 统计这条边的答案集
- 该统计方案一定不会重复 可以随便模拟试试
#include<bits/stdc++.h> using namespace std; const int N=3e5+6; const int mod=1e9+7; #define ll long long int head[N],pos,sum[N],n,m,k,fa[N][20],dep[N],cnt[N]; ll inv[N],fac[N]; struct Edge{int to,nex;}edge[N<<1]; void add(int a,int b){edge[++pos]=(Edge){b,head[a]};head[a]=pos;} void dfs(int x,int f) { fa[x][0]=f;dep[x]=dep[f]+1; for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to;if(v==f)continue; dfs(v,x); } } int getlca(int x,int y) { if(dep[x]<dep[y])swap(x,y); for(int i=19; i>=0; --i) { if(dep[fa[x][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]; } void dfs2(int x,int fa) { for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(v==fa)continue; dfs2(v,x);sum[x]+=sum[v]; } } ll C(int n,int m) { if(n<m||m==0)return 0; return fac[n]*inv[m]%mod*inv[n-m]%mod; } ll calc(int x) { ll ans=C(sum[x],k); ans=(ans-C(sum[x]-cnt[x],k)%mod)%mod; return (ans+mod)%mod; } int main() { inv[0]=inv[1]=fac[1]=1; for(int i=2;i<=N;i++)fac[i]=fac[i-1]*i%mod; for(int i=2;i<=N;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod; for(int i=2;i<=N;i++)inv[i]=inv[i-1]*inv[i]%mod; int cas;cin>>cas; while(cas--) { cin>>n>>m>>k;int u,v; for(int i=1;i<n;i++)scanf("%d%d",&u,&v),add(u,v),add(v,u); dfs(1,0); for(int j=1;j<20;j++) for(int i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1]; while(m--) { scanf("%d%d",&u,&v); int lca=getlca(u,v); sum[u]++;sum[v]++; sum[lca]--;sum[fa[lca][0]]--; cnt[lca]++; } dfs2(1,0); ll ans=0; for(int i=1;i<=n;i++)ans+=calc(i),ans%=mod; cout<<ans<<endl; for(int i=1;i<=n;i++)sum[i]=head[i]=dep[i]=cnt[i]=0;pos=0; } return 0; }