您现在的位置是:首页 > 正文

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

2024-01-30 22:55:07阅读 0

这道题我前前后后做了一年,共过了 4 4 4 遍,每次都有的新的理解;这次我认为自己理解透了,于是就写了一篇题解。

这道题是我入坑看到的第一道黑题(当时很萌,不知道黑题是什么,看到这题感觉很好玩),另外还有就是《切树游戏》和 Spiders Evil Plan,记载着我的回忆(

Description

传送门

Solution

算法一

为方便叙述,令树根为 1 1 1 w u , v w_{u,v} wu,v 表示 u , v u,v u,v 之间的边权, son { u } \text{son}\{u\} son{u} 表示 u u u 的儿子组成的集合。

可以发现,答案即为 ⌈ \lceil 在树上选出 k + 1 k+1 k+1 条不相交的路径 ⌋ \rfloor 的最大边权和。

考虑 dp \text{dp} dp

f u , i , j f_{u,i,j} fu,i,j 表示,看了以 u u u 为根的子树,子树内一共选了 i i i 条不相交的路径,且 u u u 当前度数 j j j 的最大边权和。

  • j = 0 j=0 j=0,则目前没有包含 u u u 的路径。特别的,若以 u u u 为根的子树已经遍历完,则 f u , i , j f_{u,i,j} fu,i,j 表示所有该子树中的路径都被固定时的最大边权和(也就是说,遍历完子树后 f u , 0 f_{u,0} fu,0 对应的状态中 u u u 的度数可以为 0 0 0 1 1 1 2 2 2)。
  • j = 1 j=1 j=1,则目前恰有一条以 u u u 为一端的非固定路径(也就是说可以继续延伸出去,没有彻底固定这条路径的形态)。因为这条路径不固定,所以这条路径并没有被计入 i i i
  • j = 2 j=2 j=2,则目前有一条包含 u u u 的路径,且其任意一端均不为 u u u(跨越了 u u u 的两个子树)。

考虑使用树形背包转移。具体来说,令目前要将以 v ( v ∈ son { u } ) v(v \in \text{son}\{u\}) v(vson{u}) 为根的子树合并上来,则有转移:

f u , i , 0 : = max ⁡ ( f u , i , 0 , max ⁡ j = 0 i { f u , j , 0 + f v , i − j , 0 } ) f_{u,i,0}:=\max(f_{u,i,0},\max_{j=0}^i \{f_{u,j,0}+f_{v,i-j,0}\}) fu,i,0:=max(fu,i,0,j=0maxi{fu,j,0+fv,ij,0}) f u , i , 1 : = max ⁡ ( f u , i , 1 , max ⁡ j = 0 i { f u , j , 0 + f v , i − j , 1 + w u , v } , max ⁡ j = 0 i { f u , j , 1 + f v , i − j , 0 } ) f_{u,i,1}:=\max(f_{u,i,1},\max_{j=0}^i \{f_{u,j,0}+f_{v,i-j,1}+w_{u,v}\},\max_{j=0}^i \{f_{u,j,1}+f_{v,i-j,0}\}) fu,i,1:=max(fu,i,1,j=0maxi{fu,j,0+fv,ij,1+wu,v},j=0maxi{fu,j,1+fv,ij,0}) f u , i , 2 : = max ⁡ ( f u , i , 2 , max ⁡ j = 0 i − 1 { f u , j , 1 + f v , i − j − 1 , 1 + w u , v } , max ⁡ j = 0 i { f u , j , 2 + f v , i − j , 0 } ) f_{u,i,2}:=\max(f_{u,i,2},\max_{j=0}^{i-1} \{f_{u,j,1}+f_{v,i-j-1,1}+w_{u,v}\},\max_{j=0}^i \{f_{u,j,2}+f_{v,i-j,0}\}) fu,i,2:=max(fu,i,2,j=0maxi1{fu,j,1+fv,ij1,1+wu,v},j=0maxi{fu,j,2+fv,ij,0})

在转移结束后,执行:

f u , i , 0 : = max ⁡ ( f u , i , 0 , f u , i − 1 , 1 , f u , i , 2 ) f_{u,i,0}:=\max(f_{u,i,0},f_{u,i-1,1},f_{u,i,2}) fu,i,0:=max(fu,i,0,fu,i1,1,fu,i,2)

答案即为 f 1 , k + 1 , 0 f_{1,k+1,0} f1,k+1,0

这个做法的时间复杂度是 O ( n k ) O(nk) O(nk) 而非 O ( n k 2 ) O(nk^2) O(nk2) O ( n 2 ) O(n^2) O(n2) 的,期望得分 60 60 60 分。下面是来自我说说的简要证明:

  • 每次合并,将第一维度从 0 0 0 枚举到了 m i n ( s i z [ u ] , k ) min(siz[u],k) min(siz[u],k),第二维度从 0 0 0 枚举到了 m i n ( s i z [ v ] , k ) min(siz[v],k) min(siz[v],k),那么其对复杂度的贡献就是它们的乘积。
  • 我们可以认为,这里将 ⌈ \lceil 目前已合并到 u u u 处的部分中 dfs \text{dfs} dfs 序前 k k k 大的 ⌋ \rfloor ⌈ \lceil v v v 为根的子树中 dfs \text{dfs} dfs 序前 k 小的 ⌋ \rfloor 两两合并。
  • 因此,从全局的角度来看,每个节点只会与 dfs \text{dfs} dfs 序与其差不超过 2 k 2k 2k 的点进行合并。
  • 从而,总复杂度为 O ( 4 n k ) O(4nk) O(4nk)

算法二

运气足够好可以发现, f 1 , 0 , f 1 , 1 , ⋯   , f 1 , k f_{1,0},f_{1,1},\cdots,f_{1,k} f1,0,f1,1,,f1,k 组成了一个上凸函数。

于是,直接 wqs 二分就可以 O ( n log ⁡ w ) O(n \log w) O(nlogw) 地通过本题了,尽管常数大得离谱。

这题就这么结束了?不,我们还需要注意一个细微的问题——凸函数上三点共线

这会意味着什么呢?为什么会导致错误呢?考虑一段区间 [ l , r ] [l,r] [l,r],其中的点( f 1 , l , f 1 , l + 1 , ⋯   , f 1 , r f_{1,l},f_{1,l+1},\cdots,f_{1,r} f1,l,f1,l+1,,f1,r)在一条直线上。那么,若 k ∈ [ l , r ] k \in [l,r] k[l,r],那么很容易出现切不到 k k k 的情况(即,虽然斜率正确,但是切到的点不对),导致 wqs 二分结束了都没有输出答案,从而导致 WA。

那么该如何处理呢?可以发现,在 wqs 二分结束后,若没有找出答案,那么我们依然可以得到该线的斜率截距,其中前者即为二分结束后的下界 l l l,后者可以通过再跑一轮 dp \text{dp} dp 得出。于是,我们不难确定这个一次函数的表达式,就能简单地得出该一次函数在 k k k 处的值了。

综上所述,我们处理完了细节,本题被彻底解决。

Code

由于 dp \text{dp} dp 不仅要存储最大边权和,还要存储选出路径的条数,因此我采用了一个叫做 LCT 的结构体来维护,重载加法,小于之后十分方便,这里建议大家采用。

另外,请注意开 long long,并把二分上下界的绝对值设大。同时,二分上下界有人证明过可以设置为整数了,于是我就写了整数。虽然我觉得这是错的,所以大家还是用 double 吧。

#include <bits/stdc++.h>
#define int long long
#define chkmax(a,b) ((a)<(b)?(a)=(b):0)
using namespace std;
const int maxl=300005;

int read(){
	int s=0,w=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-')  w=-w;ch=getchar();}
	while (ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^'0');ch=getchar();}
	return s*w;
}
int n,k,cnt,l,r;
int head[maxl];

