树形DP

简介

树形DP是所有DP中较为简单的一种，因为树形DP的状态一定是每个节点若干状态，所以很容易根据点数猜出每个点的状态个数，进一步猜出状态的表示。

常见技巧

在比较古老的书上有一种把多叉树转成二叉树的方法，左孩子右兄弟，用以解决一类状态合并中只能两个点合并的题目，不过目前来看这种方法用处不大。

第一类经典的题目如 P1273，看起来有O(n2)O(n^2)个状态，转移是O(n)O(n)但是总复杂度O(n2)O(n^2)。

第二类经典的题目如 P4827，组合数的递推（有22项）比次幂的递推（有k+1k+1项）简单很多，可以将转移的时间复杂度从O(k)O(k)优化到O(1)O(1)。

第三类经典的题目如 P2634，每条路径在LCA的位置被统计到，特点是每个点的状态数必须非常有限，比如如果是统计路径长度小于等于kk或者是路径长度为质数的，都是用点分治比较好。

参考题目

Codechef BLACKCOM
对于每个大小，求出最多的黑色点的个数，和最少黑色点的个数。

f[i][j] 表示 子树i 选j个节点，最多几个黑色的
子树i有很多个孩子，比如有 a b
f[i][j + k] = max(f[i][j + k], f[a][j] + f[b][k])
在点i消耗的时间，等于 子树a大小 乘以 子树b的大小，（等于有多少对点以i为LCA）

P2634 [国家集训队]聪聪可可

https://www.luogu.com.cn/problem/P2634

题目描述

聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。

他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画 nn 个“点”，并用 n−1n-1 条“边”把这 nn 个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是 33 的倍数，则判聪聪赢，否则可可赢。

聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

输入格式

输入的第 11 行包含 11 个正整数 nn。后面 n−1n-1 行，每行 33 个整数 x,y,wx,y,w，表示 xx 号点和 yy 号点之间有一条边，上面的数是 ww。

输出格式

以即约分数形式输出这个概率（即 a/b 的形式，其中 aa 和 bb 必须互质。如果概率为 11，输出 1/1）。

样例 #1

样例输入 #1
5
1 2 1
1 3 2
1 4 1
2 5 3
样例输出 #1
13/25

提示

【样例说明】

1313 组点对分别是(1,1)(1,1)，(2,2)(2,2)，(2,3)(2,3)，(2,5)(2,5)，(3,2)(3,2)，(3,3)(3,3)，(3,4)(3,4)，(3,5)(3,5)，(4,3)(4,3)，(4,4)(4,4)，(5,2)(5,2)，(5,3)(5,3)，(5,5)(5,5)。

【数据规模】

对于 100%100\% 的数据，n≤2×104n\leq 2 \times 10^4。

参考代码

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > a[20020]; 
int f[20020][3];
int n, up, down;
void dfs(int x, int y) {
	f[x][0] = 1;
	for (int i = 0; i < a[x].size(); i++) {
		if (a[x][i].first != y) {
			dfs(a[x][i].first, x);
			for (int j = 0; j < 3; j++) {
				up += f[x][j] * f[a[x][i].first][(6 - j - a[x][i].second) % 3];
			}
			for (int j = 0; j < 3; j++) {
				f[x][(j + a[x][i].second) % 3] += f[a[x][i].first][j];
			}
		}
	}
}
int gcd(int x, int y) {
	return y ? gcd(y, x % y) : x;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		a[x].push_back(make_pair(y, z % 3));
		a[y].push_back(make_pair(x, z % 3));
	}
 	dfs(1, 0);
	up = up * 2 + n;
	down = n * n;
	int g = gcd(up, down);
	up /= g;
	down /= g;
	printf("%d/%d\n", up, down);
	return 0 ;
}

题解

聪聪可可
这个题目有一个O(nk)O(nk)的动态规划的做法，即每条路径在LCA的位置被统计到。
网上许多题解是用点分治做的，但是这个题并不需要点分治。

P1352 没有上司的舞会

https://www.luogu.com.cn/problem/P1352

题目描述

某大学有 nn 个职员，编号为 1…n1\ldots n。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 rir_i，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入格式

输入的第一行是一个整数 nn。

第 22 到第 (n+1)(n + 1) 行，每行一个整数，第 (i+1)(i+1) 行的整数表示 ii 号职员的快乐指数 rir_i。

第 (n+2)(n + 2) 到第 2n2n 行，每行输入一对整数 l,kl, k，代表 kk 是 ll 的直接上司。

输出格式

输出一行一个整数代表最大的快乐指数。

样例 #1

样例输入 #1
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
样例输出 #1
5

提示

数据规模与约定

对于 100%100\% 的数据，保证 1≤n≤6×1031\leq n \leq 6 \times 10^3，−128≤ri≤127-128 \leq r_i\leq 127，1≤l,k≤n1 \leq l, k \leq n，且给出的关系一定是一棵树。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a[6020];
int w[6020];
int f[6020];
int g[6020];
void dfs(int x, int y) {
	f[x] = 0;
	g[x] = w[x];
	for (int i = 0; i < a[x].size(); i++) {
		if (a[x][i] != y) {
			dfs(a[x][i], x);
			f[x] += max(f[a[x][i]], g[a[x][i]]);
			g[x] += f[a[x][i]];
		}
	}
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
	}
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		a[y].push_back(x);
		a[x].push_back(y);
	}
	dfs(1, 0);
	cout << max(f[1], g[1]) << endl;
	return 0;
}

题解

f[x] 不选 x， x 子树的最大值是多少
g[x] 选 x， x 子树的最大值是多少

P1122 最大子树和

https://www.luogu.com.cn/problem/P1122

题目描述

小明对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿时想到了一个有关修剪花卉的问题。于是当日课后，小明就向老师提出了这个问题：

一株奇怪的花卉，上面共连有NN朵花，共有N−1N-1条枝干将花儿连在一起，并且未修剪时每朵花都不是孤立的。每朵花都有一个“美丽指数”，该数越大说明这朵花越漂亮，也有“美丽指数”为负数的，说明这朵花看着都让人恶心。所谓“修剪”，意为：去掉其中的一条枝条，这样一株花就成了两株，扔掉其中一株。经过一系列“修剪“之后，还剩下最后一株花（也可能是一朵）。老师的任务就是：通过一系列“修剪”（也可以什么“修剪”都不进行），使剩下的那株（那朵）花卉上所有花朵的“美丽指数”之和最大。

老师想了一会儿，给出了正解。小明见问题被轻易攻破，相当不爽，于是又拿来问你。

输入格式

第一行一个整数N(1≤N≤16000)N(1 ≤ N ≤ 16000)。表示原始的那株花卉上共NN朵花。

第二行有NN个整数，第II个整数表示第II朵花的美丽指数。

接下来N−1N-1行每行两个整数a,ba,b，表示存在一条连接第aa 朵花和第bb朵花的枝条。

输出格式

