博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
bzoj3631 [JLOI2014]松鼠的新家
阅读量:5231 次
发布时间:2019-06-14

本文共 2211 字,大约阅读时间需要 7 分钟。

Description

松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个房间,并且有n-1根树枝连接,每个房间都可以相互到达,且俩个房间之间的路线都是唯一的。天哪,他居然真的住在“树”上。松鼠想邀请小熊维尼前来参观,并且还指定一份参观指南,他希望维尼能够按照他的指南顺序,先去a1,再去a2,……,最后到an,去参观新家。
可是这样会导致维尼重复走很多房间,懒惰的维尼不听地推辞。可是松鼠告诉他,每走到一个房间,他就可以从房间拿一块糖果吃。维尼是个馋家伙,立马就答应了。
现在松鼠希望知道为了保证维尼有糖果吃,他需要在每一个房间各放至少多少个糖果。因为松鼠参观指南上的最后一个房间an是餐厅,餐厅里他准备了丰盛的大餐,所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

Input

第一行一个整数n,表示房间个数
第二行n个整数,依次描述a1-an
接下来n-1行,每行两个整数x,y,表示标号x和y的两个房间之间有树枝相连。

Output

一共n行,第i行输出标号为i的房间至少需要放多少个糖果,才能让维尼有糖果吃。

Sample Input

5
1 4 5 3 2
1 2
2 4
2 3
4 5

Sample Output

1
2
1
2
1

HINT

 

2<= n <=300000

 

话说前几天搞地理历史会考没发过题解……现在想起考试都是痛

这题……我也不知道该说什么

原来我是当树链剖分的模板打的

结果样例wa了……调半天调不出来

然后对着标程调出来了……结果数据一测T了

仔细一看n<=30w……TMD原来树链剖分是骗分

正解是这样的

我们注意到在树上的修改之间不存在在线的询问,就是说,可以用离线的做法搞

考虑对于树上一条链x->y修改,可以直接把x->root的+1、把fa[y]->root的-1

其实就是差分啦

然后修改变O(1)的了……最后从叶节点到根dp一下就完了

注意修改x->lca和y->lca的时候lca被找了两次,要去掉

……因为dfs1的时候以1而不是a[1]为根还wa了一次

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long#define inf 0x7fffffff#define N 300010using namespace std;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}struct edge{int to,next;}e[2*N];int n,cnt;int a[N],f[N],bin[20];int head[N],dep[N],fa[N][20];inline void ins(int u,int v){ e[++cnt].to=v; e[cnt].next=head[u]; head[u]=cnt;}inline void insert(int u,int v){ ins(u,v); ins(v,u);}inline void dfs1(int x,int d){ dep[x]=d; for (int i=1;i<20;i++) if (d>=bin[i]) { fa[x][i]=fa[fa[x][i-1]][i-1]; }else break; for (int i=head[x];i;i=e[i].next) if (fa[x][0]!=e[i].to) { fa[e[i].to][0]=x; dfs1(e[i].to,d+1); }}inline int LCA(int a,int b){ if (dep[a]
=0;i--) if (fa[a][i]!=fa[b][i]) { a=fa[a][i]; b=fa[b][i]; } if (a==b)return a; return fa[a][0];}inline void dfs2(int x){ for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa[x][0]) { dfs2(e[i].to); f[x]+=f[e[i].to]; }}int main(){ n=read(); bin[0]=1;for (int i=1;i<20;i++)bin[i]=bin[i-1]*2; for (int i=1;i<=n;i++)a[i]=read(); for (int i=1;i

 

转载于:https://www.cnblogs.com/zhber/p/4254568.html

你可能感兴趣的文章
【原创】大数据基础之Zookeeper(4)应用场景
查看>>
静态变量数组实现LRU算法
查看>>
中文系统 上传file的input显示英文
查看>>
比callback更简洁的链式执行promise
查看>>
android permission
查看>>
【译】在Asp.Net中操作PDF - iTextSharp - 使用字体
查看>>
.net 文本框只允许输入XX,(正则表达式)
查看>>
Python 第四十五章 MySQL 内容回顾
查看>>
实验2-2
查看>>
MongoDB遇到的疑似数据丢失的问题。不要用InsertMany!
查看>>
android smack MultiUserChat.getHostedRooms( NullPointerException)
查看>>
监控工具之---Prometheus 安装详解(三)
查看>>
不错的MVC文章
查看>>
IOS Google语音识别更新啦!!!
查看>>
[置顶] Linux终端中使用上一命令减少键盘输入
查看>>
BootScrap
查看>>
路冉的JavaScript学习笔记-2015年1月23日
查看>>
Mysql出现(10061)错误提示的暴力解决办法
查看>>
2018-2019-2 网络对抗技术 20165202 Exp3 免杀原理与实践
查看>>
Swift - 异步加载各网站的favicon图标,并在单元格中显示
查看>>