「SDOI2015」嫁接树

· · 题解

前言

题面 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;
}