一个数，表示一系列“修剪”之后所能得到的“美丽指数”之和的最大值。保证绝对值不超过21474836472147483647。

样例 #1

样例输入 #1
7
-1 -1 -1 1 1 1 0
1 4
2 5
3 6
4 7
5 7
6 7
样例输出 #1
3

提示

【数据规模与约定】

对于60%60\%的数据，有N≤1000N≤1000；

对于100%100\%的数据，有N≤16000N≤16000。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, ans;
vector<int> a[16020];
int w[16020];
int f[16020];
void dfs(int x, int y) {
	f[x] = w[x];
	for (int i = 0; i < a[x].size(); i++) {
		if (a[x][i] != y) {
			dfs(a[x][i], x);
			f[x] += max(f[a[x][i]], 0);
		}
	}
	ans = max(ans, f[x]);
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
	}
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		a[y].push_back(x);
		a[x].push_back(y);
	}
	ans = w[1];
	dfs(1, 0);
	cout << ans << endl;
	return 0;
}

题解

f[x] 表示选择第 x 个点，在 x 子树中最大权值和是多少

P4084 [USACO17DEC]Barn Painting G

https://www.luogu.com.cn/problem/P4084

题目描述

Farmer John has a large farm with NN barns (1≤N≤1051 \le N \le 10^5), some of which are already painted and some not yet painted. Farmer John wants to paint these remaining barns so that all the barns are painted, but he only has three paint colors available. Moreover, his prize cow Bessie becomes confused if two barns that are directly reachable from one another are the same color, so he wants to make sure this situation does not happen.

It is guaranteed that the connections between the NN barns do not form any 'cycles'. That is, between any two barns, there is at most one sequence of connections that will lead from one to the other.

How many ways can Farmer John paint the remaining yet-uncolored barns?

输入格式

The first line contains two integers NN and KK (0≤K≤N0 \le K \le N), respectively the number of barns on the farm and the number of barns that have already been painted.

The next N−1N-1 lines each contain two integers xx and yy (1≤x,y≤N,x≠y1 \le x, y \le N, x \neq y) describing a path directly connecting barns xx and yy.

The next KK lines each contain two integers bb and cc (1≤b≤N1 \le b \le N, 1≤c≤31 \le c \le 3) indicating that barn bb is painted with color cc.

输出格式

Compute the number of valid ways to paint the remaining barns, modulo 109+710^9 + 7, such that no two barns which are directly connected are the same color.

样例 #1

样例输入 #1
4 1
1 2
1 3
1 4
4 3
样例输出 #1
8

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int n, m, x, y;
vector<int> a[100020];
long long f[100020][3];
void dfs(int x, int y)
{
	for (int i: a[x])
	{
		if (i != y)
		{
			dfs(i, x);
			f[x][0] = f[x][0] * (f[i][1] + f[i][2]) % mod;
			f[x][1] = f[x][1] * (f[i][2] + f[i][0]) % mod;
			f[x][2] = f[x][2] * (f[i][0] + f[i][1]) % mod;
		}
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	fill(f[0], f[n + 1], 1);
	for (int i = 1; i < n; i++)
	{
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &x, &y);
		f[x][y % 3] = 0;
		f[x][y - 1] = 0;
	}
	dfs(1, 0);
	printf("%lld\n", (f[1][0] + f[1][1] + f[1][2]) % mod);
	return 0;
}

题解

P4084 [USACO17DEC]Barn Painting G
树上简单动态规划
f[x][0/1/2] 表示第x个点染0/1/2颜色，x子树中有多少个方案

P1273 有线电视网

https://www.luogu.com.cn/problem/P1273

题目描述

某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。

从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。

现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。

写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。

输入格式

输入文件的第一行包含两个用空格隔开的整数 NN 和 MM，其中 2≤N≤30002 \le N \le 3000，1≤M≤N−11 \le M \le N-1，NN 为整个有线电视网的结点总数，MM 为用户终端的数量。

第一个转播站即树的根结点编号为 11，其他的转播站编号为 22 到 N−MN-M，用户终端编号为 N−M+1N-M+1 到 NN。

接下来的 N−MN-M 行每行表示—个转播站的数据，第 i+1i+1 行表示第 ii 个转播站的数据，其格式如下：

K  A1  C1  A2  C2  …  Ak  CkK \ \ A_1 \ \ C_1 \ \ A_2 \ \ C_2 \ \ \ldots \ \ A_k \ \ C_k

KK 表示该转播站下接 KK 个结点（转播站或用户），每个结点对应一对整数 AA 与 CC ，AA 表示结点编号，CC 表示从当前转播站传输信号到结点 AA 的费用。最后一行依次表示所有用户为观看比赛而准备支付的钱数。单次传输成本和用户愿意交的费用均不超过 10。

输出格式

输出文件仅一行，包含一个整数，表示上述问题所要求的最大用户数。

样例 #1

样例输入 #1
5 3
2 2 2 5 3
2 3 2 4 3
3 4 2
样例输出 #1
2

提示

样例解释

如图所示，共有五个结点。结点 ① 为根结点，即现场直播站，② 为一个中转站，③④⑤ 为用户端，共 MM 个，编号从 N−M+1N-M+1 到 NN，他们为观看比赛分别准备的钱数为 33、44、22。

从结点 ① 可以传送信号到结点 ②，费用为 22；

也可以传送信号到结点 ⑤，费用为 33（第二行数据所示）；

从结点 ② 可以传输信号到结点 ③，费用为22；

也可传输信号到结点 ④，费用为 33（第三行数据所示）。

如果要让所有用户（③④⑤）都能看上比赛，则信号传输的总费用为：2+3+2+3=102+3+2+3=10，大于用户愿意支付的总费用 3+4+2=93+4+2=9，有线电视网就亏本了，而只让 ③④ 两个用户看比赛就不亏本了。

参考代码

#include <bits/stdc++.h>
using namespace std;
int f[3020][3020];
vector<int> a[3020];
int v[3020];
int w[3020];
int n, m, l, x, y;
int dfs(int x)
{
	f[x][0] = 0;
	if (x > n - m)
	{
		f[x][1] = v[x];
		return 1;
	}
	int s = 0;
	for (int i: a[x])
	{
		int t = dfs(i);
		for (int j = s; j >= 0; j--)
		{
			for (int k = t; k > 0; k--)
			{
				f[x][j + k] = max(f[x][j + k], f[x][j] + w[i] + f[i][k]);
			}
		}
		s += t;
	}
	return s;
}
int main()
{
	scanf("%d%d", &n, &m);
	memset(f, 0xc0, sizeof f);
	for (int i = 1; i <= n - m; i++)
	{
		scanf("%d", &l);
		for (int j = 0; j < l; j++)
		{
			scanf("%d%d", &x, &y);
			a[i].push_back(x);
			w[x] = -y;
		}
	}
	for (int i = n - m + 1; i <= n; i++)
	{
		scanf("%d", &v[i]);
	}
	dfs(1);
	for (int i = m; i > 0; i--)
	{
		if (f[1][i] >= 0)
		{
			printf("%d\n", i);
			break;
		}
	}
	return 0;
}

