U74201 旅行计划 树上找链长度
2024-08-30 21:56:19
题目背景
珂朵莉放假了,她打算去唐山旅行。
题目描述
我们简单地把唐山的共 nn 个景点看成是一棵树,有 n-1n−1 条边将它们连接起来,每个景点有一个游览指数 v_ivi。珂朵莉的假期时间不长,她只打算参观连续的恰好 kk 个景点。珂朵莉很可爱,所以她希望她所参观的景点里游览指数最低的景点的游览指数最高,她现在想知道其最高值是多少。
输入输出格式
输入格式:
第一行两个整数 n,k
接下来共 n−1 行每行两个整数 a b ,表示这两个景点相连
接下来 n 个整数 vi
输出格式:
一个整数,如题描述
输入输出样例
输入样例
4 2
1 2
1 3
2 4
1 2 4 3
输出样例
2
说明
对于百分之三十的数据
n,k,v≤100
对于百分之六十的数据
n,k,v≤500
对于百分之百的数据
k≤n≤100000
1≤vi≤1000000
这道题用二分枚举k上最小的最大值
然后check()判断树上是否有一条符合条件的链长度>=k;
用fir记录当前节点儿子中最长链长度,sec为当前节点儿子中第二长链,g[]为第一加第二+1等于当前节点为根节点时满足条件的最长链的长度(前提是当前节点满足条件)。
思想就是这样;
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int pre[*maxn],last[maxn],other[*maxn],l;
int n,k,val[maxn],ans,mid,qw;
int fir[maxn],sec[maxn],g[maxn];
void add(int x,int y)
{
l++;
pre[l]=last[x];
last[x]=l;
other[l]=y;
} void dfs(int u,int fa)
{
for(int p=last[u];p;p=pre[p])
{
int v=other[p];
if(v==fa) continue;
dfs(v,u);
if(g[v]>fir[u])//儿子的最长链更新 当前节点的第一大链
{
fir[u]=g[v];
}
else if(sec[u]<g[v])//不然看看第二长链
{
sec[u]=g[v];
}
}
if(val[u]>=mid&&sec[u]+fir[u]+>=k)
{
qw=;
}
if(val[u]>=mid) g[u]=fir[u]+;//更新当前节点最长链
else g[u]=;
} int check()
{
qw=;
memset(g,,sizeof(g));
memset(fir,,sizeof(fir));
memset(sec,,sizeof(sec));
dfs(,); return qw;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
for(int i=;i<=n;i++)
{
scanf("%d",&val[i]);
}
int l=,r=;
while(l<=r)
{
mid=(l+r)>>;
if(check())
{
ans=mid;
l=mid+;
}
else r=mid-;
}
printf("%d",ans);
return ;
}
最新文章
- OCIEnvNlsCreate 失败,返回代码为 -1,但错误消息文本不可用
- .Net生成HTML的三种方法
- php 对象中连贯执行方法
- [UE4]AnimDynamics简介
- Android动画之Interpolator和AnimationSet
- windows系统下Python环境的搭建
- jgroup 概述--官方文档
- poj 2774 Long Long Message 后缀数组LCP理解
- ab基本用法
- iOS-C文件添加到iOS项目中,运行报错
- DataTables获取表单输入框数据
- python类:magic魔术方法
- MySQL系统变量sql_safe_updates总结
- 关于Spring的Quartz定时器设定
- Android事件处理的三种方法
- margin的两个有趣现象:margin合并和margin塌陷
- Python-select 关键字 多表查询 子查询
- input type = file 上传图片转为base64
- HTML语言
- [书摘]Windows内存管理术语