Description
Input
Output
Sample Input
1 2 2
1 3 4
1 4 3
3 5 1
3 6 2
Sample Output
6
4
7
5
6
//样例1中输出对应的景点序列分别为:
1号景点是{1, 3},2号景点是{2, 1, 3},3号景点是{3, 1},4号景点是{4, 1, 3},5号景点是{5, 3, 1},6号景点是{6, 3, 1}。
保证每个景点到1号景点需要经过的道路数不超过30
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define M 100010
using namespace std;
int n,m,num,S,root,k;
int deep[M],f[M],fa[M],sz[M],size[M];
int head[M],dis[M],son[M],maxn[M],top[M];
bool vis[M];
struct point{int to,next,dis;}e[M<<];
vector<int>S1[M],S2[M];
void add(int from,int to,int dis) {
e[++num].next=head[from];
e[num].to=to;
e[num].dis=dis;
head[from]=num;
}
void dfs1(int x) {
deep[x]=deep[f[x]]+,sz[x]=;
for(int i=head[x];i;i=e[i].next) {
int to=e[i].to;
if(to==f[x]) continue;
f[to]=x,dis[to]=dis[x]+e[i].dis;
dfs1(to),sz[x]+=sz[to];
if(sz[son[x]]<sz[to]) son[x]=to;
}
}
void dfs2(int x,int tp) {
top[x]=tp;
if(son[x]) dfs2(son[x],tp);
for(int i=head[x];i;i=e[i].next)
if(e[i].to!=f[x]&&e[i].to!=son[x])
dfs2(e[i].to,e[i].to);
}
int lca(int x,int y) {
while(top[x]!=top[y]) {
if(deep[top[x]]<deep[top[y]]) swap(x,y);
x=f[top[x]];
}
return deep[x]<deep[y]?x:y;
}
int getdis(int x,int y) {
return dis[x]+dis[y]-*dis[lca(x,y)];
}
void getroot(int x,int fa) {
size[x]=;maxn[x]=;
for(int i=head[x];i;i=e[i].next) {
int to=e[i].to;
if(fa==to||vis[to]) continue;
getroot(to,x);size[x]+=size[to];
maxn[x]=max(maxn[x],size[to]);
}
maxn[x]=max(maxn[x],S-size[x]);
if(maxn[x]<maxn[root]) root=x;
}
void solve(int x,int ff) {
fa[x]=ff;vis[x]=true;
for(int i=head[x];i;i=e[i].next) {
int to=e[i].to;
if(vis[to]) continue;
S=size[to],root=,getroot(to,x);
solve(root,x);
}
}
void update(int x) {
S1[x].push_back();
for(int i=x;fa[i];i=fa[i]) {
int dt=getdis(x,fa[i]);
S1[fa[i]].push_back(dt);
S2[i].push_back(dt);
}
}
int get1(int id,int d) {
int l=,r=S1[id].size()-,ans=;
while(l<=r) {
int mid=(l+r)/;
if(S1[id][mid]<=d) l=mid+,ans=mid+;
else r=mid-;
}
return ans;
}
int get2(int id,int d) {
int l=,r=S2[id].size()-,ans=;
while(l<=r) {
int mid=(l+r)/;
if(S2[id][mid]<=d) l=mid+,ans=mid+;
else r=mid-;
}
return ans;
}
int query(int x,int d) {
int ans=get1(x,d);
for(int i=x;fa[i];i=fa[i]) {
int dt=getdis(fa[i],x);
if(dt>d) continue;
ans+=get1(fa[i],d-dt);
ans-=get2(i,d-dt);
}
return ans;
}
int main() {
char s[];scanf("%s",s);
scanf("%d%d",&n,&k);k++;
for(int i=;i<n;i++) {
int a,b,c;scanf("%d%d%d",&a,&b,&c);
add(a,b,c),add(b,a,c);
}
dfs1(),dfs2(,);
maxn[]=S=n,getroot(,),solve(root,);
for(int i=;i<=n;i++)
update(i);
for(int i=;i<=n;i++) {
if(!S1[i].empty()) sort(S1[i].begin(),S1[i].end());
if(!S2[i].empty()) sort(S2[i].begin(),S2[i].end());
}
for(int i=;i<=n;i++) {
int l=,r=1e9,ans=1e9;
while(l<=r) {
int mid=(l+r)/;
if(query(i,mid)>=k) ans=mid,r=mid-;
else l=mid+;
}
printf("%d\n",ans);
}
return ;
}
[BZOJ2117]Crash的旅游计划的更多相关文章
-
[BZOJ2051]A Problem For Fun/[BZOJ2117]Crash的旅游计划/[BZOJ4317]Atm的树
[BZOJ2051]A Problem For Fun/[BZOJ2117]Crash的旅游计划/[BZOJ4317]Atm的树 题目大意: 给出一个\(n(n\le10^5)\)个结点的树,每条边有 ...
-
【BZOJ2117】 [2010国家集训队]Crash的旅游计划
[BZOJ2117] [2010国家集训队]Crash的旅游计划 Description 眼看着假期就要到了,Crash由于长期切题而感到无聊了,因此他决定利用这个假期和好友陶陶一起出去旅游. Cra ...
-
BZOJ4317Atm的树&;BZOJ2051A Problem For Fun&;BZOJ2117[2010国家集训队]Crash的旅游计划——二分答案+动态点分治(点分树套线段树/点分树+vector)
题目描述 Atm有一段时间在虐qtree的题目,于是,他满脑子都是tree,tree,tree…… 于是,一天晚上他梦到自己被关在了一个有根树中,每条路径都有边权,一个神秘的声音告诉他,每个点到其他的 ...
-
BZOJ2117: [2010国家集训队]Crash的旅游计划
裸点分,点分树每层维护有序表,查询二分,复杂度$O(nlog^3n)$. #include<bits/stdc++.h> #define M (u+v>>1) #define ...
-
[2010国家集训队]Crash的旅游计划
Description 眼看着假期就要到了,Crash由于长期切题而感到无聊了,因此他决定利用这个假期和好友陶陶一起出去旅游. Crash和陶陶所要去的城市里有N (N > 1) 个景点,Cra ...
-
BZOJ 2117: [2010国家集训队]Crash的旅游计划 动态点分治+二分
感觉现在写点分治可快了~ 二分答案,就可以将求第 $k$ 大转换成一个判断问题,直接拿点分树判断一下就行了. #include <cstdio> #include <vector&g ...
-
Crash的旅行计划
除草了.. Crash的旅行计划 [问题描述] 过不了多久,Crash就要迎来他朝思暮想的暑假.在这个暑假里,他计划着到火星上旅游.在火星上有N个旅游景点,Crash用1至N这N个正整数对这些景点标号 ...
-
CDOJ 1437 谭松松的旅游计划 Label:倍增LCA &;&; 最短路
谭松松的旅游计划 Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) Submit ...
-
思维导图哪款好用?怎么借助MindManager 做旅游计划
世界那么大,想不想去看看!想不想来一场说走就走的旅行?尤其是在新冠的笼罩下, 2020年已经过去四分之三,国内疫情已经基本得到了控制,接下来的日子里你想出门好好玩玩吗? 说走就走的旅游虽然美好,但是你 ...
随机推荐
-
【BZOJ 2541】【Vijos 1366】【CTSC 2000】冰原探险
http://www.lydsy.com/JudgeOnline/problem.php?id=2541 https://vijos.org/p/1366 loli秘制大爆搜_(:з」∠)_坑了好久啊 ...
-
写出形似QML的C++代码
最开始想出的标题是<Declarative C++ GUI库>,但太标题党了.只写了两行代码,连Demo都算不上,怎么能叫库呢……后来想换掉“库”这个字,但始终找不到合适词来替换.最后还是 ...
-
centos下整合PagerDuty、nagios初探(on-call尝鲜和体验)
[前言] 今天在某个群里看见有人介绍了PagerDuty,介绍到了slack.整合后可以更加方便和团队合作.于是我觉得来尝尝鲜. [PagerDuty是什么?] PagerDuty是一款能够在服务器出 ...
-
【MySql】权限不足导致的无法连接到数据库以及权限的授予和撤销
[环境参数] 1.Host OS:Win7 64bit 2.Host IP:192.168.10.1 3.VM: VMware 11.1.0 4.Client OS:CentOS 6 5.Client ...
-
Entity Framework学习(一)
网上看了很多的资料,发现都不是想要的学习资料,讲的不是很明白,最后在msdn开始自己研究EF MSDN的地址 https://msdn.microsoft.com/zh-cn/library/gg69 ...
-
常见的仿Flash图片轮播效果
现在基本在很多网站上都能看到轮播效果,虽然有点烂大街的赶脚,但是这个效果确实很好看,很时尚,今天分享下代码相对较少的轮播框架,望采纳 . ①向左滑动: 思路: 将几个图片用分别用几个 li 包住,并且 ...
-
asp.net学习
http://www.cnblogs.com/fish-li/archive/2011/12/27/2304063.html
-
Druid使用记录
最近项目稳定下来,就像折腾一下看看系统的运行情况,但是我们搞java的毕竟不是专业运维,看看数据库的运行情况就ok了. 1 Druid介绍 官方地址 https://github.com/alibab ...
-
使用jquery 的ajax 与 Java servlet的交互
由于是使用jquery的 所以别忘记导入jq 下面是jsp文件 <%@ page language="java" contentType="text/html; c ...
-
vs编码对编译的影响(UTF-8 no BOM编译通不过)
VS的编译器对Unicode源代码支持如下: UTF-16 little endian with or without byte order mark (BOM). UTF-16 big endian ...