首页 > 其他分享 >P4383 [八省联考 2018] 林克卡特树

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

时间:2024-11-05 14:32:59浏览次数:2  
标签:Node 八省 ch int max mid rd 2018 联考

简化题意,给一棵树,找出恰好 \(k+1\) 条链,是这些链之和最大。

有恰好选出的字眼,并且原问题显然具有凸性,直接考虑 wqs 二分。

然后每条链会减去二分的 \(mid\),然后没有限制,求最大链和及链的数量,考虑树形 dp。

设 \(f_{x,0/1/2}\) 表示以 \(x\) 为根的子树,\(x\) 点入度为 \(0/1/2\) 所得的最大链值。

特别地,每次转移完 \(x\) 后令 \(f_{x,0}=\max(f_{x,0},f_{x,1}+mid,f_{x,2})\),表示 \(x\) 不再和祖先进行链的合并,此时得到的最优解。

接下来就能转移了,设 \(y\) 是 \(x\) 的儿子,转移分三步:

\(f_{x,2}=\max(f_{x,2}+f_{y,0},f_{x,1}+f_{y,1}+w_{(x,y)}+mid)\)

\(f_{x,1}=\max(f_{x,1}+f_{y,0},f_{x,0}+f_{y,1}+w_{(x,y)})\)

\(f_{x,0}=\max(f_{x,0}+f_{y,0})\)

最后判断链数和 \(k\) 的大小关系,就做完了。

注意边权相等时,链数少的状态优先转移,因为维护的是上凸包。

#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ll long long
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*f;
}
const int N=3e5+10;
const ll INF=1e12;
int n,k,head[N],tot;
struct node{int to,nxt,w;}edge[N<<1];
void add(int x,int y,int w){edge[++tot]={y,head[x],w};head[x]=tot;}
struct Node{
	ll val;int cnt;
	Node(ll x=0,int y=0):val(x),cnt(y){}
	friend bool operator<(Node a,Node b){return a.val!=b.val?a.val<b.val:a.cnt>b.cnt;}
	friend Node operator+(Node a,Node b){return Node{a.val+b.val,a.cnt+b.cnt};}
	friend Node operator+(Node a,ll v){return Node{a.val+v,a.cnt};}
}f[N][3],tmp;
void dfs(int x,int fa){
	f[x][0]=f[x][1]=f[x][2]=Node();
	f[x][2]=max(f[x][2],tmp);
	for(int i=head[x];i;i=edge[i].nxt){
		int y=edge[i].to;if(y==fa) continue;
		dfs(y,x);
		f[x][2]=max(f[x][2],max(f[x][2]+f[y][0],f[x][1]+f[y][1]+edge[i].w+tmp));
		f[x][1]=max(f[x][1],max(f[x][1]+f[y][0],f[x][0]+f[y][1]+edge[i].w));
		f[x][0]=max(f[x][0],f[x][0]+f[y][0]);
	}
	f[x][0]=max(f[x][0],max(f[x][1]+tmp,f[x][2]));
}
int main(){
	n=rd,k=rd,k++;
	FOR(i,1,n-1){int x=rd,y=rd,w=rd;add(x,y,w),add(y,x,w);}
	ll l=-INF,r=INF,ans=0 ;
	while(l<r){
		ll mid=(l+r+1)/2ll;
		tmp=Node{-mid,1};dfs(1,0);
		if(f[1][0].cnt==k){printf("%lld\n",f[1][0].val+k*mid);return 0;}
		if(f[1][0].cnt>k) l=mid+1;
		else r=mid;
	}
	tmp=Node{-l,1};dfs(1,0),printf("%lld\n",f[1][0].val+k*l);
	return 0;
}

标签:Node,八省,ch,int,max,mid,rd,2018,联考
From: https://www.cnblogs.com/summ1t/p/18527828

