Gym102012G Rikka with Intersections of Paths

题意

\(T\) 组数据，每组数据给定一棵 \(n\) 个点的树和 \(m\) 条路径，求选出 \(k\) 条给定路径使得至少有两条交于一点的方案数，对 \(10^9+7\) 取模。

\(\texttt{Data Range:}1\leq T\leq 200,1\leq n\leq 3\times 10^5,2\leq m\leq 3\times 10^5,2\leq k\leq m\)。

题解

这种题都不能一次 AC，而且还是犯的弱智错误，我太菜了。

考虑这样一个结论：如果两条路径交于一些点，那么这些点中的某一个肯定是这两条路径中一条的两个端点的 LCA。

我们枚举这样一个端点，然后容斥。设 \(u_x\) 为这些路径中经过 \(x\) 的数量，\(v_x\) 为这些路径中两个端点的 LCA 为 \(x\) 的数量，那么答案为

\[\sum\limits_{i=1}^{n}\binom{u_i}{k}-\binom{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\n",res);

}

int main()

{

    test=read(),setup(300010);

    for(register int i=0;i<test;i++)

    {

        solve();

    }

}

巴特西

Gym102012G Rikka with Intersections of Paths

题意

题解

代码

最新文章

热门文章