题解

树上背包
f[i][j] i子树花j的钱，最多满足多少人
f[i][j] i子树满足j个人，最多赚多少钱（负数表示最小亏多少）
在第i个点消耗了多少时间：有多少对点以i为LCA
所以总时间不会超过 点对 个数

f[i][j]
i 子树中选 j 个节点

P1552 [APIO2012]派遣

https://www.luogu.com.cn/problem/P1552

题目背景

在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。

题目描述

在这个帮派里，有一名忍者被称之为 Master。除了 Master 以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。

现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者支付一定的薪水，同时使得支付的薪水总额不超过你的预算。另外，为了发送指令，你需要选择一名忍者作为管理者，要求这个管理者可以向所有被派遣的忍者发送指令，在发送指令时，任何忍者（不管是否被派遣）都可以作为消息的传递人。管理者自己可以被派遣，也可以不被派遣。当然，如果管理者没有被排遣，你就不需要支付管理者的薪水。

你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平，其中每个忍者的领导力水平也是一定的。

写一个程序，给定每一个忍者 ii 的上级 BiB_i，薪水 CiC_i，领导力 LiL_i，以及支付给忍者们的薪水总预算 MM，输出在预算内满足上述要求时顾客满意度的最大值。

输入格式

第一行包含两个整数 NN 和 MM，其中 NN 表示忍者的个数，MM表示薪水的总预算。

接下来 NN 行描述忍者们的上级、薪水以及领导力。其中的第i行包含三个整数 Bi,Ci,LiB_i,C_i,L_i 分别表示第 ii 个忍者的上级，薪水以及领导力。Master 满足 Bi=0B_i=0，并且每一个忍者的老板的编号一定小于自己的编号 Bi<iB_i\lt i。

输出格式

一行一个整数，表示在预算内顾客的满意度的最大值。

样例 #1

样例输入 #1
5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1
样例输出 #1
6

提示

1≤N≤1051 \le N \le 10^5，1≤M≤1091 \le M \le 10^9，0≤Bi<i0 \le B_i \lt i，1≤Ci≤M1 \le C_i \le M，1≤Li≤1091 \le L_i \le 10^9。

对于 30%30\% 的数据，N≤3000N \le 3000。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
long long ans;
int f[100020];
long long s[100020];
long long l[100020];
priority_queue<int> q[100020];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d%lld%lld", &f[i], &s[i], &l[i]);
		q[i].push(s[i]);
	}
	for (int i = n; i > 0; i--)
	{
		while (s[i] > m)
		{
			s[i] -= q[i].top();
			q[i].pop();
		}
		ans = max(ans, (long long)q[i].size() * l[i]);
		s[f[i]] += s[i];
		if (q[f[i]].size() < q[i].size())
		{
			q[f[i]].swap(q[i]);
		}
		while (q[i].size())
		{
			q[f[i]].push(q[i].top());
			q[i].pop();
		}
	}
	printf("%lld\n", ans);
	return 0;
}

题解

启发式合并

问区间第 k 小是谁？
问数字 x 是第几小？
问最小的 k 个和是多少？
问选择和不超过 s 最多选择几个数字？

P4383 [八省联考 2018] 林克卡特树

https://www.luogu.com.cn/problem/P4383

题目描述

小 L 最近沉迷于塞尔达传说：荒野之息（The Legend of Zelda: Breath of The Wild）无法自拔，他尤其喜欢游戏中的迷你挑战。

游戏中有一个叫做 LCT 的挑战，它的规则是这样子的：现在有一个 NN 个点的树，每条边有一个整数边权 viv_i，若 vi≥0v_i \geq 0，表示走这条边会获得 viv_i 的收益；若 vi<0v_i \lt 0 ，则表示走这条边需要支付 −vi-v_i 的过路费。小 L 需要控制主角 Link 切掉（Cut）树上的恰好 KK 条边，然后再连接 KK 条边权为 0 的边，得到一棵新的树。接着，他会选择树上的两个点 p,qp,q，并沿着树上连接这两点的简单路径从 pp 走到 qq，并为经过的每条边支付过路费/ 获取相应收益。

海拉鲁大陆之神 TemporaryDO 想考验一下 Link。他告诉 Link，如果 Link 能切掉合适的边、选择合适的路径从而使 总收益 - 总过路费 最大化的话，就把传说中的大师之剑送给他。

小 L 想得到大师之剑，于是他找到了你来帮忙，请你告诉他，Link 能得到的 总收益 - 总过路费 最大是多少。

输入格式

输入第一行包含两个正整数 N,KN,K。

接下来 N−1N - 1 行，每行包含三个整数 xi,yi,vix_i,y_i,v_i，表示第 ii 条边连接图中的 xi,yix_i, y_i 两点，它的边权为 viv_i。

输出格式

输出一行一个整数，表示答案。

样例 #1

样例输入 #1
5 1
1 2 3
2 3 5
2 4 -3
4 5 6
样例输出 #1
14

提示

样例解释

一种可能的最优方案为：切掉 (2,4,−3)(2, 4, -3) 这条边，连接 (3,4,0)(3, 4, 0) 这条边，选择 (p,q)=(1,5)(p, q) = (1, 5)。

数据范围

对于全部的测试数据，保证 1≤N≤3×1051 \leq N \leq 3 \times 10^5，0≤K≤3×1050 \leq K \leq 3 \times 10^5，K<NK \lt N，1≤xi,yi≤N1 \leq x_i,y_i \leq N，∣vi∣≤106|v_i| \leq 10^6。

提示

题目并不难。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, k, M;
vector<pair<int, int> > a[300020];
typedef long long ll;
struct D {
	ll x, y;
	D(ll x = 0, ll y = 0): x(x), y(y) {
	}
}f[300020][3];
D operator+(const D &a, const D &b) {
	return D(a.x + b.x, a.y + b.y);
}
D operator+(const D &a, int x) {
	return D(a.x + x, a.y);
}
bool operator<(const D &a, const D &b) {
	if (a.x != b.x) {
		return a.x < b.x;
	}
	return a.y > b.y;
}
D dec(D a) {
	return D(a.x + M, a.y + 1);
}
void dfs(int x, int y) {
	f[x][0] = D(0, 0);
	f[x][1] = D(0, 0);
	f[x][2] = D(0, 0);
	for (pair<int, int> i: a[x]) {
		if (i.first == y) {
			continue;
		}
		dfs(i.first, x);
		f[x][2] = max(f[x][2] + f[i.first][2], dec(f[x][1] + f[i.first][1] + i.second));
		f[x][1] = max(f[x][1] + f[i.first][2], f[x][0] + f[i.first][1] + i.second);
		f[x][0] = f[x][0] + f[i.first][0];
	}
	f[x][2] = max(f[x][2], f[x][0]);
	f[x][2] = max(f[x][2], dec(f[x][1]));
}
int main() {
	scanf("%d%d", &n, &k);
	k++;
	for (int i = 1; i < n; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		a[x].push_back(make_pair(y, z));
		a[y].push_back(make_pair(x, z));
	}
	int R = 1000001, L = -R;
	while (L < R - 1) {
		M = (L + R) / 2;
		dfs(1, 0);
		if (f[1][2].y > k) {
			R = M;
		} else {
			L = M;
		}
	}
	M = L;
	dfs(1, 0);
	printf("%lld\n", f[1][2].x - k * M);
	return 0;
}

