ZigZagK的博客
[树上解方程+组合数化简]2022牛客暑期多校训练营3 D【Directed】题解
2022年7月26日 00:32
牛客
查看标签

题目概述

Directed

解题报告

这题竟是脑子题……

显然这是个树上解方程的题目,设 $D_x$ 为 $x$ 的度数,$fa$ 为 $x$ 的父亲,$u$ 为 $x$ 儿子:

$$ f_{x}={1\over D_x}(f_{fa}+\sum_{u}f_u)+1 $$

类似随机游走,我们不难发现可设 $f_x=a_xf_{fa}+b_x$ ,则:

$$ (D_x-\sum_ua_u)f_x=f_{fa}+\sum_u b_u+D_x $$

由于 $a_u$ 出现在分母里,所以很不可维护,但是如果我们从叶子节点开始考虑,显然 $f_x=f_{fa}+1$ ,此时 $a_x=1$ ,考虑叶子节点的父亲 $fa$ ,则:

$$ (D_{fa}-\sum_{u}a_u)f_{fa}=f_{fafa}+\sum_{u}b_u+D_{fa}\\ (D_{fa}-\sum_{u}1)f_{fa}=f_{fafa}+\sum_{u}b_u+D_{fa}\\ f_{fa}=f_{fafa}+\sum_{u}b_u+D_{fa} $$

以此类推不难发现 $a_x$ 均为 $1$ ,我们只需要假设 $f_x=f_{fa}+b_x$ ,然后稍作分析,会发现 $b_x$ 其实就等于 $x$ 子树中所有节点度数的和,记为 $sum_x$ ,则 $f_{x}=f_{fa}+sum_x$ 。由于 $f_1=0$ ,也就是说 $f_x$ 其实就是 $x$ 到 $1$ 路径上所有 $sum$ 的和。

这样问题就变得容易分析了。当一条边 $x\to fa$ 改为单向边时,说明 $fa$ 往上不再统计 $x$ 子树里的度数,而 $x$ 子树中的不受影响。那么 $f_S$ 减少的值可以这么考虑:求出 $fa$ 和 $S$ 的 $LCA$ ,首先 $fa\to LCA$ 上不可以再选边,否则 $x\to fa$ 将影响不到 $S$ 。然后考虑 $LCA$ 往上走多少点遇到了另一条单向边,若点数为 $i$ 则 $f_S$ 减少的值为 $i\cdot (sum_{x}+1)$ 。特别的,$1$ 号点即使能走到也没有贡献。

枚举边 $x\to fa$ ,假设除掉 $x\to LCA$ 的边后剩下 $m$ 条边,$LCA$ 到 $1$ 路径上边的个数为 $d$ 。由于这条边改为单向的贡献恒为 $sum_x+1$ ,我们只需要考虑所有情况下 $i$ 的和。分为两种:$LCA$ 到 $1$ 路径上选了边(此时考虑最近的边),以及 $LCA$ 到 $1$ 路径上没有选边。第一种:$\sum_{i=1}^{d}i{m-i\choose K-2}$ ,第二种:$d{m-d\choose K-1}$ 。

如果我们直接枚举第一种情况复杂度肯定是不能接受的,因此我们考虑利用组合数公式简化式子:

$$ \sum_{i=0}^{n}{i\choose k}={n+1\choose k+1}\\ \begin{aligned} \sum_{i=1}^{d}i{m-i\choose K-2}&=\sum_{i=1}^{d}\sum_{j=i}^{d}{m-j\choose K-2}=\sum_{i=1}^{d}\sum_{j=m-d}^{m-i}{j\choose K-2}\\ &=\sum_{i=1}^{d}(\sum_{j=0}^{m-i}{j\choose K-2}-\sum_{j=0}^{m-d-1}{j\choose K-2})\\ &=\sum_{i=1}^{d}({m-i+1\choose K-1}-{m-d\choose K-1})\\ &=\sum_{i=m-d+1}^{m}{i\choose K-1}-d{m-d\choose K-1}\\ &=\sum_{i=0}^{m}{i\choose K-1}-\sum_{i=0}^{m-d}{i\choose K-1}-d{m-d\choose K-1}\\ &={m+1\choose K}-{m-d+1\choose K}-d{m-d\choose K-1} \end{aligned} $$

这样就可以快速计算了,令 $val={m+1\choose K}-{m-d+1\choose K}$ ,需要减去的值就是 $val(sum_x+1)$ 。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1000000,maxe=maxn<<1,LOG=20,MOD=998244353;

int n,K,S,D[maxn+5],sum[maxn+5],f[maxn+5];
int E,lnk[maxn+5],nxt[maxe+5],to[maxe+5];
int dep[maxn+5],ST[maxn+5][LOG+1];
int fac[maxn+5],INV[maxn+5],ans;

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
inline void Add(int x,int y) {to[++E]=y;nxt[E]=lnk[x];lnk[x]=E;}
void DFS(int x,int pre=0){
    dep[x]=dep[pre]+1;ST[x][0]=pre;sum[x]=D[x];
    for (int j=1;j<=LOG;j++) ST[x][j]=ST[ST[x][j-1]][j-1];
    for (int j=lnk[x];j;j=nxt[j])
        if (to[j]!=pre) DFS(to[j],x),sum[x]+=sum[to[j]];
}
inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
void DP(int x,int pre=0){
    for (int j=lnk[x];j;j=nxt[j])
        if (to[j]!=pre) f[to[j]]=ADD(f[x],sum[to[j]]),DP(to[j],x);
}
void Make(int n){
    INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=MUL(MOD-MOD/i,INV[MOD%i]);
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=MUL(fac[i-1],i),INV[i]=MUL(INV[i-1],INV[i]);
}
inline int C(int x,int y) {return x<y?0:MUL(fac[x],MUL(INV[y],INV[x-y]));}
int LCA(int x,int y){
    if (dep[x]<dep[y]) swap(x,y);
    for (int j=LOG;~j && dep[x]>dep[y];j--) if (dep[ST[x][j]]>=dep[y]) x=ST[x][j];
    if (x==y) return x;
    for (int j=LOG;~j;j--) if (ST[x][j]!=ST[y][j]) x=ST[x][j],y=ST[y][j];
    return ST[x][0];
}
int main(){
    readi(n);readi(K);readi(S);
    for (int i=1,x,y;i<n;i++)
        readi(x),readi(y),Add(x,y),Add(y,x),D[x]++,D[y]++;
    DFS(1);DP(1);Make(n);
    if (!K) {printf("%d\n",f[S]);return 0;}
    ans=MUL(f[S],C(n-1,K));
    for (int i=2;i<=n;i++){
        int lca=LCA(S,ST[i][0]),m=n-1-(dep[i]-dep[lca]),d=dep[lca]-1;
        int val=ADD(C(m+1,K),MOD-C(m-d+1,K));
        ans=ADD(ans,MOD-MUL(val,sum[i]+1));
    }
    ans=MUL(ans,MUL(MUL(fac[K],fac[n-1-K]),INV[n-1]));
    printf("%d\n",ans);
    return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!