树剖/差分裸题。。
//28260kb 584ms
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 500000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=3e5+5;
int A[N],Enum,H[N],nxt[N<<1],to[N<<1],fa[N],dep[N],sz[N],son[N],top[N],sum[N];
char IN[MAXIN],*SS=IN,*TT=IN,OUT[3000000],*O=OUT;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
void print(int x)
{
if(x>9) print(x/10);
*O++ = x%10+48;
}
inline void AE(int u,int v)
{
to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;
}
inline int LCA(int u,int v)
{
while(top[u]!=top[v]) dep[top[u]]>dep[top[v]]?u=fa[top[u]]:v=fa[top[v]];
return dep[u]<dep[v]?u:v;
}
void DFS1(int x)
{
int mx=0; sz[x]=1;
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=fa[x])
fa[v]=x, dep[v]=dep[x]+1, DFS1(v), sz[x]+=sz[v], sz[v]>mx&&(mx=sz[v],son[x]=v);
}
void DFS2(int x,int tp)
{
top[x]=tp;
if(son[x])
{
DFS2(son[x],tp);
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=fa[x]&&v!=son[x]) DFS2(v,v);
}
}
void DFS3(int x)
{
for(int i=H[x]; i; i=nxt[i])
if(to[i]!=fa[x]) DFS3(to[i]), sum[x]+=sum[to[i]];
}
int main()
{
int n=read();
for(int i=1; i<=n; ++i) A[i]=read();
for(int i=1; i<n; ++i) AE(read(),read());
DFS1(1), DFS2(1,1);
for(int i=1,w; i<n; ++i)
++sum[fa[A[i]]], ++sum[A[i+1]], --sum[w=LCA(A[i],A[i+1])], --sum[fa[w]];
// ++sum[A[i]], ++sum[A[i+1]], --sum[w=LCA(A[i],A[i+1])], --sum[fa[w]];
DFS3(1);//还可以用拓扑替换掉DFS。。
++sum[A[1]], --sum[A[n]];
// for(int i=2; i<=n; ++i) --sum[A[i]];
for(int i=1; i<=n; ++i) print(sum[i]),*O++='\n';//printf("%d\n",sum[i]);
fwrite(OUT,O-OUT,1,stdout);
return 0;
}
BZOJ.3631.[JLOI2014]松鼠的新家(树上差分)的更多相关文章
-
BZOJ 3631: [JLOI2014]松鼠的新家 树上差分 + LCA
Description 松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个房间,并且有n-1根树枝连接,每个房间都可以相互到达,且俩个房间之间的路线都是唯一的.天哪,他居然真的住在“树”上.松鼠想邀 ...
-
BZOJ 3631: [JLOI2014]松鼠的新家( 树链剖分 )
裸树链剖分... ------------------------------------------------------------------- #include<bits/stdc++ ...
-
Bzoj 3631: [JLOI2014]松鼠的新家(树链剖分+线段树)
3631: [JLOI2014]松鼠的新家 Time Limit: 10 Sec Memory Limit: 128 MB Description 松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个 ...
-
bzoj 3631: [JLOI2014]松鼠的新家
Description 松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个房间,并且有n-1根树枝连接,每个房间都可以相互到达,且俩个房间之间的路线都是唯一的.天哪,他居然真的住在"树&q ...
-
洛谷 P3258 BZOJ 3631 [JLOI2014]松鼠的新家
题目描述 松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个房间,并且有n-1根树枝连接,每个房间都可以相互到达,且俩个房间之间的路线都是唯一的.天哪,他居然真的住在”树“上. 松鼠想邀请小熊维尼前 ...
-
bzoj3631 [JLOI2014]松鼠的新家——树上差分
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3631 树上差分:注意路径的结尾被多算了一次,最后要减去(不能提前减). 代码如下: #inc ...
-
[JLOI2014]松鼠的新家 树上差分
差分 一开始竟然想分情况讨论来差分,然后发现各自情况要分析, 就是为了解决中间节点重复计算的问题, 结果 最后一想,中间重复计算了一次,那我最后减掉不就好了么,,, 那这就是一道差分裸题了(这是唯一不 ...
-
3631: [JLOI2014]松鼠的新家
3631: [JLOI2014]松鼠的新家 Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 707 Solved: 342[Submit][Statu ...
-
3631. [JLOI2014]松鼠的新家【树形DP】
Description 松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个房间,并且有n-1根树枝连接,每个房间都可以相互到达,且俩个房间之间的路线都是唯一的.天哪,他居然真的住在“树”上.松鼠想邀 ...
随机推荐
-
DIV实现纵向滚动条overflow-y
DIV实现纵向滚动条overflow-y:scroll的使用, 1.首先设置固定div的宽高2.overflow-y:scroll如果设置overflow:auto;表示当你内容超过div高度出现滚动 ...
-
Mysql分支
MySQL是历史上最受欢迎的免费开源程序之一.它是成千上万个网站的数据库骨干,并且可以将它(和linux)作为过去10年里Internet呈指数级增长的一个有力证明. 那么,如果MySQL真的这么重要 ...
-
Flex 箭头(军标)库封装完成
封装的一个月,在这个月期间还完成的一些其它的工作:公司有规定不能公布代码,我可以讲一下大致的流程,真的很抱歉! 1.用B样条曲线画箭头的两侧的曲线,这个要注意了,不要贝塞尔曲线,因为贝塞尔曲线的算法会 ...
-
第一次";正经面试";之发现自己的缺陷和不足
1:初试之校园招聘~~~ 如果你细心,可能发现了"正经面试"加了双引号,说起这次面试(昨天面的技术试),要从上礼拜六,距今已经一礼拜了吧.现在这个时候校园招聘已经蠢蠢欲动了吧,(说 ...
-
Python之切片操作
1.列表list中使用 1.range()生成器 就是list取值的一种方式. 生成器range(),用于写列表的范围,如果只写一个数,就表示从0开始,到写入的值-1: l=list(range(10 ...
-
雷林鹏分享:jQuery EasyUI 数据网格 - 创建属性网格
jQuery EasyUI 数据网格 - 创建属性网格 属性网格(property grid)带有一个内置的 expand(展开)/collapse(合并) 按钮,可以简单地为行分组.您可以简单地创建 ...
-
npm install权限问题,报错:permission denied。
1.部署gulp项目时,nodeJs和gulp都已经正确安装,在项目内部执行npm install命令时,有些gulp的插件一直下载不成功,报错几种以下错误: “gulp-imagemin: Coul ...
-
python resize
import sys import os sys.path.append('/usr/local/lib/python2.7/site-packages') sys.path.append('/usr ...
-
kettle 遇到 解决Incorrect integer value: &#39;&#39; for column &#39;id&#39; at row 1 完美解决-费元星
最近自己在测试一个开源的程序,测试中发现.该程序都添加和更新的时候回出现 Incorrect integer value: '' for column 'id' at row 1类是的错误! 后来我自 ...
-
Shortcut Keys in Eclipse
@1: Here are some shortcut keys in Eclipse that I use a lot.Eclipse的编辑功能非常强大,掌握了Eclipse快捷键功能,能够大大提高开 ...