题解 牛客网CSP-S集训4 路径计数机

发布于 2022-03-05  170 次阅读


计数万古如长夜啊,大样例老是过不去啊
什么?数漏了,再开个数组把漏掉的加上就可以了
什么?又数重复了,再开个数组把重复的容斥掉即可
什么?转移速度太慢,再开一个数组记录前缀和就优化了
什么?函数名还有哪些啊,都用完了
恶心的树形$\text{DP}$, 我使用了$11$个$\text{DP}$数组终于$\text{AC}$了

  • 用于各种转移的数组也就这些

$$f[x][i], g[x][i], F[x][i], G[x][i]$$

$$h[x][i], Sum[x][i], S[x], R[x], d[x][i],sum_p[x], sum_q[x]$$

  • 解释下含义

f[x][i]:从$x$出发向下走长度为$i$的链的个数

F[x][i]:从$x$出发长度为$i$的链的个数

g[x][i]:从$x$出发向上走长度为$i$的链的个数

G[x][i]:删除以$x$为根的子树,长度为$i$的链的个数$\times 2$(咳咳,这个和g[x][i]没有任何关系)

h[x][i]:从$x$的子树外,到$x$的子树内,长度为$i$的链的个数

d[x][i]:在$x$的子树内,经过$x$的长度为$i$的链的个数$\times 2$

Sum[x][i]:在$x$的子树内,F[][i]数组的和

S[i]:整棵树,F[][i]的数组的和

sum_p[x]:在$x$的子树内,d[][p]的和$\times \dfrac{1}{2}$

sum_q[x]:在$x$的子树内,d[][q]的和$\times \dfrac{1}{2}$

R[x]:在$x$的子树内,对于所有不相交的长度为$p$和长度为$q$的链,设这两条链的端点分别为$a, b$和$c, d$,满足$LCA(a, b, c, d) \notin {a, b, c, d}$,的对数

  • 转移:

$\color{Red}{\text{约定x表示任意树上节点,v是x的孩子}}$

$$f[x][0] = d[x][0] = 1$$

$$f[x][i] = \sum f[v][i - 1]$$

$$F[v][i] = f[v][i] + F[x][i - 1] - f[v][i - 2] [i \ge 2]$$

注意上面那个$[i \ge 2]$是艾弗森括号

$$g[v][i] = F[x][i - 1] - f[v][i - 2]$$

$$d[x][i] = f[v][j - 1] \times f[x][i - j], j \in [1, i - 1], d[x][i] += f[x][i], d[x][i] *= 2$$

注意,上柿子的前半部分是在每次$f$数组更新前更新,后半部分是遍历子节点结束后进行

$$Sum[x][i] = \sum Sum[v][i] + F[x][i]$$

$$S[i] = \sum F[x][i]$$

$$h[x][i] = \sum g[x][j] \times f[x][i - j], j \in [1, i]$$

$$G[x][i] = S[i] - Sum[x][i] - h[x][i]$$

$$sum_p[x] = \sum sum_p[v] + d[x][p] \times \dfrac{1}{2}$$

$$sum_q[x] = \sum sum_q[v] + d[x][q] \times \dfrac{1}{2} $$

$$R[x] = \sum R[v] + sum_p[x] \times sum_q[v] + sum_q[x] \times sum_p[v]$$

注意,柿子后面的都是在每次$sum_p[x]$和$sum_q[x]$更新前更新

最后激动人心的$Ans = \sum d[x][p] \times G[x][q] + \sum d[x][q] \times G[x][p] - R[1] \times 4$

完结撒花ヾ(✿゚▽゚)ノ

