[cogs2652]秘术「天文密葬法」（01分数规划，长链剖分（继承时每个深度需要假设 val[u] 的处理））

题目大意：给你一棵树，每个点有两个权值$a_i,b_i$ai​,bi​，你需要找出一条长为m的路径（指路径上点的个数为 m 个），最小化$\frac{\sum a_i}{\sum b_i}$∑bi​∑ai​​。

题解：
这个式子以及题意就是01分数规划的形式。

前缀技能：01分数规划
01分数规划对应有一些元素，你需要从中选出 $k$k 个，使得$\displaystyle\frac{\sum a_i}{\sum b_i}$∑bi​∑ai​​最小或最大。

对于$\displaystyle\frac{\sum a_i}{\sum b_i}$∑bi​∑ai​​最小的情况：

01分数规划的做法是 构造一个函数 $f(x) = \sum a_i - x* \sum b_i$f(x)=∑ai​−x∗∑bi​

若 $f(x) \leq 0$f(x)≤0，移项一下可得：$\frac{\sum a_i}{\sum b_i} \leq x$∑bi​∑ai​​≤x，$x$x 正是这个式子的解。

二分 x，$f(x) = \sum(a_i - x * b_i)$f(x)=∑(ai​−x∗bi​)，每次贪心的选前最小的 $k$k 个，根据 $f(x)$f(x) 与 0 的相对大小缩小区间。

---

对这题，二分 $x$x，然后找一条长为 $m - 1$m−1权值和最小 的路径(一般长度是指路径边的数量，点的数量m相当于边数量为 m - 1)，根据权值和与0的大小关系缩小值域范围。

求路径可以用 dp,dp[u][i] 表示以 u 为根节点，往下走深度为 i 的路径的最小权值和，复杂度为 $O(n^2)$O(n2)，总复杂度为$O(n^2 \log n)$O(n2logn)。

也可以用点分，复杂度为 $O(n \log^2 n)$O(nlog2n)

如果用长链剖分优化树形 $dp$dp，继承重儿子后，每个深度的值都需要加上 $a[u] - mid * b[u]$a[u]−mid∗b[u]，为了保证复杂度，显然不能对每个深度都加上 这个值来维护一个正确的值。

一个做法是，用一个变量记录需要加上的值，使得 $dp[u][i] + val[u]$dp[u][i]+val[u] 得到正确的值。初始时 $val[u] = a[u] - mid * b[u]$val[u]=a[u]−mid∗b[u]，继承重儿子时，val[u] += val[son[u]]。

对于更新答案：ans = min(ans,dp[v][i] + val[v] + dp[u][m - i - 1] + val[u])
对于 dp 转移： dp[u][i + 1] = min(dp[u][i + 1]，dp[v][i] + val[v] + a[u] - mid * b[u] - val[u])

(减掉val[u] 是为了构造使得 dp[u][i] + val[u] 得到正确值)
复杂度就降至$O(n \log n)$O(nlogn)
(没有题目交不了，代码不一定正确，大致是这个处理过程)

---

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
const double esp = 1e-6;
typedef long long ll;

int n,m,a[maxn],b[maxn];
int len[maxn],son[maxn];
double tmp[maxn],*dp[maxn],*id;
double val[maxn];
vector<int> g[maxn];

void prework(int u,int fa) {
	len[u] = son[u] = 0;
	for(auto v : g[u]) {
		if(v == fa) continue;
		prework(v,u);
		if(!son[u] || len[son[u]] < len[v])
			son[u] = v;
	}
	len[u] = len[son[u]] + 1;
}
void dfs(double &ans,int u,int fa,double mid) {
	val[u] = a[u] - mid * b[u]; dp[u][0] = 0;
	if(son[u]) {
		dp[son[u]] = dp[u] + 1;
		dfs(ans,son[u],u,mid);
		val[u] += val[son[u]];
		dp[u][0] -= val[son[u]];
		if(m < len[u]) 
			ans = min(ans,dp[u][m] + val[u]);
	}
	for(auto v : g[u]) {
		if(v == fa || v == son[u]) continue;
		dp[v] = id,id += len[v];
		dfs(ans,v,u,mid);
		for(int i = 0; i < len[v] && i < m; i++)
			if(m - i - 1 < len[u])
				ans = min(ans,dp[v][i] + val[v] + dp[u][m - i - 1] + val[u]);
		for(int i = 0; i < len[v]; i++)
			dp[u][i + 1] = min(dp[u][i + 1],dp[v][i] + val[v] + a[u] - mid * b[u] - val[u]);
	}
}
int main() {
	ll sum = 0;
	scanf("%d%d",&n,&m);
	m -= 1;
	for(int i = 1; i <= n; i++)
		scanf("%d",&a[i]),sum += a[i];
	for(int i = 1; i <= n; i++)
		scanf("%d",&b[i]);	
	for(int i = 1; i < n; i++) {
		int x,y;scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	prework(1,0);
	double l = 0,r = 2e5 + 5;
	while(r - l > esp) {
		double mid = (r + l) / 2,ans = 1e18;
		id = tmp,dp[1] = id,id += len[1];
		dfs(ans,1,0,mid);
		if(ans <= 0) r = mid;
		else l = mid + esp;
	}
	printf("%.2lf\n",l);
	return 0;
}