题解

wqs二分（凸优化）
选择k+1条路径
把他们接在一起
每一条路径可以是单独一个点
路径和路径之间不能有公共点

原本要求k+1个
现在不要求个数
但是每选一个路径会获得M的额外收益（M可能是负数）
问最大收益，求最大收益的同时，需要求解选择了几个路径。

P6142 [USACO20FEB]Delegation P

https://www.luogu.com.cn/problem/P6142

题目描述

Farmer John 有 NN 个牧场，这些牧场通过 N−1N-1 条道路连接，形成了一个树形结构。

但在 28 年的经营后（译者注：USACO 创办于 1992 年），FJ 觉得处理树上问题非常辣手，他认为一条链上的问题更加简单。

因此他决定将整棵树划分为若干条链，将每一条链的管理权授予一位工人。他不关心链的数量，却关心链的长度，他希望划分的链都尽可能长，从而不会有人用效率低下的算法蒙混过关。

FJ 现在想知道最大的正整数 KK，使得整棵树被划分成若干条链，且每条链的长度都至少是 KK。

输入格式

第一行一个整数 NN（1≤N≤1051 \leq N \leq 10^5）。

接下来 NN 行，每行两个整数 u,vu,v（1≤u,v≤N1 \leq u,v \leq N），描述一条连接 u,vu,v 的道路。

输出格式

输出 KK。

样例 #1

样例输入 #1
8
1 2
1 3
1 4
4 5
1 6
6 7
7 8
样例输出 #1
3

提示

样例解释

一种划分方案如下：

2−1−6−7−8,3−1−4−52-1-6-7-8, 3-1-4-5

子任务

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, x, y, z, M, flag;
vector<int> a[100020];

int dfs(int x, int y) {
	multiset<int> b;
	for (int i = 0; i < a[x].size(); i++) {
		if (a[x][i] != y) {
			int l = dfs(a[x][i], x);
			b.insert(l + 1);
			if (!flag)
			{
				return 0;
			}
		}
	}
	int only = 0;
	while (b.size() > 1)
	{
		int u = *b.begin();
		b.erase(b.begin());
		if (u < M)
		{
			multiset<int>::iterator it = b.lower_bound(M - u);
			if (it == b.end())
			{
				if (only == 0)
				{
					only = u;
					continue;
				}
				flag = false;
				return 0;
			}
			if (b.size() == 1 && *it >= M)
			{
				return *b.begin();
			}
			b.erase(it);
		}
	}
	if (b.size() == 0)
	{
		return only;
	}
	else
	{
		if (only > 0)
		{
			flag = false;
			return 0;
		}
		return *b.begin();
	}
}
bool ok() {
	flag = true;
	int res = dfs(1, 0);
	return flag && (res >= M || res == 0);
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	int L = 1, R = n;
	while (L < R - 1) {
		M = (L + R) / 2;
		if (ok()) {
			L = M;
		} else {
			R = M;
		}
	}
	printf("%d\n", L);
	return 0;
}

题解

二分，每个点用 set 匹配，有非常多的特殊情况。

DFS，每个点只考虑孩子，希望把孩子尽可能的匹配
剩下一条最长的链传给父亲节点
每一个点有一个集合，要求把集合中的数字配对，使得每对和都>=M

有一个列表
希望删去其中一个数字
使得剩下的数字配对之后>=M
问删去的数字最大是多少？

例子
M=10
[2, 3, 7] 应该 3 和 7 匹配，返回 2
[5, 10] 是否应该匹配呢？如果是根节点，5和10匹配返回0，如果不是根节点，10自己满足条件，返回5

int dfs(int x, int y) {
multiset b;
for (int i = 0; i < a[x].size(); i++) {
if (a[x][i] != y) {
int l = dfs(a[x][i], x);
b.insert(l + 1);
if (!flag)
{
return 0;
}
}
}
int only = 0;
while (b.size() > 1)
{
int u = *b.begin(); 找到集合中最小的数字
b.erase(b.begin()); 删去最小的数字
if (u < M)
{
multiset::iterator it = b.lower_bound(M - u); 问集合中哪个数字和u匹配后可以>=M 选最小的匹配后>=M
if (it == b.end()) 如果这样的数字不存在
{
if (only == 0) 那么可能会剩下他
{
only = u; // 剩下他
continue;
}
flag = false; // 如果剩下了2个无法匹配的数字，那就无解
return 0;
}
if (b.size() == 1 && *it >= M) // 如果剩下1个 <M 剩下1个 >=M 的 情况比较复杂，返回哪个都不对
{
return *b.begin();
}
b.erase(it); // 删去和 u 匹配的数字
}
}
if (b.size() == 0) // 如果最后集合空了，返回可能存在的only
{
return only;
}
else // 如果还剩下一个
{
if (only > 0) // only 也有，剩下2个，无解
{
flag = false;
return 0;
}
return *b.begin(); // 返回剩下的一个
}
}
bool ok() {
flag = true;
int res = dfs(1, 0);
return flag && (res >= M || res == 0);
}

P6147 [USACO20FEB] Delegation G

https://www.luogu.com.cn/problem/P6147

题目描述

Farmer John 有 NN 个牧场，这些牧场通过 N−1N-1 条道路连接，形成了一个树形结构。

但在 28 年的经营后（译者注：USACO 创办于 1992 年），FJ 觉得处理树上问题非常辣手，他认为一条链上的问题更加简单。

因此他决定将整棵树划分为若干条链，将每一条链的管理权授予一位工人。为了避免可能的争端，他希望所有链的长度均相同。

FJ 现在想知道，对于每一个满足 1≤K≤N−11 \leq K \leq N-1 的 KK，是否存在一种划分方案，使得整棵树被划分成若干条链，且每条链的长度都恰好是 KK。

输入格式

第一行一个整数 NN（1≤N≤1051 \leq N \leq 10^5）。

接下来 N−1N-1 行，每行两个整数 u,vu,v（1≤u,v≤N1 \leq u,v \leq N），描述一条连接 u,vu,v 的道路。

输出格式

输出一个长度 N−1N-1 的 0/1 串。第 ii 位的值为 11 当且仅当存在一种划分方案，使得整棵树被划分成若干条链，且每条链的长度都恰好是 ii，否则第 ii 位的值为 00。

样例 #1

样例输入 #1
13
1 2
2 3
2 4
4 5
2 6
6 7
6 8
8 9
9 10
8 11
11 12
12 13
样例输出 #1
111000000000

