文档章节

BZOJ4987 Tree

o
 osc_1ee7cxmx
发布于 2018/08/06 18:50
字数 833
阅读 10
收藏 0

精选30+云产品,助力企业轻松上云!>>>

Tree

Description

从前有棵树。
找出$k$个点$A_1,A_2,…,A_k$。
使得$\sum_{1\leq i \leq k-1}dis(A_i,A_{i+1})$最小。

Input

第一行两个正整数$n,k$,表示树的顶点数和需要选出的点个数。
接下来$n-1$行每行$3$个非负整数$x,y,z$,表示从存在一条从$x$到$y$权值为$z$的边。

Output

一行一个整数,表示最小的距离和。
 
 
题解:
不难发现,选取的$k$个点在原树上是一个联通子树,考虑树形DP。
最终选取的$k$个点一定是从其中最远点对的一个点沿着直径同时遍历接在直径上的每一棵子树来到另一个点。
 
但是其实我们可以完全不考虑那么多,
就只需要把它想成沿着一个点出发遍历其他的点最终不需回到原来的点即可。
 
于是我们的状态就很显然,对于每一个节点$x$:
$C[x][m]$表示,起点和终点为$x$所在子树的任意一点,途径$x$所在的子树,共计遍历了$m$个不同点的最小代价。
$F[x][m]$表示,起点和终点中有一点为$x$所在子树的任意一点且另一点为$x$,途径$x$所在的子树,共计遍历了$m$各不同点的最小代价。
$B[x][m]$表示,起点和终点均为$x$,途径$x$所在的子树,共计遍历了$m$个不同的点的最小代价。
 
转移就很好写,DFS时,从大到小枚举一个点的前若干个子树大小之和,同时从大到小枚举当前子树大小,更新当前根节点的答案即可。
 
这样的复杂度相当于在以$x$为根的子树中枚举点对,且这两个点分别在不同儿子的子树中。因此,对于任意点对$(u,v)$,当且仅当DFS到$lca(u,v)$时会被枚举到,因此时间复杂度综合为$O(n^2)$。
 
 
 
 
AC代码如下
 
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define M 3020
using namespace std;
int read(){
	int nm=0,fh=1;char cw=getchar();
	for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;
	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
	return nm*fh;
}
int n,m,fs[M],nt[M<<1],to[M<<1],len[M<<1];
int ans,F[M][M],B[M][M],C[M][M],dst,tmp,u,v,sz[M];
void update(int &x,int y){x=min(x,y);}
void link(int x,int y){nt[tmp]=fs[x],fs[x]=tmp,to[tmp]=y,len[tmp++]=dst;}
void DP(int x,int last){
	sz[x]=1,F[x][1]=C[x][1]=B[x][1]=0;
	for(int i=fs[x];i!=-1;i=nt[i]){
		if(to[i]==last) continue;
		int v=to[i]; DP(v,x);
		for(int k=sz[x];k>0;k--){
		    for(int j=sz[v];j>0;j--){
				update(B[x][j+k],B[v][j]+B[x][k]+(len[i]<<1));
				update(F[x][j+k],min(B[v][j]+F[x][k]+len[i],F[v][j]+B[x][k])+len[i]);
				update(C[x][j+k],min(min(C[x][k]+B[v][j],C[v][j]+B[x][k])+len[i],F[x][k]+F[v][j])+len[i]);
			}
		}
		sz[x]+=sz[v];
	}
	update(ans,min(min(C[x][m],B[x][m]),F[x][m]));
}
int main(){
	n=read(),m=read(),memset(&ans,0x7f,sizeof(int));
	memset(fs,-1,sizeof(fs)),memset(F,0x7f,sizeof(F));
	memset(C,0x7f,sizeof(C)),memset(B,0x7f,sizeof(B));
	for(int i=1;i<n;i++) u=read(),v=read(),dst=read(),link(u,v),link(v,u);
	DP(1,0),printf("%d\n",ans);
	return 0;
}
 
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Hacker News 简讯 2020-07-11

更新时间: 2020-07-11 00:00 Scientists make precise edits to mitochondrial DNA for first time - (nature.com) 科学家首次对线粒体DNA进行精确编辑 得分:66 | 评论:4 LibreOffice: The N......

FalconChen
45分钟前
95
0
是否有可能从另一个git存储库中挑选一个提交? - Is it possible to cherry-pick a commit from another git repository?

问题: I'm working with a git repository that needs a commit from another git repository that knows nothing of the first. 我正在使用一个git存储库,需要从另一个不知道第一个存储库......

技术盛宴
昨天
26
0
【LeetCode】53 盛最多水的容器

题目 解题思路 双指针法: https://leetcode-cn.com/problems/container-with-most-water/solution/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/ 代码 public class Solution { ......

JaneRoad
昨天
20
0
阿里云OSS配置CDN加速

首先购买CDN流量包 然后添加域名 添加好后 然后将域名OSS.xxxx.com 解析到 生成的CDN域名上 这样就完成了

可达鸭眉头一皱
昨天
16
0
js 整数与小数正则替换片段

说明 /(\d+)/g 整数 /(\d+\.\d+)rem/g 小数 /(\d+\.\d+|\d+)rem/g 其中 | 或 条件 例子 全局查找带 rem 单位的,替换成 px 单位 let text = text.replace(/(\d+\.\d+|\d+)rem/g, function(s......

DrChenXX
昨天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部