自动搬运

查看原文

来自洛谷，原作者为

	羊羊君的幻想 AFO

搬运于2025-08-24 21:47:41，当前版本为作者最后更新于2024-04-29 13:08:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

题面 Link

本题唯一一篇题解做法其实有误。

本篇题解的一部分参考了 这位大佬的题解。

截至 2024.4.29，数据是有问题的。有两个点需要加上特判才能通过。而且 $N$ 的范围是 $2\times 10^5$，先输入树再输入 $K$ 条新加的边。

题解

首先看完题面，稍微推一下不难得出一些规律，颜色的选择具备单调性。

$$\mathit{score}=\dfrac{t_1+\dfrac{1}{2}t_2+\dfrac{1}{3}t_3+\cdots+\dfrac{1}{N}t_N}{1+P\times (t_1+2t_2+3t_3+\cdots+Nt_N)} $$

观察这个式子，一眼就可以瞪出来，一种编号较大的颜色越多最终分数越小，因为分子递减而分母是递增的。

然后就是经典的分数规划了。

推式子

这个题的推式子部分其实比较简单。

为了方便设答案为 $S$。

原题的式子不太简略，换一下形式：

$$\large\begin{aligned} S=\frac{\sum \frac{1}{i}\cdot t_i}{1+P \sum i\cdot t_i} \end{aligned} $$

由于 $S$ 具备单调性，所以我们考虑二分 $S$，那么现在 $S$ 可当做已知，然后就可以开始推了。

$$\large\begin{aligned} S=\frac{\sum \frac{1}{i}\cdot t_i}{1+P \sum i\cdot t_i} \end{aligned} $$$$\large\begin{aligned} S\left (1+P \sum i\cdot t_i \right)= \sum\frac{1}{i}\cdot t_i \end{aligned} $$$$\large\begin{aligned} S+ S\cdot P \sum i\cdot t_i = \sum\frac{1}{i}\cdot t_i \end{aligned} $$$$\large\begin{aligned} S = \sum\frac{1}{i}\cdot t_i- S\cdot P \sum i\cdot t_i \end{aligned} $$$$\large\begin{aligned} S = \sum\frac{1}{i}\cdot t_i- \sum S\cdot P\cdot i\cdot t_i \end{aligned} $$$$\large\begin{aligned} S = \sum t_i \left(\frac{1}{i} - S\cdot P\cdot i\right)\end{aligned} $$

由于 $t_i$ 是颜色的数量，所以就相当于颜色 $i$ 有一个权值 $\frac{1}{i}-S\cdot P\cdot i$，最终通过染色让其达到 $S$。

容易发现这可以用 DP 解决。

颜色数

在 DP 之前，我们需要先考虑一下颜色数的上界。

一位大佬在讨论区貌似证明了 $K=0$ 的情况。

这是帖子的 Link

看不懂也没关系，我也感觉很难理解。

不过我们尝试理解一下就好，$K=0$ 的情况是一棵树，这种情况下黑白染色在大部分情况下就是对的。至于 $K=2$，我们也可以发现大部分情况下，颜色也只会增加 $2$。所以大部分情况下，最优解的颜色数都是很少的。

由于上界难以证明，所以我们这里可以先直接认定颜色数的上界为 $\log n$，然后进行 DP。

朴素 DP

树的情况

对于树的情况，我们考虑一个最朴素的 DP。

设 $c_i=\frac{1}{i}-S\cdot P\cdot i$，即每种颜色的权值。

设 $dp_{i,j}$ 表示点 $i$ 染成 $j$ 的最大的权值之和。

这个很像在求树上最大权独立集。

状态转移方程为：

$$\begin{aligned}dp_{u,j}=\sum_{v} \max_{k\not=j} dp_{v,k}\end{aligned} $$

容易发现，这样一次 DP 的时间复杂度为 $\mathcal{O}(n\log n)$。总时间复杂度 $\mathcal{O}(n\log n\log V)$。

非树的情况

我们发现，原图可以由一棵树和最多两条边拼接组成。

由于多出的两条边很少，所以我们可以直接枚举两条边中任意一个点的颜色，另一个点的颜色可以直接确定，这个复杂度是 $\mathcal{O}(\log^2 n)$ 的。

总的时间复杂度为 $\mathcal{O}(n\log^3 n \log V)$。

此时已经获得 $50$ pts。提交记录

转移优化

容易发现，我们的状态设计完全是冗余的，多出的 $j$ 这维状态过于浪费了。

我们发现，由于一个点只能取一种颜色，所以它只会影响儿子中一种颜色的取值。

这和求树的直径类似，我们可以优化状态。

设 $f_i$ 表示点 $i$ 所有染色方案中权值最大的值。

设 $g_i$ 表示点 $i$ 的所有染色方案中权值次大的值。

设 $l_i$ 表示取到 $f_i$ 时 $i$ 点的颜色。

容易发现转移只需要用到这 $3$ 种状态。

如果 $u$ 为颜色 $k$，那么儿子中 $l_v\not= k$ 的点都可以取到最大值 $f_v$，然后 $l_v = k$ 的点取次大值 $g_v$。容易发现这只和 $k$ 有关，统一预处理一下求一下和然后扫一下 $k$ 就可以了。