struct edge{int nxt,to,dis;}e[maxl<<1];

struct LCT{
	int val,x;
	LCT(int xx=0,int yy=0):val(xx),x(yy){};
	friend bool operator<(LCT a,LCT b){
		return a.val==b.val?a.x>b.x:a.val<b.val;
	}
	friend LCT operator+(LCT a,LCT b){
		return LCT(a.val+b.val,a.x+b.x);
	}
	friend LCT operator+(LCT a,int b){
		return LCT(a.val+b,a.x);
	}
}f[maxl][3],s;

void add_edge(int u,int v,int w){
	cnt++;
	e[cnt].to=v,e[cnt].dis=w,e[cnt].nxt=head[u],head[u]=cnt; 
}

void dfs(int u,int fath){
	f[u][0]=f[u][1]=f[u][2]=LCT();
	for (int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if (v==fath)  continue;
		dfs(v,u);
		
		chkmax(f[u][2],max(f[u][2]+f[v][0],f[u][1]+f[v][1]+s+e[i].dis));
		chkmax(f[u][1],max(f[u][1]+f[v][0],f[u][0]+f[v][1]+e[i].dis));
		chkmax(f[u][0],f[u][0]+f[v][0]);
	}
	chkmax(f[u][0],max(f[u][1]+s,f[u][2]));
}

signed main(){
	n=read(),k=read()+1;
	for (int i=1;i<n;i++){
		int u=read(),v=read(),w=read();
		add_edge(u,v,w),add_edge(v,u,w);
	}
	l=-3e11,r=3e11;
	while (l<=r){
		int mid=(l+r)>>1;
		s=LCT(-mid,1);
		
		dfs(1,0);
		if (f[1][0].x==k)  return cout<<f[1][0].val+k*mid<<endl,0;
		else if (f[1][0].x>k)  l=mid+1;
		else r=mid-1;
	}
	s=LCT(-l,1),dfs(1,0);
	cout<<f[1][0].val+k*l<<endl;
	
	return 0;
}

网站文章

  • webpack的使用方法

    webpack的使用方法

    webpack的使用方法

    2024-01-30 22:54:59
  • XML标记语言:标签和语法规则、利用dom4j对XML进行解析、XML的DTD约束和schema约束;自定义枚举;自定义注解和元注解

    XML标记语言:标签和语法规则、利用dom4j对XML进行解析、XML的DTD约束和schema约束;自定义枚举;自定义注解和元注解

    XML标记语言:标签和语法规则、利用dom4j对XML进行解析、XML的DTD约束和schema约束;自定义枚举;自定义注解和元注解

    2024-01-30 22:54:53
  • 其实你也可以使用SpringBoot自定义starter

    其实你也可以使用SpringBoot自定义starter

    使用过SpringBoot的都应该知道,一个SpringBoot 项目就是由一个一个 Starter 组成的,一个 Starter 代表该项目的 SpringBoot 启动依赖,除了官方已有的 Sta...

    2024-01-30 22:54:26
  • 快速排序为什么要从右边开始

    为什么要从右边开始:假如对 6 1 2 7 9进行从小到大的排序,6作为基准数,如果从左边开始,i首先到达一个比6大的数,这个数为7,这时候再从左边走,但这时7到最后一个数之间已经没有比6小的数,所以...

    2024-01-30 22:54:19
  • 《TensorFlow深度学习》(七)——Keras高层接口

    《TensorFlow深度学习》(七)——Keras高层接口

    Keras 是一个主要由Python 语言开发的开源神经网络计算库,最初由François Chollet编写,它被设计为高度模块化和易扩展的高层神经网络接口,使得用户可以不需要过多的专业知识就可以简洁、快速地完成模型的搭建与训练。本文学习tf.keras

    2024-01-30 22:54:12
  • 详解基于MATLAB的车牌识别系统设计与实现(1):车牌定位

    详解基于MATLAB的车牌识别系统设计与实现(1):车牌定位

    车牌识别系统主要包括车牌定位、字符分割和字符识别三个核心模块。车牌定位是利用车牌的颜色和形状特征确认并获取汽车的车牌位置;字符分割是将获取到的车牌切割成单个字符;字符识别目前主要有基于模板匹配算法和基于人工神经网络算法对切割的字符进行识别。本节内容主要讲解车牌定位,主要内容有:读取图像预处理边缘检测形态学操作定位裁剪主函数代码如下 :// main.mclose all;cle...

    2024-01-30 22:53:41
  • ACPI电源管理的6个状态(S0-S5) 热门推荐

    ACPI 电源管理的6个状态:S0: 主机正常工作状态S1: CPU停止工作,wakeup时间为:0sS2: CPU关闭,wakeup时间为:0.1sS3: 主机中除了内存以外其他所有部件都停止工 作,wakeup时间为:0.5sS4: 主机将内存中的信息写入到硬盘中,之后关闭所有组件,wakeup时间为:30sS5: 关机

    2024-01-30 22:53:33
  • Servlet Cookie取不到值原因

    现象: 在测试带Cookie的HTTP请求时发现,服务端用request.getHeader(&quot;cookie&quot;)可以去到值;但是用request.getCookies()却不行Co...

    2024-01-30 22:53:16
  • Java中的类与变量

    一、静态 1、类的静态成员与类直接相关,与对象无关,在一个类的所有实例之间共享同一个静态成员,该类的对象共享其静态成员变量的值 2、静态成员函数中不能调用非静态成员,静态成员变量可被该类的所有方法访问...

    2024-01-30 22:52:48
  • 网络安全,别报!!!

    网络安全,别报!!!

    网络安全究竟要不要报?7年网工如是说

    2024-01-30 22:52:38