题意：
题目给出一棵树，再给出 (m) 条树上路径，问取 (k) 条树上路径使这些路径至少有一个公共点的方法数量。
想法：
- 我们考虑怎么取就可以让路径有公共点，很显然只要有一个点相同即可，那么我们已知所有可取路径，也就可以把每条路径经过的点求出，也就可以把每个点被经过几次求出即可。
- 怎么求每个点被经过几次，考虑复杂度，暴力显然不行。想到树上点差分，这样可以在 (O(n)) 复杂度内求出每个点的被经过几次。设每个点被经过 (ans[i]) 次。
- 我们很容易想到对于设某个点为公共点，那么取法就是 (C^{ k}_{ans[i]})，但由于某些路径不止一个公共点，显然会有重边。
- 考虑一个性质：如果树上两条路径有公共点，那么其中一定有一个公共点是某一条路径的两个端点的 (lca)。
- 看到上述性质，那么可以对于某个点，我们只求某个点作为公共点且有公共点是某条路径的 (lca) ，这样子就可以保证没有重复方案。
这样子答案就是
代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1000000+200;
const int MOD=1000000007;
int n,m,k;
ll fact[N+5]; //阶乘
ll a[N+10]; // 乘法逆元
//LL inv[maxn+10]; //快速幂
ll pow(ll x)
{
ll n = MOD-2;
ll res=1;
while(n>0)
{
if(n%2==1)
res=res*x%MOD;
x=x*x%MOD;
n>>=1;
}
return res;
}
void init(){
a[0] = a[1] = 1;
fact[0] = fact[1] = 1;
// inv[1] = 1;
for(int i = 2; i <= 1000005; i++)
{
fact[i] = fact[i-1] * i % MOD;
a[i] = a[i-1] * pow(i) % MOD; //m!的MOD次方 = (m-1)!的MOD次方 * m的MOD次方
// inv[i] = (MOD - MOD/i)*inv[MOD%i]%MOD;
// a[i] = a[i-1] * inv[i] % MOD;
}
}
ll C(int n, int m){ //乘法逆元
if(n<0||m<0||n<m)return 0;
return fact[n]*a[n-m]%MOD*a[m]%MOD;
}
struct LCA
{
int head[N<<1],Next[N<<1],edge[N<<1],ver[N<<1],tot;
int deep[N],fa[N][22],lg[N],date[N],ans[N];
int sumlca[N];
inline void init()
{
memset(head,0,sizeof(head));
memset(deep,0,sizeof(deep));
memset(sumlca,0,sizeof(sumlca));
memset(ans,0,sizeof(ans));
memset(date,0,sizeof(date));
memset(deep,0,sizeof(deep));
memset(fa,0,sizeof(fa));
tot=0;
}
inline void add_edge(int a,int b,int c)
{
edge[++tot]=b;
ver[tot]=a;
Next[tot]=head[a];
head[a]=tot;
}
inline void dfs(int x,int y)
{
deep[x]=deep[y]+1;//深度是父亲节点+1
fa[x][0]=y;//2^0=1,也就是父亲节点
for(int i=1; (1<<i)<=deep[x]; i++) //2^i<=deep[x]也就是别跳出根节点了
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head[x]; i; i=Next[i]) //遍历所有的出边
if (edge[i]!=y)//避免回到父亲节点
dfs(edge[i],x);//自己的儿子节点, 自己是父亲节点
return ;
}
inline int Lca(int x,int y)//Lca过程
{
if (deep[x]<deep[y])//x节点默认深度深一些,在下面
swap(x,y);//交换
while(deep[x]>deep[y])//还没有同一高度
x=fa[x][lg[deep[x]-deep[y]]-1];//往上面跳跃,deep[x]-deep[y]是高度差.-1是为了防止deep[x]<deep[y]
if(x==y)//意外发现,y就是(x,y)的Lca
return x;
for(int i=lg[deep[x]]; i>=0; i--)
if (fa[x][i]!=fa[y][i])//没有跳到Lca
{
x=fa[x][i];//旋转跳跃
y=fa[y][i];//我闭着眼
}
return fa[x][0];//父亲节点就是Lca,因为本身是离着Lca节点最近的节点,也就是Lca的儿子节点.
}
//点差分
inline void query(int x)
{
int sum=0;
for(int i=head[x];i;i=Next[i])
{
int j=edge[i];
if(deep[x]>deep[j])continue;
query(j);
sum+=ans[j];
}
sum+=date[x];
ans[x]=sum;
}
inline void update(int x,int y)//修改操作,x,y节点构成的路径统一+1
{
int now=Lca(x,y);
date[x]++;
date[y]++;
date[now]--;
if(now!=1)date[fa[now][0]]--;
sumlca[now]++;
}
}G;
int main()
{
int T;
init();
cin>>T;
while(T--){
scanf("%d%d%d",&n,&m,&k);
G.init();
for(int i=1; i<n; i++)
{
int a,b;
scanf("%d%d",&a,&b);
G.add_edge(a,b,0);//加边
G.add_edge(b,a,0);//无向图
}
for(int i=1; i<=n; i++)
G.lg[i]=G.lg[i-1]+(1<<G.lg[i-1]==i);//处理log数组的关系
G.dfs(1,0);
for(int i=1; i<=m; i++)
{
int a,b;
scanf("%d%d",&a,&b);
G.update(a,b);//附加边
}
G.query(1);
//for(int i=1;i<=n;i++)cout<<G.ans[i]<<" "<<G.sumlca[i]<<endl;
ll fans=0;
for(int i=1;i<=n;i++){
//printf("xx%d
",G.ans[i]);
fans=(((fans+(C(G.ans[i],k)-C(G.ans[i]-G.sumlca[i],k)+MOD)%MOD+MOD)%MOD)%MOD+MOD)%MOD;
}
cout<<fans<<endl;
}
return 0;
}