LRL52 的新博客

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

0%

发表于

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

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

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

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

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

恶心的树形\(\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;
}

发表于

发表于

My New Blog has successfully created by LRL52 at 19:42 9/15/2021

发表于

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment