LRL52 的新博客

原博客地址：https://www.luogu.com.cn/blog/lrl/

0%

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

发表于

计数万古如长夜啊，大样例老是过不去啊

什么？数漏了，再开个数组把漏掉的加上就可以了

什么？又数重复了，再开个数组把重复的容斥掉即可

什么？转移速度太慢，再开一个数组记录前缀和就优化了

什么？函数名还有哪些啊，都用完了

恶心的树形\(\text{DP}\), 我使用了\(11\)个\(\text{DP}\)数组终于\(\text{AC}\)了

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

\[\text{f[x][i], g[x][i], F[x][i], G[x][i]}\]

\[\text{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\)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
//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;
}