【洛谷 P3258】[JLOI2014]松鼠的新家【树上差分+LCA】


题目描述

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

松鼠想邀请小熊前来参观,并且还指定一份参观指南,他希望小熊能够按照他的指南顺序,先去 a 1 ,再去 a 2 ,……,最后到 a n ,去参观新家。可是这样会导致重复走很多房间,懒惰的维尼不停地推辞。可是松鼠告诉他,每走到一个房间,他就可以从房间拿一块糖果吃。

小熊是个馋家伙,立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃,他需要在每一个房间各放至少多少个糖果。

因为松鼠参观指南上的最后一个房间 a n 是餐厅,餐厅里他准备了丰盛的大餐,所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

输入格式

第一行一个正整数 n,表示房间个数第二行 n 个正整数,依次描述a1,a 2​ ,⋯,a n 。

接下来 n-1 行,每行两个正整数 x,y,表示标号 x 和 y 的两个房间之间有树枝相连。

输出格式

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

输入输出样例

输入 #1

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

输出 #1

1
2
1
2
1

分析:

你谷人均清华北大 有线段树+树上差分的 有树链剖分的 还有什么

LCT(LinkCutTreeLCT(Link Cut Tree

LCT(LinkCutTree动态树

))

)的 我只能 %%%

STOORZSTOORZ

STOORZ
树上差分

+LCA+LCA

+LCA
题目大意:

n1n-1

n−1条路径 求每个点被覆盖了多少次
但是对于

xx

x和

x1x-1

x−1两个点 它们是相连的 会被计算两次 要全部

ans1ans-1

ans−1
尽管如此 范围也应该是

a2a2

a2~

anan

an 所以要用差分做
树上差分就是在树上进行差分
树上差分的

aiai

ai表示

ii

i节点的子树和……
求出每条链

xx

x

yy

y 求出它们的

LCALCA

LCA 再将

xx

x到

LCALCA

LCA和

yy

y到

LCALCA

LCA都进行差分
只要

LCALCA

LCA不是根节点

LCALCA

LCA做一次差分

LCALCA

LCA的父节点做一次差分

CODE:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+1;
int qaq[3*N],n,tot,x,y,head[3*N],dep[3*N],f[3*N][20],qwq[3*N],ans[3*N];
struct node{
int to,next;
}a[6*N];
void add(int x,int y)
{
a[++tot]=(node){y,head[x]}; //邻接表
head[x]=tot;
}
void dfs(int x,int fa){
for(int i=head[x];i;i=a[i].next)
{
int OvO=a[i].to;
if(OvO==fa) continue; //LCA预处理
f[OvO][0]=x;
dep[OvO]=dep[x]+1;
dfs(OvO,x);
}
}
int LCA(int x,int y){ //求出LCA函数
int ans=0;
if(dep[x]<dep[y]) swap(x,y);
for(int i=19;i>=0;i--)
if(dep[f[x][i]]>=dep[y])
x=f[x][i];
if(x==y) return x;
for(int i=19;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
else ans=f[x][i];
}
return ans;
}
void ans_(int x,int fa){
for(int i=head[x];i;i=a[i].next)
{
int OvO=a[i].to;
if(OvO==fa) continue;
ans_(OvO,x);
ans[x]+=ans[OvO];
}
ans[x]+=qwq[x]; //计算子树和
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&qaq[i]);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
dep[1]=1; dfs(1,0);
for(int j=1;j<20;j++)
for(int i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1]; //模板LCA
for(int i=1;i<n;i++)
{
int lca=LCA(qaq[i],qaq[i+1]); //求出LCA
qwq[qaq[i]]++;
qwq[qaq[i+1]]++; //差分
qwq[lca]--;
if(lca!=1) qwq[f[lca][0]]--; //lca不是根节点
}
ans_(1,0); //子树和
for(int i=1;i<=n;i++)
ans[i]--;
ans[qaq[1]]++; //除了a[1] ans都-1
for(int i=1;i<=n;i++)
printf("%d\n",ans[i]);

return 0;
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

【洛谷 P3258】[JLOI2014]松鼠的新家【树上差分+LCA】

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 【洛谷 P3258】[JLOI2014]松鼠的新家【树上差分+LCA】
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