题意
(T) 组数据，每组数据给定一棵 (n) 个点的树和 (m) 条路径，求选出 (k) 条给定路径使得至少有两条交于一点的方案数，对 (10^9+7) 取模。
( exttt{Data Range:}1leq Tleq 200,1leq nleq 3 imes 10^5,2leq mleq 3 imes 10^5,2leq kleq m)。
题解
这种题都不能一次 AC，而且还是犯的弱智错误，我太菜了。
考虑这样一个结论：如果两条路径交于一些点，那么这些点中的某一个肯定是这两条路径中一条的两个端点的 LCA。
我们枚举这样一个端点，然后容斥。设 (u_x) 为这些路径中经过 (x) 的数量，(v_x) 为这些路径中两个端点的 LCA 为 (x) 的数量，那么答案为
[sumlimits_{i=1}^{n}inom{u_i}{k}-inom{u_i-v_i}{k}
]
然后 (v) 是很容易维护的，(u) 树上差分一下就好了。
所以我们容易看出邪王真眼是最强的！！！
代码
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=3e5+51,MOD=1e9+7;
struct Edge{
ll to,prev;
};
Edge ed[MAXN<<1];
ll test,n,m,kk,tot,from,to,lca,res;
ll last[MAXN],u[MAXN],v[MAXN],depth[MAXN],anc[MAXN][20],fact[MAXN];
ll finv[MAXN],f[MAXN],diff[MAXN];
inline ll read()
{
register ll num=0,neg=1;
register char ch=getchar();
while(!isdigit(ch)&&ch!='-')
{
ch=getchar();
}
if(ch=='-')
{
neg=-1;
ch=getchar();
}
while(isdigit(ch))
{
num=(num<<3)+(num<<1)+(ch-'0');
ch=getchar();
}
return num*neg;
}
inline ll qpow(ll base,ll exponent)
{
ll res=1;
while(exponent)
{
if(exponent&1)
{
res=(li)res*base%MOD;
}
base=(li)base*base%MOD,exponent>>=1;
}
return res;
}
inline void setup(ll cnt)
{
fact[0]=fact[1]=finv[0]=1;
for(register int i=2;i<=cnt;i++)
{
fact[i]=(li)fact[i-1]*i%MOD;
}
finv[cnt]=qpow(fact[cnt],MOD-2);
for(register int i=cnt-1;i;i--)
{
finv[i]=(li)finv[i+1]*(i+1)%MOD;
}
}
inline ll binom(ll m,ll n)
{
return m<n?0:(li)fact[m]*finv[n]%MOD*finv[m-n]%MOD;
}
inline void addEdge(ll from,ll to)
{
ed[++tot].prev=last[from];
ed[tot].to=to;
last[from]=tot;
}
inline void dfs(ll node,ll fa)
{
depth[node]=depth[anc[node][0]=fa]+1;
for(register int i=last[node];i;i=ed[i].prev)
{
ed[i].to!=fa?dfs(ed[i].to,node):(void)1;
}
}
inline void LCASetup()
{
for(register int j=1;j<20;j++)
{
for(register int i=1;i<=n;i++)
{
anc[i][j]=anc[anc[i][j-1]][j-1];
}
}
}
inline ll LCA(ll x,ll y)
{
depth[x]<depth[y]?swap(x,y):(void)1;
for(register int i=19;i>=0;i--)
{
depth[anc[x][i]]>=depth[y]?x=anc[x][i]:1;
}
for(register int i=19;i>=0;i--)
{
anc[x][i]!=anc[y][i]?x=anc[x][i],y=anc[y][i]:1;
}
return x==y?x:anc[x][0];
}
inline void dfs2(ll node,ll fa)
{
ll to;
for(register int i=last[node];i;i=ed[i].prev)
{
(to=ed[i].to)!=fa?dfs2(to,node),diff[node]+=diff[to]:1;
}
}
inline void solve()
{
n=read(),m=read(),kk=read(),tot=0,memset(last,0,sizeof(last));
for(register int i=0;i<n-1;i++)
{
from=read(),to=read(),addEdge(from,to),addEdge(to,from);
}
dfs(1,0),LCASetup(),memset(f,0,sizeof(f)),memset(diff,0,sizeof(diff));
for(register int i=1;i<=m;i++)
{
u[i]=read(),v[i]=read(),f[lca=LCA(u[i],v[i])]++;
diff[u[i]]++,diff[v[i]]++,diff[lca]--,diff[anc[lca][0]]--;
}
dfs2(1,0),res=0;
for(register int i=1;i<=n;i++)
{
res=(res+(binom(diff[i],kk)-binom(diff[i]-f[i],kk)+MOD)%MOD)%MOD;
}
printf("%d
",res);
}
int main()
{
test=read(),setup(300010);
for(register int i=0;i<test;i++)
{
solve();
}
}