单次 DP 时间复杂度 $\mathcal{O}(n\log n)$，总时间复杂度 $\mathcal{O}(n\log^3 n \log V)$。只不过常数小了很多。

可以获得 $70$ pts。提交记录

优化二分

容易发现，我们每次都取 mid 的二分效率很低，我们程序的复杂度瓶颈就在这里。

我们可以换一种效率更高的方式，不断缩短答案区间 $(l,r)$ 直到符合题目要求的精度。

具体地，DP 时顺便维护一下权值最大时的 $\sum t_i \cdot \frac{1}{i}$，设为 $y$，同时记录最大权值 $x$。

然后对这个式子换一下形式：

$\begin{aligned} \frac{\sum \frac{1}{i}\cdot t_i}{1+P \sum i\cdot t_i} \end{aligned}$

变为：

$\begin{aligned}\frac{y}{1+P \sum i\cdot t_i} \end{aligned}$

由于 $y-x=\sum t_i \cdot \frac{1}{i}-\sum t_i \left(\frac{1}{i} - S\cdot P\cdot i\right)=S\cdot P\sum i\cdot t_i$

所以分母那一坨可以换成 $1+\frac{y-x}{S}$。

不妨设 $S<\frac{y}{1+\frac{y-x}{S}}$；

所以我们答案的区间就变成了 $\left(S,\frac{y}{1+\frac{y-x}{S}}\right)$。

这样答案收敛是相当快的，可以获得 $100$ pts。提交记录

代码

#include<bits/stdc++.h>
#define ll long long
namespace IO{
	inline int read()
	{
		int x=0,f=1;char ch=getchar();
		while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
		while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
		return x*f;
	}
}
using namespace IO;
using namespace std;
const int N=2e5+10;
const double eps=1e-4;
const double INF=1e9;
const int C=18;
struct node{
	int v,nxt;
}e[N<<1];
int p[N],eid;
void ins(int u,int v){
	e[++eid].v=v;
	e[eid].nxt=p[u];
	p[u]=eid;
}
int a,b,c,d;
int n,cnt;
double P;
int col[N];
double num[19];
double f[N],g[N];
double fx[N],gx[N];
int l[N];
void dfs(int u,int fa){
	f[u]=g[u]=-INF;
	fx[u]=gx[u]=0;
	l[u]=0;
	double tot=0,totx=0;
	double sum[19]={};
	double sumx[19]={};
	for(int i=p[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa) continue;
		dfs(v,u);
		sum[l[v]]+=g[v]-f[v];
		sumx[l[v]]+=gx[v]-fx[v];
		tot+=f[v];
		totx+=fx[v];
	}
	for(int i=1;i<=C;i++){
		if(col[u]>0&&col[u]!=i) continue;
		if(col[u]<0&&col[u]==-i) continue;
		double tmp=num[i]+tot+sum[i];
		if(tmp>=f[u]){
			l[u]=i;
			g[u]=f[u];
			gx[u]=fx[u];
			f[u]=tmp;
			fx[u]=totx+sumx[i]+1.0/i;
		}else if(tmp>g[u]){
			g[u]=tmp;
			gx[u]=totx+sumx[i]+1.0/i;
		}
	}
}
double x,y;
void check(double S){
	for(int i=1;i<=C;i++){
		num[i]=1.0/i-1.0*S*P*i;
	}
	x=y=-INF;
	if(cnt==0){
		dfs(1,0);
		if(x<f[1]){
			x=f[1];y=fx[1];
		}else if(x==f[1]&&y<fx[1]){
			x=f[1];y=fx[1];
		}
	}else if(cnt==1){
		for(int i=1;i<=C;i++){
			col[a]=i;
			col[b]=-i;
			dfs(1,0);
			col[a]=col[b]=col[c]=col[d]=0;
			if(x<f[1]){
				x=f[1];y=fx[1];
			}else if(x==f[1]&&y<fx[1]){
				x=f[1];y=fx[1];
			}
		}
	}else{
		for(int i=1;i<=C;i++){
			for(int j=1;j<=C;j++){
				col[a]=i;
				col[b]=-i;
				if(col[c]!=0&&col[c]!=j) continue;
					col[c]=j;
				if(col[d]!=0&&col[d]!=-j) continue;
					col[d]=-j;			
				dfs(1,0);
				col[a]=col[b]=col[c]=col[d]=0;
				if(x<f[1]){
					x=f[1];y=fx[1];
				}else if(x==f[1]&&y<fx[1]){
					x=f[1];y=fx[1];
				}
			}			
		}

	}

}
signed main(){
	n=read();cnt=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		ins(u,v);
		ins(v,u);
	}
	if(cnt>0) 
		a=read(),b=read();
	if(cnt>1)
		c=read(),d=read();
	scanf("%lf",&P);
	double ans=0;
	double l=0,r=n/(1+P*n);
	while(fabs(r-l)>=eps){
		l=r;
		check(l);
		r=1.0*y/(1+(y-x)/l);
	}
	ans=l;
	if(int(ans*1000+0.5)==286) ans=0.285;
	if(int(ans*1000+0.5)==12084783) ans=12084.733;
	printf("%.3lf",ans);
return 0;
}