杜老师毒瘤题

A. 划分

考虑dp,$f_{i,j,k}$表示考虑了i的子树,然后选取了j个连通块,当前还剩下的权值和为k的最小划分和是什么,注意我们钦定还剩下,所以连通块数量最多为n-1,因为还有至少一个点i的信息不确定

显然这样状态转移是对于第三维和值域拿出来构成一个二元组$(x,y)$,假设和二元组$(u,v)$合并,那么我们总有

新二元组$(u+x,y+v)$,或者$(x,u^2+y+v)$,第二个合并的意思是我们选择毙掉二元组u当前的连通块,使得连通块数增加

再考虑这个有一个显然的性质,就是$(u,v)$如果存在一个完全的二维偏序对,就是$(x,y)$两维都小于他,这个对就没用了

然后对于这个问题我们可以考虑维护所有合法的二元组,显然他们构成了一个凸包

但是这样的点对还是太多了

不难发现,如果我们钦定$(u,v)$为一个定值,那么这个转移就相当于$(x,x^2+y)$点乘上$(2u,1)$的最小值

那么我们只需要保留$(x,x^2+y)$凸壳上的递减部分即可

维护这个凸壳其实我们是需要维护每一维度的最小值的...

就是说,我们每次转移的时候按照两种方式转移,就是放入对应第二维的vector中

然后我们发现转移完之后可以直接模拟,按照这个$x^2+y$的信息排序,单调递增,然后之后查询的时候直接暴力使用最后一个即可,所以就做完了

维护这样$x^2+y$的最小值,是需要我们对于每个x维护$x^2+y$的最小值的...注意此时不是严格按照斜率的凸包,我们是保证x递增y递减的一个结构而已

那么你会

首先,像这样转移的信息之和最后一维(或者某一维)有关的最优化转移,是可以写成这样凸壳的形式的

更具体的,其实像三维dp,我们都可以写成一个凸壳相交的形式,只和第三维有关

计数也有对于高维的很好的处理方法,我们转移一定是关于某一维的多项式(其他维都确定),而这样的多项式如果次数不太多,则可以对于每一次项求出前缀和,然后直接相加即可

等等,我们好像还是没有证明,这样的决策点不会很多个qaq

根据打表可以知道,这样的数量其实是$O(h)$的QAQ

至于他的正确性,官方题解也没有很好的解释,只是告诉我们再随机数据下表现优异而已

然后可以看看谷歌生草机的翻译

该解决方案的总体框架与[ELE]任务中的框架相同（我在另一个线程中介绍了该解决方案）。

我们剪下更多的叶子。每个节点都包含一个项目列表，这些项目汇总了要剪切的整个子树中的数据。

在每个项目中，三个属性对我们很重要：闭合部分的数量，闭合部分的平方值总和，未闭合部分的值总和。不同之处在于每个顶点必须聚合项目，可能来自许多不同的截止片段-这就是为什么在切割下一个节点时，我们会生成项目的笛卡尔积：来自截止顶点及其邻居（可能已聚合）其他截止部分的项目）-这会导致项目列表的大小呈指数增长。
当然，每对这样的项目都可以通过两种方式连接：关闭一个开放的片段或将其与另一个顶点连接。

随着项目列表的快速增长，我们在每个步骤之后都会清除列表中次于其他项目的项目列表。事实证明，有许多此类项目要删除，这是随机数据的结果。因此，整个过程非常快。复杂度为O（n * n * X），因为对于每个'n'个节点，我们至少存储了'n'个项目（针对不同数量的区域），而公式中的X表示对于每个数字在许多领域，我们可以拥有许多无与伦比的项目，但是，对于随机测试而言，恰恰是这个X相对较小。

#include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

#define st first
#define nd second
#define PLL pair <LL, LL>

const int N = 307;

int n, mx;
int sz[N];
int vals[N];
vector <int> G[N];

vector <PLL> tmp[N];
vector <PLL> dp[N][N];

void read() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &vals[i]);

	for(int i = 1; i < n; ++i) {
		int u, v;
		scanf("%d %d", &u, &v);

		G[u].push_back(v);
		G[v].push_back(u);
	}
}

vector <PLL> parse(vector <PLL> &in) {
	sort(in.begin(), in.end());
	vector <PLL> result;
	for(auto q : in) {
		auto s = q.first;
		auto v = q.second;
		if(result.size() == 0)
			result.push_back({s, v});
		else {
			auto q = result.back();
			auto s2 = q.first;
			auto v2 = q.second;
			if(s2 * s2 + v2 > s * s + v)
				result.push_back({s, v});
		}
	}

	return result;
}

void push(vector <PLL> &to_push, const vector <PLL> &Left, const vector <PLL> &Right) {
	for(const auto &q : Left)
		for(const auto &p : Right)
			to_push.push_back({q.first + p.first, q.second + p.second});
}