//ID: LRL52  Date: 2019.11.5
//计数万古如长夜啊
//恶心的树形DP, 我使用了11个DP数组终于AC了 
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define ee(i, a) for(int i = head[a]; i; i = e[i].nxt)
#include<bits/stdc++.h>
using namespace std;
const int N = 3055, M = 2055; char ss[1 << 21], *A = ss, *B = ss, cc;
inline char gc(){return A == B && (B = (A = ss) + fread(ss, 1, 1 << 21, stdin), A == B) ? EOF : *A++;}
template<class T>inline void rd(T &x){
    int f = 1; x = 0, cc = gc(); while(cc < '0' || cc > '9'){if(cc == '-') f = -1; cc = gc();}
    while(cc >= '0' && cc <= '9'){x = x * 10 + (cc ^ 48); cc = gc();} x *= f;
}
#define int long long
int n, ct, P, Q, K;
int head[N], f[N][N], d[N][N], Sum[N][N], S[N], G[N][N], F[N][N], h[N][N], g[N][N];
int R[N], sum_p[N], sum_q[N];
struct edge{
    int v, nxt;
}e[N << 1];

inline void adde(int from, int to){
    e[++ct] = (edge){to, head[from]};
    head[from] = ct;
}

void dfs(int x, int far){
    f[x][0] = d[x][0] = 1;
    ee(I, x){
        int v = e[I].v;
        if(v == far) continue;
        dfs(v, x);
        for(int i = 1; i <= K; ++i){
            for(int j = 1; j < i; ++j){
                d[x][i] += f[v][j - 1] * f[x][i - j];
            }
        }
        for(int i = 1; i <= K; ++i)
            f[x][i] += f[v][i - 1];
    }
    for(int i = 1; i <= K; ++i){
        d[x][i] += f[x][i];
        d[x][i] *= 2;
    }
}

void dfs2(int x, int far){
    ee(I, x){
        int v = e[I].v;
        if(v == far) continue;
        F[v][0] = 1;
        for(int i = 1; i <= K; ++i){
            F[v][i] = f[v][i] + F[x][i - 1];
            g[v][i] = F[x][i - 1];
            if(i >= 2){
                F[v][i] -= f[v][i - 2];
                g[v][i] -= f[v][i - 2];
            }
        }
        dfs2(v, x);
    }
}

void dfs3(int x, int far){
    for(int i = 0; i <= K; ++i) Sum[x][i] = F[x][i];
    for(int i = 1; i <= K; ++i){
        for(int j = 1; j <= i; ++j){
            h[x][i] += g[x][j] * f[x][i - j];
        }
    }
    ee(I, x){
        int v = e[I].v;
        if(v == far) continue;
        dfs3(v, x);
        R[x] += R[v];
        R[x] += sum_p[x] * sum_q[v] + sum_q[x] * sum_p[v];
        sum_p[x] += sum_p[v];
        sum_q[x] += sum_q[v];
        for(int i = 0; i <= K; ++i)
            Sum[x][i] += Sum[v][i];
    }
    sum_p[x] += d[x][P] / 2;
    sum_q[x] += d[x][Q] / 2;
    for(int i = 0; i <= K; ++i)
        G[x][i] = S[i] - Sum[x][i] - h[x][i];
}

#undef int
int main(){
#ifdef LRL52
    freopen("b.in", "r", stdin);
#endif
    //freopen("T2.out", "w", stdout);
#define int long long
    rd(n), rd(P), rd(Q); int x, y;
    K = max(P, Q);
    rep(i, 1, n - 1){
        rd(x), rd(y);
        adde(x, y), adde(y, x);
    }
    dfs(1, -1);
    for(int i = 0; i <= K; ++i) F[1][i] = f[1][i];
    dfs2(1, -1);
    for(int i = 0; i <= K; ++i){
        for(int j = 1; j <= n; ++j){
            S[i] += F[j][i];
        }
    }
    dfs3(1, -1);
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        ans += d[i][P] * G[i][Q];
        ans += d[i][Q] * G[i][P];
    }
    ans -= R[1] * 4;
    printf("%lld\n", ans);
    //printf("%.3lf M\n", (double)(&cur2 - &cur1) / (1 << 20));
    return 0;
}

昨日的月光悄然退场,曦阳已经渐亮