第 1 行包含2个非负整数 n,t,分别表示城市的个数和数据类型(其意义将在后面提到)。输入文件的第 2 到 n 行,每行描述一个除SZ之外的城市。其中第 v 行包含 5 个非负整数 f_v,s_v,p_v,q_v,l_v,分别表示城市 v 的父亲城市,它到父亲城市道路的长度,票价的两个参数和距离限制。请注意:输入不包含编号为 1 的SZ市,第 2 行到第 n 行分别描述的是城市 2 到城市 n。
输出包含 n-1 行,每行包含一个整数。其中第 v 行表示从城市 v+1 出发,到达SZ市最少的购票费用。同样请注意:输出不包含编号为 1 的SZ市。
对于所有测试数据,保证 0≤pv≤106,0≤qv≤1012,1≤fv<v;保证 0<sv≤lv≤2×1011,且任意城市到SZ市的总路程长度不超过 2×1011。
输入的 t 表示数据类型,0≤t<4,其中:
当 t=0 或 2 时,对输入的所有城市 v,都有 fv=v-1,即所有城市构成一个以SZ市为终点的链;
当 t=0 或 1 时,对输入的所有城市 v,都有 lv=2×1011,即没有移动的距离限制,每个城市都能到达它的所有祖先;
当 t=3 时,数据没有特殊性质。
n=2×10^5
强行树分治。
首先我们先弄出斜率方程【我还没弄出来】
然后先分治根到重心的所有点和子树。更新重心子树的答案【具体做法是扫描重心到根这条链。然后加入一个点就把最远可以到达这个点的子树更新】
然后分治重心的子树
于是乎我还没写完这题的代码= =b
写完了
http://blog.csdn.net/popoqqq/article/details/42640777
于是重新写一遍
首先呢我们弄出斜率方程
当j在k上面且j比k优的时候有:(f[j]-f[k])/(s[j]-s[k])>p[i]
可是p[i]似乎不是单调的啊。怎么办呢。可以二分
然后就很好做了
我们做树分治
每次先分治上面的【跟到重心这棵子树】再更新下面的【重心下面的】
对于下面的节点,我们按照可以到达的深度从大到小排序
然后从重心往根跳,每往上跳一个就更新最远可以到达当前的那些节点
然后再分治重心的子树就可以了
【调了一整天发现是一个函数调用的时候括号把后面比较的一起括进去了,累不爱】
大概不是括号。。也许只是最后一次DEBUG发现那里括号在上一次改动的时候标错了= =翻了几个历史版本似乎括号都没问题
#include<cstdio>
#include<algorithm>
using namespace std;
struct city
{
long long f,s,p,q,l;
}p[1000001];
struct line
{
int s,t;
long long x;
int next;
bool flag;
}a[2000001];
int head[1000001];
int edge;
inline void add(int s,int t,long long x)
{
a[edge].next=head[s];
head[s]=edge;
a[edge].s=s;
a[edge].t=t;
a[edge].x=x;
a[edge].flag=true;
}
long long dis[1000001];
int len[1000001];
int dep[1000001],son[1000001],mson[1000001];
int ans[1000001][22];
long long anc[1000001][22];
long long f[1000001];
inline bool cmp(int x,int y)
{
if(dep[len[x]]>dep[len[y]])
return true;
return false;
}
inline void dfs1(int d)
{
int i,j;
for(i=head[d];i!=0;i=a[i].next)
{
int t=a[i].t;
dis[t]=dis[d]+a[i].x;
dep[t]=dep[d]+1;
ans[t][0]=d;
anc[t][0]=a[i].x;
for(j=1;j<=21;j++)
{
ans[t][j]=ans[ans[t][j-1]][j-1];
anc[t][j]=anc[ans[t][j-1]][j-1]+anc[t][j-1];
}
dfs1(t);
}
}
int minx,mini;
inline void find(int d,int s)
{
son[d]=0;
mson[d]=0;
int i;
for(i=head[d];i!=0;i=a[i].next)
{
if(a[i].flag)
{
int t=a[i].t;
find(t,s);
son[d]+=son[t]+1;
mson[d]=max(mson[d],son[t]+1);
}
}
int tmp=max(mson[d],s-mson[d]-1);
if(tmp<minx)
{
minx=tmp;
mini=d;
}
}
int ps;
int px[1000001];
inline void gets(int d)
{
int i;
for(i=head[d];i!=0;i=a[i].next)
{
if(a[i].flag)
{
int t=a[i].t;
ps++;
px[ps]=t;
gets(t);
}
}
}
int q[1000001];
struct save
{
int x;
long long f;
long long dis;
double k;
};
inline double getk(int k,int j)
{
return double(f[j]-f[k])/double(dis[j]-dis[k]);
}
inline void solve(int d,int size,int zx)
{
if(size==1)
return ;
else if(size==2)
{
if(dep[len[zx]]<=dep[d])
{
if(f[zx]!=0)
f[zx]=min(f[zx],f[d]+(dis[zx]-dis[d])*p[zx].p+p[zx].q);
else
f[zx]=f[d]+(dis[zx]-dis[d])*p[zx].p+p[zx].q;
}
return ;
}
int i;
int ttx=son[zx];
son[d]-=son[zx];
for(i=head[zx];i!=0;i=a[i].next)
a[i].flag=false;
minx=2100000000;
mini=0;
find(d,son[d]+1);
solve(d,son[d]+1,mini);
for(i=head[zx];i!=0;i=a[i].next)
a[i].flag=true;
ps=0;
ps++;
px[ps]=zx;
gets(zx);
sort(px+1,px+1+ps,cmp);
int dx=zx;
int l=1,r=0,lt=1;
while(dx!=p[d].f)
{
while(l<r&&getk(q[r-1],q[r])<getk(q[r],dx))
r--;
r++;
q[r]=dx;
while(dep[len[px[lt]]]>dep[dx])
lt++;
dx=p[dx].f;
while(((dep[len[px[lt]]]==dep[q[r]])||(dep[len[px[lt]]]<dep[q[r]]&&dx==p[d].f))&<<=ps)
{
int ll=l+1,rr=r;
while(ll<=rr)
{
int mid=(ll+rr)/2;
if(getk(q[mid-1],q[mid])>p[px[lt]].p)
ll=mid+1;
else
rr=mid-1;
}
if(f[px[lt]]!=0)
f[px[lt]]=min(f[px[lt]],f[q[rr]]+(dis[px[lt]]-dis[q[rr]])*p[px[lt]].p+p[px[lt]].q);
else
f[px[lt]]=f[q[rr]]+(dis[px[lt]]-dis[q[rr]])*p[px[lt]].p+p[px[lt]].q;
lt++;
if(lt>ps)
break;
}
//此处是没有推出公式的斜率优化dp ,
//动态维护凸包(-dis,f)
//-dis是单调的......
}
find(zx,ttx+1);
for(i=head[zx];i!=0;i=a[i].next)
{
int t=a[i].t;
minx=2100000000;
mini=0;
find(t,son[t]+1);
solve(t,son[t]+1,mini);
}
}
int main()
{
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
int n,t;
scanf("%d%d",&n,&t);
int i,j;
for(i=2;i<=n;i++)
{
scanf("%lld%lld%lld%lld%lld",&p[i].f,&p[i].s,&p[i].p,&p[i].q,&p[i].l);
edge++;
add(p[i].f,i,p[i].s);
}
dis[1]=0;
dep[1]=1;
dfs1(1);
long long dx;
int d;
for(i=1;i<=n;i++)
{
j=21;
dx=0;
d=i;
while(j>=0)
{
if(dx+anc[d][j]<=p[i].l)
{
dx+=anc[d][j];
d=ans[d][j];
}
j--;
}
len[i]=d;
}
minx=2100000000;
mini=0;
find(1,n);
solve(1,n,mini);
for(i=2;i<=n;i++)
printf("%lld\n",f[i]);
return 0;
}
文章浏览阅读712次。视频播放器原理 什么是ffmpeg? ffmpeg 音视频编/解码 流程图 ffmpeg 常用 struct AVFormatContext AVStream AVCodecContext AVCodec AVPacket AVFrame ffmpeg 常用Api av_register_all() avformat_alloc_output_context2() avio_open()..._视频效果演示系统的核心技术
文章浏览阅读449次。Java List集合多种情况处理方法:List集合交集、并集、差集、去重、与数组互转、删除、排序等操作_java list reduce
文章浏览阅读2.3k次,点赞77次,收藏80次。需求:指人对客观事务需要的表现,体现为愿望、意向和兴趣,因而成为行动的一种直接原因。软件需求(IEEE软件工程标准词汇表):(1)用户解决问题或达到目标所需的条件或能力。(2)系统或系统部件要满足合同、标准、规范或者其他正式规定文档所需具有条 件或能力。(3)对(1)或(2)中的一个条件或一种能力的一种文档化表述。用例:定义 1 用例是对一个活动者使用一个系统的一项功能时进行交互过程中的一个文字描述序列。_uml需求文档访客管家
文章浏览阅读574次。第三章、Linux根文件系统及文件管理命令详解02_03_Linux根文件系统详解文件系统:rootfs: 根文件系统 FHS:Filesystem Hierarchy Standard(文件系统目录标准)的缩写,多数Linux版本采用这种文件组织形式,类似于Windows操作系统中c盘的文件目录,FHS采用树形结构组织文件。FHS定_根文件系统文本登陆
文章浏览阅读358次。马克 · 扎克伯格期望的元宇宙到底会是什么样子?_马克扎克伯格博客
文章浏览阅读1.4w次,点赞8次,收藏78次。本文接上一篇文章 使用Python开发游戏运行脚本(一)成功调用大漠插件上一篇我们已经简单实现了python调用大漠插件并输出版本号的功能,接下来我们要做的就是通过大漠插件模拟鼠标点击和键盘文字输入。 由于近年来最热门的游戏基本都是手游,所以我们也会以手游为例来进行游戏脚本的开发。大漠插件是一款针对Windows平台的鼠标键盘模拟+图文查找库,这样我们要想实现手游脚本开发的第一步,就是下载Android模拟器,然后在对安卓模拟器进行鼠标和键盘的模拟,以此来实现自动化游戏脚本。一、Android模拟器的_大漠窗口绑定成功按键
文章浏览阅读1k次。 利用Canvas的fillText(),隔一定时间在画布上作画<!DOCTYPE html><head> <meta charset="utf-8"> <meta name="viewport" content="width=device-width,initial-scale=1.0"> &_canvas画字符雨
文章浏览阅读1.1k次。微信公众号跳转微信小程序,自定义微信跳转标签_opentaglist
文章浏览阅读4.3k次。数据恢复技术与LVM数据恢复方法 1摘要 随着计算机网络应用的发展,数据存储的安全性变的越来越重要。在常见的基于RAID和LVM的环境下面,当出现硬盘故障或者错误操作导致数据丢失的情况下,采用适当的数据恢复策略可以在很大程度上提供数据恢复的成功概率。本文研究了几种情况下的数据恢复技术和方法,为数据恢复和数据安全的预防提供了指导。 2数据恢复需求 2.1Linux IO存储栈 图(1)Linux IO 存储..._vgreduce --removemissing恢复
文章浏览阅读307次。深度学习程序员想年薪百万,基础必须打牢,所以推荐重点书籍Deep Learning花书Deep Learning with PythonDeep Learning for Computer Vision with PythonScikit-Learn与TensorFLow机器学习实用指南深度学习实践Tensorflow机器学习指南..._年薪百万的程序员看什么书
文章浏览阅读1.3k次。一、使用clock()函数,获取毫秒级(ms)时间[1]#include <time.h>//clock()头文件clock_t start = clock();{statement section}//测试代码段clock_t end = clock();printf("the running time is :%fs\n", (double)(end -s..._large_integer nfreq, t1, t2;
文章浏览阅读6.8k次,点赞3次,收藏31次。 前言: 至于用哪个开发工具本文暂且不做任何讨论, 今天着重讲解IntelliJ IDEA这款开发工具的使用 前言:IntelliJ IDEA如果说IntelliJ IDEA是一款现代化智能开发工具的话,Eclipse则称得上是石器时代的东西了。其实笔者也是一枚从Eclipse转IDEA的探索者,随着近期的不断开发实践和调试,逐步..._idea使用视频教程