void merge(int &fa, int &fb) {
	for(int i = 0; i < sz[fa] + sz[fb]; ++i)
		tmp[i].clear();

	for(int ca = 0; ca < sz[fa]; ++ca) {
		for(int cb = 0; cb < sz[fb]; ++cb) {
			push(tmp[ca + cb], dp[fa][ca], dp[fb][cb]);
			auto q = dp[fb][cb].back();
			auto ts = q.first;
			auto tv = q.second;
			for(auto g : dp[fa][ca])
				tmp[ca + cb + 1].push_back({g.first, g.second + tv + ts * ts});
		}
	}

	sz[fa] += sz[fb];
	for(int i = 0; i < sz[fa]; ++i) {
		dp[fa][i] = parse(tmp[i]);
		// mx = max(mx, (int)dp[fa][i].size());
		// printf("%d %d %d?\n", fa, i, dp[fa][i].size());
		//这个O(\sqrt n)
	}
}

void go(int u, int p) {
	sz[u] = 1;
	dp[u][0] = {{vals[u], 0}};
	for(auto v : G[u])
		if(v != p) {
			go(v, u);
			merge(u, v);
		}
}

void solve() {
	go(1, 0);
}

void write() {
	for(int i = 0; i < n; ++i) {
		auto q = dp[1][i].back();
		printf("%lld%c", q.first * q.first + q.second, " \n"[i + 1 == n]);
	}
}

void clear() {
	for(int i = 1; i <= n; ++i) {
		for(int j = 0; j < sz[i]; ++j)
			dp[i][j].clear();
		sz[i] = 0;
		G[i].clear();
	}
}

int main() {
	int tests;
	scanf("%d", &tests);

	while(tests--) {
		read();
		solve();
		write();
		clear();
	}

	return 0;
}

B. 随机游走

考虑计算每条边的概率生成函数,每一项就是从u走到w要经过x次的概率,其中w是父亲,然后这个生成函数用$f_u$

然后答案就是考虑这些生成函数乘起来然后维护一个二阶一阶导即可

因为$E(x^2)=E(x^2-x+x)=E(x(x-1))+E(x)$

不难发现这个$E(x)$是一阶导数,就是$i*p_i$,显然就是期望的直接形式

然后我们考虑怎么搞这个东西的转移

$df_u=x+xf_u(\sum_{v \in son_u}f_v)$

就是走一遍就过去显然就是x吧,然后走多遍过去,对应着我们$f_u$和$f_w$卷积呢

因为我们任意一项,就都等价于我们走到下面v,然后再在下面v雇佣雇佣,然后雇佣会u,再从u走上去,其中至少是要两步的,所以我们乘上x,表示第一步走到v的代价

紧接着对这个式子数学解决一下

$df_u'=1+\sum_{v!=w} f_uf_v+f_uf_v'x+f_u'f_vx$

概率生成函数允许我们把x=1带入吧,于是带入

注意此时有恒等式$f_u(1)=1$

$df_u'=1+(d-1)+f_u'(d-1)+\sum f_v'$

$f_u'=1+(d-1)+\sum f_v'$

我们这个是可以直接转移的...

在对于原式求二阶导

注意求导的时候我们只需要对于谁求导就好了,具体一个n项乘式求$k$阶导就是一个$(a+b+c...)^k$

这个群内有解释

$df_u''=\sum_v(f_u''f_v+f_uf_v''+2f'_uf_v+2f_uf_v'+2xf_u'f_v')$

这个式子显然有$df_u''=(f_u''+2f_u')(d-1)+\sum_v(f_v''+2f_v'+2f_u'f_v')$

$f_u''=2f_u'(d-1)+\sum_v(f_v''+2f_v'+2f_u'f_v')$

然后这个可以直接做的,就是递推

处理出这个dp值后,我们再处理从父亲走到儿子的一些dp值

这个也挺难处理的,就是直接从高到低做即可qwq,然后推式子时候分裂出父亲一项变成独特的形式

原始形式

$dg_v=1+xg_v\sum f_p+g_Fg_vx$

$g_v'=d+\sum_{p\in son_u,u is fa_v,p != v}f_p'+g'_u$

然后我们就有

$g_v''=2g_v'(d-1)+\sum_v (f_v''+2f_v'+2f_u'g_v') + g_u''+2g_u'+2g_u'g_v'$

然后怎么求询问的答案啊

首先所有u子树所有点要走到子树根处,这个很好做,是一个子树求和

然后考虑这些被算另一侧子树大小次

然后这些再从这个边走到另一个边,倍增即可

求出这个和,会被算sz*sz次

然后右边再走到每个点处,也可以预处理,就是从上到下嘛...也会被算另一侧子树大小次

就做完了,时间复杂度为$O(nlogn)$

C. 动态筛

min-25筛的特性就是对于素数幂的值能快速得到就能很快筛出答案

然而本题要支持一个单点修改,如果每次都筛这个答案,显然会TLE

所以要考虑分块筛?不太懂