题目背景

珂朵莉放假了,她打算去唐山旅行。

题目描述

我们简单地把唐山的共 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 ;
}

最新文章

  1. OCIEnvNlsCreate 失败,返回代码为 -1,但错误消息文本不可用
  2. .Net生成HTML的三种方法
  3. php 对象中连贯执行方法
  4. [UE4]AnimDynamics简介
  5. Android动画之Interpolator和AnimationSet
  6. windows系统下Python环境的搭建
  7. jgroup 概述--官方文档
  8. poj 2774 Long Long Message 后缀数组LCP理解
  9. ab基本用法
  10. iOS-C文件添加到iOS项目中,运行报错
  11. DataTables获取表单输入框数据
  12. python类:magic魔术方法
  13. MySQL系统变量sql_safe_updates总结
  14. 关于Spring的Quartz定时器设定
  15. Android事件处理的三种方法
  16. margin的两个有趣现象:margin合并和margin塌陷
  17. Python-select 关键字 多表查询 子查询
  18. input type = file 上传图片转为base64
  19. HTML语言
  20. [书摘]Windows内存管理术语

热门文章

  1. Python之元祖
  2. python中正则表达式与模式匹配
  3. MySql 基础 基本使用方法
  4. C语言的移位操作符及位运算
  5. vector元素的删除 remove的使用 unique的使用
  6. 解决EF 4.0 中数据缓存机制
  7. BNUOJ 1268 PIGS
  8. codeforces 691D(数据结构)
  9. 在windows下安装Django
  10. POJ1328 Radar Installation 解题报告