提示

样例解释

K=1,2,3K=1,2,3 时都存在一种合法的划分方案。

K=3K=3 时的一种划分方案如下：

13−12−11−8,10−9−8−6,7−6−2−3,5−4−2−113-12-11-8, 10-9-8-6, 7-6-2-3, 5-4-2-1

子任务

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int s[100020];
int c[100020], cc;
vector<int> a[100020];
vector<int> b[100020];
void dfs(int x, int y)
{
	s[x] = 1;
	for (int i: a[x])
	{
		if (i != y)
		{
			dfs(i, x);
			b[x].push_back(s[i]);
			s[x] += s[i];
		}
	}
	b[x].push_back(n - s[x]);
}
int ok(int l)
{
	if ((n - 1) % l != 0)
	{
		return 0;
	}
	for (int i = 1; i <= n; i++)
	{
		cc = 0;
		for (int j: b[i])
		{
			j %= l;
			if (j > 0)
			{
				c[cc++] = j;
			}
		}
		sort(c, c + cc);
		if (cc % 2 > 0)
		{
			return false;
		}
		for (int i = 0; i < cc; i++)
		{
			if (c[i] + c[cc - 1 - i] != l)
			{
				return false;
			}
		}
	}
	return true;
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i < n; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	dfs(1, 0);
	for (int i = 1; i < n; i++)
	{
		printf("%d", ok(i));
	}
	printf("\n");
	return 0;
}

题解

每个点自己做匹配

P4827 [国家集训队] Crash 的文明世界

https://www.luogu.com.cn/problem/P4827

题目描述

Crash 小朋友最近迷上了一款游戏——文明5 (Civilization V)。在这个游戏中，玩家可以建立和发展自己的国家，通过外交和别的国家交流，或是通过战争征服别的国家。

现在 Crash 已经拥有了一个 nn 个城市的国家，这些城市之间通过道路相连。由于建设道路是有花费的，因此 Crash 只修建了 n−1n-1 条道路连接这些城市，不过可以保证任意两个城市都有路径相通。

在游戏中，Crash 需要选择一个城市作为他的国家的首都，选择首都需要考虑很多指标，有一个指标是这样的：

S(i)=∑j=1ndist(i,j)kS(i) = \sum_{j = 1}^{n}{\rm dist}(i, j) ^ k

其中 S(i)S(i) 表示第 ii 个城市的指标值，dist(i,j){\rm dist}(i, j) 表示第 ii 个城市到第 jj 个城市需要经过的道路条数的最小值，kk 为一个常数且为正整数。

因此 Crash 交给你一个简单的任务：给出城市之间的道路，对于每个城市，输出这个城市的指标值，由于指标值可能会很大，所以你只需要输出这个数  mod  10007\bmod\ 10007 的值。

输入格式

输入的第一行包括两个正整数 nn 和 kk。

接下来有 n−1n-1 行，每行两个正整数 u,vu, v（1≤u,v≤n1\le u, v\le n），表示第 uu 个城市和第 vv 个城市之间有道路相连。这些道路保证能符合题目的要求。

输出格式

输出共 nn 行，每行一个正整数，第 ii 行的正整数表示第 ii 个城市的指标值  mod  10007\bmod\ 10007 的值。

样例 #1

样例输入 #1
5 2
1 2
1 3
2 4
2 5
样例输出 #1
10
7
23
18
18

提示

对于 20%20 \% 的数据，n≤5000n\le 5000，k≤30k\le 30。

对于 50%50 \% 的数据，n≤5×104n\le 5\times 10^4，k≤30k\le 30。

对于 100%100 \% 的数据，1≤n≤5×1041\le n\le 5\times 10^4，1≤k≤1501\le k\le 150。

参考代码

题解

根据题目可以感觉到至少O(nk)O(nk)个状态。
通过次幂和组合数的关系，将维护x0,x1,…,xkx^0, x^1, \ldots, x^k，
转化为维护(x0),(x1),…,(xk)\binom{x}{0}, \binom{x}{1}, \ldots, \binom{x}{k}。
斯特灵数

P5203 [USACO19JAN]Exercise Route P

https://www.luogu.com.cn/problem/P5203

题目背景

USACO 19年一月月赛铂金组第二题。

题目描述

奶牛 Bessie 意识到为了保持好的体形她需要更多地进行锻炼。她需要你帮助她选择在农场里每天用来晨跑的路线。 农场由 nn 块草地组成，方便起见编号为 1∼n1\sim n，由 mm 条双向的小路连接。作为一种遵循规律的生物，奶牛们倾向于使用其中特定的 n−1n-1 条小路作为她们日常在草地之间移动的路线——她们管这些叫“常规的”小路。从每块草地出发都可以仅通过常规的小路到达所有其他草地。

为了使她的晨跑更加有趣，Bessie 觉得她应该选择一条包含一些非常规的小路的路线。然而，使用常规的小路能够使她感到舒适，所以她不是很想在她的路线中使用过多非常规的小路。经过一些思考，她认为一条好的路线应当形成一个简单环（能够不经过任何草地超过一次的情况下回到起点），其中包含恰好两条非常规的小路。

请帮助 Bessie 计算她可以使用的好的路线的数量。两条路线被认为是相同的，如果它们包含的小路的集合相等。

输入格式

输入的第一行包含 nn 和 mm。以下 mm 行每行包含两个整数 aia_i 和 bib_i，描述了一条小路的两端。其中前 (n−1)(n-1) 条是常规的小路。

输出格式

输出一行一个整数表示 Bessie 可以选择的路线的总数。

样例 #1

样例输入 #1
5 8
1 2
1 3
1 4
1 5
2 3
3 4
4 5
5 2
样例输出 #1
4

提示

数据规模与约定