相关文章

  • [2023四校联考3]flandre
    flandre题目:芙兰朵露有nn种烟花,每种都有两个参数:「真实效果」aa和「感觉效果」bb,其中「真实效果」是一个给定不变的整数(可以为负),「感觉效果」初值等于「真实效果」。将烟花按一定顺序燃放,先燃放的烟花会使得后面「真实效果」较差的烟花「感觉效果」更差,「真实效果」更优的「......
  • [HCTF 2018]admin
    题目链接:https://buuoj.cn/challenges#[HCTF2018]admin打开题目后如下所示。右上方有一个菜单,存在登陆模块,尝试使用admin登陆,对密码进行爆破,发现密码为123,随即获得flag。但实际上,该题的真正考点并不是弱密码。访问环境默认页面,在页面源代码处发现提示"youarenotadm......
  • [护网杯 2018]easy_tornado
    题目链接:https://buuoj.cn/challenges#[护网杯2018]easy_tornado打开环境后如下所示。依次访问。这里需要留意一下url,在访问flag.txt时,发现url为:/file?filename=/flag.txt&filehash=f37c974391ee4a7bc4a23cc8987e0eed。尝试将filehash参数更改掉,发现被重定向到:/er......
  • P4898 [IOI2018] seats 排座位
    题目链接主要算法:线段树(虚假的),奇技淫巧(真正的)思路:1.初步:考虑如何保证一个区间坐好后是一个矩形,有一个思路从另一个题中启示我们维护\(xmin,xmax,ymin,ymax\),但是这样无法保证在中间挖一个空的情况(有一个别的题解,可以染色后维护四个角和一个判框的东西),但我们觉得就算可以维......
  • [HCTF 2018]WarmUp
    题目链接:https://buuoj.cn/challenges#[HCTF2018]WarmUp打开环境后如下。查看页面源代码,发现存在提示"source.php"。<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"conte......
  • Adobe Acrobat Pro 2024 v24.3.20180 (macOS, Windows) - 创建、转换和编辑 PDF
    AdobeAcrobatPro2024v24.3.20180(macOS,Windows)-创建、转换和编辑PDFAdobeAcrobatPDFsoftware请访问原文链接:https://sysin.org/blog/adobe-acrobat查看最新版。原创作品,转载请保留出处。作者主页:sysin.orgAcrobat:创建、转换和编辑PDF借助Acrobat实现各种......
  • 2024.10.4 2018-2019 ACM-ICPC Southeastern European Regional Programming Contest
    比赛链接Solved:7/11Penalty:914Rank:1/74Rank(vp):63/1k+Dirt:22%G答案是4*纯色块数+5。考虑怎么维护这个纯色块数。这道题的修改保证了一个块纯色当且仅当其行列都纯色。因此对行列分别维护一棵线段树,维护每一层分别有多少个纯色节点,按层乘起来相加就行。K1操作的增加量......
  • 题解:P7306 [COCI2018-2019#1] Strah
    分享一个\(O(nm\logm)\)的方法。分析考虑每次在\(x\)轴上固定左端点,然后移动\(x\)轴上的右端点,并统计答案。考虑如何统计一个\(1\timesn\)的区域的贡献。显然长度为\(i\)的区间有\(n-i+1\)个,所以贡献即为:\[\begin{aligned}f(n)=&\sum^n_{i=1}i\left(n-i+1\ri......
  • 1-petalinux2018.3摸索记录-petalinux-config
    1-petalinux2018.3摸索记录-petalinux-config一、petalinux-config的具体配置-ZYNQMPConfiguration​​1、LinuxCompomentSelection​​LinuxCompomentSelection,Linux组件选择.FirstStageBootloader和Autoupdateps_init勾选会自动生成fsbl.elf,自动更新ps_i......
  • 0-petalinux2018.3摸索记录-快速亮机
    0-petalinux2018.3摸索记录-快速亮机一、环境搭建1、环境要求①需要注意petalinux、vivado、vitis、linux之间的版本对应关系,在ug1144上可以找到②需要注意linux的硬件要求,运存8G以上不然会报错等等2、环境依赖配置2018.3_PetaLinux_Package_List.xls......