BZOJ.3631.[JLOI2014]松鼠的新家(树上差分)

时间:2022-09-08 09:32:25

题目链接

树剖/差分裸题。。

//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]松鼠的新家(树上差分)的更多相关文章

  1. BZOJ 3631&colon; &lbrack;JLOI2014&rsqb;松鼠的新家 树上差分 &plus; LCA

    Description 松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个房间,并且有n-1根树枝连接,每个房间都可以相互到达,且俩个房间之间的路线都是唯一的.天哪,他居然真的住在“树”上.松鼠想邀 ...

  2. BZOJ 3631&colon; &lbrack;JLOI2014&rsqb;松鼠的新家&lpar; 树链剖分 &rpar;

    裸树链剖分... ------------------------------------------------------------------- #include<bits/stdc++ ...

  3. Bzoj 3631&colon; &lbrack;JLOI2014&rsqb;松鼠的新家&lpar;树链剖分&plus;线段树&rpar;

    3631: [JLOI2014]松鼠的新家 Time Limit: 10 Sec Memory Limit: 128 MB Description 松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个 ...

  4. bzoj 3631&colon; &lbrack;JLOI2014&rsqb;松鼠的新家

    Description 松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个房间,并且有n-1根树枝连接,每个房间都可以相互到达,且俩个房间之间的路线都是唯一的.天哪,他居然真的住在"树&q ...

  5. 洛谷 P3258 BZOJ 3631 &lbrack;JLOI2014&rsqb;松鼠的新家

    题目描述 松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个房间,并且有n-1根树枝连接,每个房间都可以相互到达,且俩个房间之间的路线都是唯一的.天哪,他居然真的住在”树“上. 松鼠想邀请小熊维尼前 ...

  6. bzoj3631 &lbrack;JLOI2014&rsqb;松鼠的新家——树上差分

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3631 树上差分:注意路径的结尾被多算了一次,最后要减去(不能提前减). 代码如下: #inc ...

  7. &lbrack;JLOI2014&rsqb;松鼠的新家 树上差分

    差分 一开始竟然想分情况讨论来差分,然后发现各自情况要分析, 就是为了解决中间节点重复计算的问题, 结果 最后一想,中间重复计算了一次,那我最后减掉不就好了么,,, 那这就是一道差分裸题了(这是唯一不 ...

  8. 3631&colon; &lbrack;JLOI2014&rsqb;松鼠的新家

    3631: [JLOI2014]松鼠的新家 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 707  Solved: 342[Submit][Statu ...

  9. 3631&period; &lbrack;JLOI2014&rsqb;松鼠的新家【树形DP】

    Description 松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个房间,并且有n-1根树枝连接,每个房间都可以相互到达,且俩个房间之间的路线都是唯一的.天哪,他居然真的住在“树”上.松鼠想邀 ...

随机推荐

  1. DIV实现纵向滚动条overflow-y

    DIV实现纵向滚动条overflow-y:scroll的使用, 1.首先设置固定div的宽高2.overflow-y:scroll如果设置overflow:auto;表示当你内容超过div高度出现滚动 ...

  2. Mysql分支

    MySQL是历史上最受欢迎的免费开源程序之一.它是成千上万个网站的数据库骨干,并且可以将它(和linux)作为过去10年里Internet呈指数级增长的一个有力证明. 那么,如果MySQL真的这么重要 ...

  3. Flex 箭头(军标)库封装完成

    封装的一个月,在这个月期间还完成的一些其它的工作:公司有规定不能公布代码,我可以讲一下大致的流程,真的很抱歉! 1.用B样条曲线画箭头的两侧的曲线,这个要注意了,不要贝塞尔曲线,因为贝塞尔曲线的算法会 ...

  4. 第一次&quot&semi;正经面试&quot&semi;之发现自己的缺陷和不足

    1:初试之校园招聘~~~ 如果你细心,可能发现了"正经面试"加了双引号,说起这次面试(昨天面的技术试),要从上礼拜六,距今已经一礼拜了吧.现在这个时候校园招聘已经蠢蠢欲动了吧,(说 ...

  5. Python之切片操作

    1.列表list中使用 1.range()生成器 就是list取值的一种方式. 生成器range(),用于写列表的范围,如果只写一个数,就表示从0开始,到写入的值-1: l=list(range(10 ...

  6. 雷林鹏分享:jQuery EasyUI 数据网格 - 创建属性网格

    jQuery EasyUI 数据网格 - 创建属性网格 属性网格(property grid)带有一个内置的 expand(展开)/collapse(合并) 按钮,可以简单地为行分组.您可以简单地创建 ...

  7. npm install权限问题,报错:permission denied。

    1.部署gulp项目时,nodeJs和gulp都已经正确安装,在项目内部执行npm install命令时,有些gulp的插件一直下载不成功,报错几种以下错误: “gulp-imagemin: Coul ...

  8. python resize

    import sys import os sys.path.append('/usr/local/lib/python2.7/site-packages') sys.path.append('/usr ...

  9. kettle 遇到 解决Incorrect integer value&colon; &&num;39&semi;&&num;39&semi; for column &&num;39&semi;id&&num;39&semi; at row 1 完美解决-费元星

    最近自己在测试一个开源的程序,测试中发现.该程序都添加和更新的时候回出现 Incorrect integer value: '' for column 'id' at row 1类是的错误! 后来我自 ...

  10. Shortcut Keys in Eclipse

    @1: Here are some shortcut keys in Eclipse that I use a lot.Eclipse的编辑功能非常强大,掌握了Eclipse快捷键功能,能够大大提高开 ...