对于全部的测试点，保证 1≤n≤2×1051 \leq n \leq 2 \times 10^5，1≤m≤2×1051 \leq m \leq 2 \times 10^5，m≥n−1m \geq n - 1，1≤ai,bi≤n1 \leq a_i, b_i \leq n。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> a[200020];
int f[200020][18]; // father
int d[200020]; //depth
long long b[200020]; // 有多少条路径过自己父亲这条边
long long r[200020]; // 当前点有多少个lca
long long c[200020]; // 子树内有多少个lca
long long e[200020]; // 有多少个路径，以x的父亲节点为lca
long long ans;
map<pair<int, int>, int> g[200020];
void dfs(int x, int y) {
	f[x][0] = y;
	d[x] = d[y] + 1;
	for (int i = 1; i < 18; i++) {
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
	for (int i: a[x]) {
		if (i != y) {
			dfs(i, x);
		}
	}
}

void dfs2(int x, int y) {
	long long u = c[x];
	r[x] = c[x];
	long long s1 = 0;
	long long s2 = 0;
	for (int i: a[x]) {
		if (i != y) {
			dfs2(i, x);
			c[x] += c[i];
			b[x] += b[i];
			s1 += c[i];
			s2 += c[i] * c[i];
			ans -= (b[i] - e[i]) * (b[i] - e[i] - 1) / 2;
		}
	}
	ans -= u * (m - c[x] - b[x]);
// 有一些会被减两次
	ans += (s1 * s1 - s2) / 2;
// 加回来


	ans -= (b[x] + r[x]) * (b[x] + r[x] - 1) / 2;
//  cerr << (b[x] + r[x]) * (b[x] + r[x] - 1) / 2 << endl;
// 减去交集为0的对数（过点x的）

	ans += (b[x]) * (b[x] - 1) / 2 * 2;
//  cerr << (b[x]) * (b[x] - 1) / 2 << endl;
// 加上交集为1的对数（过点x父亲那条边的）

// 减去交集为2的，LCA是当前点。
	for (pair<pair<int, int>, int> i: g[x]) {
		ans -= (long long)i.second * (i.second - 1) / 2;
//      cerr << (long long)i.second * (i.second - 1) / 2 << endl;
	}
// 接下来需要考虑的路径就是自己孩子到自己父亲节点这种路径了
// 简单来说这就是b[i] ?但是有一些路径以自己结束啊，再开一个数组吧。
}

int lca(int x, int y) {
	if (d[x] < d[y]) {
		swap(x, y);
	}
	int dd = d[x] - d[y];
	for (int i = 0; i < 18; i++) {
		if (dd >> i & 1) {
			x = f[x][i];
		}
	}
	if (x == y) {
		return x;
	}
	for (int i = 17; i >= 0; i--) {
		if (f[x][i] != f[y][i]) {
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}

/*
对于每个点，每条路径是一个大小为2的集合
问有多少对集合没有交集
交集为0的对数 - 交集为1的对数 + 交集为2的对数
*/

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	dfs(1, 0);
	m -= n - 1;
	for (int i = 0; i < m; i++) {
		int x, y, nx, ny;
		scanf("%d%d", &x, &y);
		nx = x;
		ny = y;
		int l = lca(x, y);
		b[x]++;
		b[y]++;
		b[l] -= 2;
		c[l]++;
		for (int i = 17; i >= 0; i--) {
			if (d[f[nx][i]] > d[l]) {
				nx = f[nx][i];
			}
			if (d[f[ny][i]] > d[l]) {
				ny = f[ny][i];
			}
		}
		if (nx > ny) {
			swap(nx, ny);
		}
		if (nx != l) {
			e[nx]++;
		}
		if (ny != l) {
			e[ny]++;
		}
		if (nx != l && ny != l) {
			g[l][make_pair(nx, ny)]++;
		}
	}
	ans = (long long)m * (m - 1) / 2;
/*
全部 m*(m-1)/2
减去 不想交的
*/
	dfs2(1, 0);
/*
到这里，答案应该是点相交的无序对数量
还需要减去，只相交在点上的，也就是 -(交集为0的对数 - 交集为1的对数 + 交集为2的对数)
*/
	printf("%lld\n", ans);
	return 0;
}

题解

树上有多少对路径边相交

P5243 [USACO19FEB]Moorio Kart P

https://www.luogu.com.cn/problem/P5243

题目描述

Bessie 和 Farmer John 喜欢山羊卡丁车比赛。这个比赛非常类似于其他人喜欢的卡丁车比赛，除了卡丁车是由山羊拉动，以及赛道是由农田组成。农田由 NN 个草地和 MM 条道路组成，每条道路都连接着两个草地。

定义农场是两个或更多草地的一个集合，同一农场中的每个草地都可以沿着一系列唯一的道路到达农场中其他任意一个草地。

整个农田可能由多个农场组成，假设图中有 KK 个农场。Bessie 希望通过添加长度为 XX 的 KK 条道路，连接所有 KK 个农场来制作山羊卡丁车赛道。每个农场只应访问一次，并且每个农场内必须至少穿过一条道路。

为了让选手们对赛道更有兴趣，赛道的长度至少应该为 YY 。Bessie 希望知道所有这些有趣赛道的赛道长度总和。如果一个赛道中有两个农场直接相连，但另外一个赛道中这两个农场没有直接相连的话，这两个赛道就是不同的。

输入格式

第一行包括四个整数 N,M,X,YN,M,X,Y（1≤N≤1500,1≤M≤N−1,0≤X,Y≤25001 \leq N \leq 1500,1 \leq M \leq N-1,0 \leq X, Y \leq 2500）。

接下来 MM 行，每行包含三个整数： Ai,Bi,DiA_i,B_i,D_i（1≤Ai,Bi≤N,0≤Di≤25001 \leq A_i, B_i \leq N,0 \leq D_i \leq 2500），代表 AiA_i 号草地和 BiB_i 号草地间有一条长度为 DiD_i 的道路。保证两个草地间最多只有一条道路直接相连，且不存在自环。

输出格式

输出有趣赛道的赛道长度总和 (mod109+7)\pmod {10^9+7} 后的结果。

样例 #1

样例输入 #1
5 3 1 12
1 2 3
2 3 4
4 5 6
样例输出 #1
54

提示

有 6 个合法的赛道方案：

其中后 4 条赛道满足了赛道总长不低于 12 的条件，这几条赛道的长度总和为 54。

子任务：对于 70%70\% 的数据， N,Y≤1000N,Y \leq 1000 。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
vector<pair<int, int> > a[2520];
long long ans = 0;
long long cnt = 1;
long long sum;
int sz;
bool v[2520];
long long inv[2520];
long long f[2520];
long long g[2520];
int n, m, x, y;
int dfs(int x, int y) {
	v[x] = true;
	int re = 1;
	for (pair<int, int> i: a[x]) {
		if (i.first != y) {
			int tmp = dfs(i.first, x);
			re += tmp;
			sum += (long long)i.second * tmp * (sz - tmp);
		}
	}
	return re;
}
map<int, int> c;
map<int, int> gao(int x, int y) {
	v[x] = true;
	map<int, int> re;
	re[0] = 1;
	for (pair<int, int> i: a[x]) {
		if (i.first != y) {
			map<int, int> tmp = gao(i.first, x);
			for (pair<int, int> j: re) {
				for (pair<int, int> k: tmp) {
					c[j.first + i.second + k.first] += j.second * k.second * 2;
				}
			}
			for (pair<int, int> k: tmp) {
				re[i.second + k.first] += k.second;
			}
		}
	}
	return re;
}
int main() {
	cin >> n >> m >> x >> y;
	inv[1] = 1;
	for (int i = 2; i <= n; i++) {
		inv[i] = inv[mod % i] * (mod - mod / i) % mod;
	}
	if ((n - m) * x <= y) {
		f[(n - m) * x] = 1;
	}

	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		a[x].push_back(make_pair(y, z));
		a[y].push_back(make_pair(x, z));
	}

	memset(v, 0, sizeof v);
	for (int i = 1; i <= n; i++) {
		if (!v[i]) {
			sz = dfs(i, 0);
			cnt = cnt * sz % mod * (sz - 1) % mod;
		}
	}

	memset(v, 0, sizeof v);
	for (int i = 1; i <= n; i++) {
		if (!v[i]) {
			sz = dfs(i, 0);
			sum = 0;
			dfs(i, 0);
			ans = (ans + cnt * inv[sz] % mod * inv[sz-1] % mod * sum % mod) % mod;
		}
	}

	ans *= 2;

	ans = (ans + cnt * (n - m) * x) % mod;

	memset(v, 0, sizeof v);
	for (int i = 1; i <= n; i++) {
		if (!v[i]) {
			c.clear();
			gao(i, 0);
			memset(g, 0, sizeof g);
			for (pair<int, int> i: c) {
				for (int j = i.first; j <= y; j++) {
					g[j] = (g[j] + f[j - i.first] * i.second) % mod;
				}
			}
			swap(f, g);
		}
	}

	for (int i = 0; i < y; i++) {
		ans = (ans - (long long)i * f[i] % mod + mod) % mod;
	}

	for (int i = 1; i < n - m; i++) {
		ans = ans * i % mod;
	}

	if (ans & 1) {
		ans += mod;
	}
	ans /= 2;
	cout << ans << endl;
	return 0;
}

题解

简单背包

P5853 [USACO19DEC]Tree Depth P

https://www.luogu.com.cn/problem/P5853

题目背景

For the new year, Farmer John decided to give his cows a festive binary search tree
(BST)!

To generate the BST, FJ starts with a permutation a={a1,a2,…,aN}a=\{a_1,a_2,\ldots,a_N\}
of the integers 1…N1\ldots N, where N≤300N\le 300. He then runs the following
pseudocode with arguments 11 and N.N.

generate(l,r):
  if l > r, return empty subtree;
  x = argmin_{l <= i <= r} a_i; // index of min a_i in {a_l,...,a_r}
  return a BST with x as the root, 
    generate(l,x-1) as the left subtree,
    generate(x+1,r) as the right subtree;

For example, the permutation {3,2,5,1,4}\{3,2,5,1,4\} generates the following BST:

    4
   / \
  2   5
 / \ 
1   3

Let di(a)d_i(a) denote the depth of node ii in the tree corresponding to a,a,
meaning the number of nodes on the path from aia_i to the root. In the above
example, d4(a)=1,d2(a)=d5(a)=2,d_4(a)=1, d_2(a)=d_5(a)=2, and d1(a)=d3(a)=3.d_1(a)=d_3(a)=3.

The number of inversions of aa is equal to the number of pairs of integers
(i,j)(i,j) such that 1≤i<j≤N1\le i<j\le N and ai>aj.a_i>a_j. The cows know that the aa that
FJ will use to generate the BST has exactly KK inversions
(0≤K≤N(N−1)2)(0\le K\le \frac{N(N-1)}{2}). Over all aa satisfying this condition, compute
the remainder when ∑adi(a)\sum_ad_i(a) is divided by MM for each 1≤i≤N.1\le i\le N.

题目描述

为了迎接新年，Farmer John 决定给他的奶牛们一个节日二叉搜索树！

为了生成这个二叉搜索树，Farmer John 从一个 1…N1 \dots N 的排列 a={1,2,…,N}a= \{1,2, \dots ,N\} 开始，然后以参数 ll 和 rr 开始运行如下的伪代码：

generate(l,r):
  if l > r, return empty subtree;
  x = argmin_{l <= i <= r} a_i; // index of min a_i in {a_l,...,a_r}
  return a BST with x as the root, 
    generate(l,x-1) as the left subtree,
    generate(x+1,r) as the right subtree;

例如，排列 {3,2,5,1,4}\{ 3,2,5,1,4 \} 将产生如下的二叉搜索树：

令 di(a)d_i(a) 表示节点 ii 在用排列 aa 生成的二叉搜索树中的深度。深度定义为这个节点到根节点的路径上的点数。在上述例子中，d4(a)=1,d2(a)=d5(a)=2,d1(a)=d3(a)=3d_4(a)=1,d_2(a)=d_5(a)=2,d_1(a)=d_3(a)=3。

aa 中的逆序对数等于满足 1≤i<j≤N1 \le i<j \le N 且 ai>aja_i>a_j 的数对 (i,j)(i,j) 的个数。奶牛们知道 Farmer John 用来生成二叉搜索树的排列 aa 中恰好有 KK 个逆序对。对于所有满足条件的 aa，请计算对于每个 1≤i≤N1 \le i \le N，∑adi(a)\sum_a d_i(a) 对 MM 取模后的结果。

输入格式

输入只有一行，包含三个整数 N,K,MN,K,M。

输出格式

输出一行 NN 个整数，第 ii 个整数表示 ∑adi(a) mod M\sum_a d_i(a) \bmod M。两个整数之间用一个空格隔开。

样例 #1

样例输入 #1
3 0 192603497
样例输出 #1
1 2 3

样例 #2

样例输入 #2
3 1 144408983
样例输出 #2
3 4 4

提示

样例解释 1

对于这个样例，唯一满足条件的排列为 a={1,2,3}a=\{1,2,3\}。

样例解释 2

对于这个样例，满足条件的两个排列分别为 a={1,3,2}a=\{1,3,2\} 和 a={2,1,3}a=\{2,1,3\}。

数据范围

对于全部数据，1≤N≤3001\le N\le 300，0≤K≤N(N−1)20\le K\le \frac{N(N-1)}{2}，保证 MM 是一个 [108,109+9]\left[ 10^8,10^9+9 \right] 范围中的质数。

对于测试点 3,43,4，满足 N≤8N \le 8；

对于测试点 5−75-7，满足 N≤20N \le 20；

对于测试点 8−108-10，满足 N≤50N \le 50。

USACO 2019 December 铂金组T3

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, l, mod;
int a[45000] = {1};
int z[300];
void mul(int b)
{
	for (int i = 1; i < l; i++)
	{
		a[i] = (a[i] + a[i - 1]) % mod;
	}
	for (int i = l - 1; i >= b; i--)
	{
		a[i] = (a[i] + mod - a[i - b]) % mod;
	}
}
void div(int b)
{
	for (int i = b; i < l; i++)
	{
		a[i] = (a[i] + a[i - b]) % mod;
	}
	for (int i = l - 1; i > 0; i--)
	{
		a[i] = (a[i] + mod - a[i - 1]) % mod;
	}
}
int main()
{
	cin >> n >> m >> mod;
	l = n * (n - 1) / 2;
	for (int i = 1; i <= n; i++)
	{
		mul(i);
	}
	for (int j = 1; j < n; j++)
	{
		div(j + 1);
		for (int i = 0; i < n - j; i++)
		{
			z[i] = (z[i] + a[n * (n - 1) / 2 - m]) % mod;
			z[i + j] = (z[i + j] + a[m]) % mod;
		}
		mul(j + 1);
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d%c", (z[i] + a[m]) % mod, i == n - 1 ? '\n' : ' ');
	}
	return 0;
}

题解

笛卡尔树

P6008 [USACO20JAN]Cave Paintings P

https://www.luogu.com.cn/problem/P6008

题目描述

Bessie 成为了一名艺术家，正在创作壁画！她现在正在创作的作品是一个高为 NN 的方阵，方阵的每行都由 MM 个方格组成（1≤N,M≤10001\le N,M\le 1000）。每个方格是空的，画了石头，或者画了水。Bessie 已经画上了包含石头的方格，包括整幅画作的边界。她现在想要将某些空的方格画上水，使得如果这幅画是真实的，其中应当不存在水的净移动。定义从上到下第 ii 行的方格的高度为 N+1−iN+1-i。Bessie 想要她的画作满足以下限制：

假设方格 aa 画的是水。那么如果存在一条从 aa 到方格 bb 的路径，由高度不超过 aa 的空的方格或是有水的方格组成，路径中每相邻两个方格都有一条公共边，那么 bb 画的也是水。

求 Bessie 可以创作的不同作品的数量模 109+710^9+7 的余数。Bessie 可以将任意数量的空格画上水，包括不画以及全画。

输入格式

输入的第一行包含两个空格分隔的整数 NN 和 MM。

以下 NN 行每行包含 MM 个字符。每个字符均为 . 或 #，分别表示一个空的方格和一个画有石头的方格。第一行和最后一行、第一列和最后一列仅包含 #。

输出格式

输出一个整数，为满足限制的作品的数量模 109+710^9+7 的余数。

样例 #1

样例输入 #1
4 9
#########
#...#...#
#.#...#.#
#########
样例输出 #1
9

提示

样例解释

如果第二行中的任意一个方格被画上水，那么所有空的方格必须都被画上水。否则，假设没有这样的方格画有水。那么 Bessie 可以选择画上第三行的空格组成的三个连续区域的任意子集。所以，画作的总数等于 1+23=91+2^3=9。

子任务

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
char s[1020][1020];
vector<int> a[1000020];
int cnt;
const int mod = 1000000007;
int f[1000020];
int c[1000020];
int v[1000020];
int F(int x)
{
	return f[x] != x ? f[x] = F(f[x]) : x;
}
void U(int x, int y)
{
	x = F(x);
	y = F(y);
	if (x > y)
	{
		f[x] = y;
	}
	else
	{
		f[y] = x;
	}
}
int G(int x)
{
	int re = 1;
	for (int i : a[x])
	{
		re = (long long)re * G(i) % mod;
	}
	return (re + 1) % mod;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		scanf("%s", s[i]);
	}
	for (int i = 0; i < n * m; i++)
	{
		f[i] = i;
	}
	for (int i = n - 1; i >= 0; i--)
	{
		for (int j = 0; j < m; j++)
		{
			if (s[i][j] == '.' && s[i + 1][j] == '.')
			{
				U(i * m + j, (i + 1) * m + j);
			}
		}
		for (int j = 1; j < m; j++)
		{
			if (s[i][j - 1] == '.' && s[i][j] == '.')
			{
				U(i * m + j - 1, i * m + j);
			}
		}
		for (int j = 0; j < m; j++)
		{
			if (s[i][j] == '.')
			{
				if (F(i * m + j) == i * m + j)
				{
					c[i * m + j] = ++cnt;
				}
				else
				{
					c[i * m + j] = c[F(i * m + j)];
				}
			}
		}
		for (int j = 0; j < m; j++)
		{
			if (s[i][j] == '.' && s[i + 1][j] == '.')
			{
				a[c[i * m + j]].push_back(c[(i + 1) * m + j]);
				v[c[(i + 1) * m + j]] = 1;
			}
		}
	}
	for (int i = 1; i <= cnt; i++)
	{
		sort(a[i].begin(), a[i].end());
		a[i].resize(unique(a[i].begin(), a[i].end()) - a[i].begin());
	}
	int ans = 1;
	for (int i = 1; i <= cnt; i++)
	{
		if (v[i] == 0)
		{
			ans = (long long)ans * G(i) % mod;
		}
	}
	printf("%d\n", ans);
	return 0;
}

题解

树上dp，计数

P2796 Facer的程序

https://www.luogu.com.cn/problem/P2796

题目描述

Facer是一个萌萌哒的码农

他写了N个程序

程序之间是有 有机的联系的

任意两个程序恰好由1条联系链连在一起

具体来说，对于程序a,b ， 存在且仅存在一个序列a,x1,x2....xn,b

使得a,x1有联系,x1,x2有联系.....

符合这样的一组程序称为程序块

现在已知一个程序块的程序之间的联系

询问它有多少个子程序块

即取出一个程序子集S，使得S也满足上述条件

输入格式

第一行N

接下来N-1行，每行两个数，代表有联系的两个程序

输出格式

输出有多少个子程序块

对1000000007取模

样例 #1

样例输入 #1
3
1 2
2 3
样例输出 #1
6

提示

样例解释：

子集(1),(2),(3),(1,2),(2,3),(1,2,3)满足

对于 10%的数据 1 <= N <= 20

对于 40%的数据 1 <= N <= 500

对于 100%的数据 1 <= N <= 100000

参考代码

#include <bits/stdc++.h>
using namespace std;
const int p = 1000000007;
int n, x, y, z;
vector<int> a[100020];
int F(int x, int y)
{
	long long re = 1;
	for (int i: a[x])
	{
		if (i != y)
		{
			re = re * F(i, x) % p;
		}
	}
	z = (z + re) % p;
	return re + 1;
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i < n; i++)
	{
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	F(1, 0);
	printf("%d\n", z);
	return 0;
}

题解

f[x] 表示选择第 x 个点，只考虑 x 子树中的点，方案数是多少
f[x] = 枚举所有孩子i (f[i]+1)的连乘积

SP1435 PT07X - Vertex Cover
树上 最小点覆盖

SP666 VOCV - Con-Junctions
树上 最小点覆盖方案数

SP1480 PT07D - Let us count 1 2 3
树的计数

AT2293 [AGC009D] Uninity

CF1101D 树上找链GCD最大

  1. 树形DP
    1. 简介
    2. 常见技巧
    3. 参考题目
      1. P2634 [国家集训队]聪聪可可
      2. P1352 没有上司的舞会
      3. P1122 最大子树和
      4. P4084 [USACO17DEC]Barn Painting G
      5. P1273 有线电视网
      6. P1552 [APIO2012]派遣
      7. P4383 [八省联考 2018] 林克卡特树
      8. P6142 [USACO20FEB]Delegation P
      9. P6147 [USACO20FEB] Delegation G
      10. P4827 [国家集训队] Crash 的文明世界
      11. P5203 [USACO19JAN]Exercise Route P
      12. P5243 [USACO19FEB]Moorio Kart P
      13. P5853 [USACO19DEC]Tree Depth P
      14. P6008 [USACO20JAN]Cave Paintings P
      15. P2796 Facer的程序
≡