【LOJ#2236】【洛谷P3258】松鼠的新家【LCA】【树上差分】

2024-01-30 09:58

本文主要是介绍【LOJ#2236】【洛谷P3258】松鼠的新家【LCA】【树上差分】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目大意:

题目链接:
洛谷:https://www.luogu.org/problem/P3258
LOJ:https://loj.ac/problem/2236
给出一棵树以及 n n n个点走的顺序,求每一个点会被经过几次。规定到达最后一个点的那一次不算。


思路:

这是一道在「省选斗兽场 − - 树链剖分」的一道题目。
本着背树剖板子心态来刷的。看完题后
这不是一道树上差分sb题吗?????
既然在树剖分类中,那就用树剖求LCA吧。
在普通树剖中,我们会有这样一段程序

void addrange(int x,int y,int k)
{while (top[x]!=top[y]){if (dep[top[x]]<dep[top[y]]) swap(x,y);Tree.update(1,id[top[x]],id[x],k);x=fa[top[x]];}if (id[x]>id[y]) Tree.update(1,id[y],id[x],k);else Tree.update(1,id[x],id[y],k);
}

我们发现,最终退出 w h i l e while while循环时, x y xy xy两点必然位于同一条重链中。
那么显然此时的LCA就是深度较浅的点。
这样就可以用树剖 O ( log ⁡ n ) O(\log n) O(logn)求出LCA。而且常数很小。
然后随便用树上差分搞一搞就可以了。
但是要注意,从 x → y , y → z x\to y,y\to z xy,yz中,我们会把 y y y计算两次,这样就导致答案多了1。所以最终答案要减去1。
同时第 1 , n 1,n 1,n个点只会算1次,按理来说是不用减1的,但是题目要求最后一次到达第 n n n个点不用算,所以就依然要减1,而第一个点就不用了。
时间复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn)


代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int N=300010;
int n,tot,a[N],s[N],head[N],dep[N],son[N],fa[N],top[N],size[N];struct edge
{int next,to;
}e[N*2];void add(int from,int to)
{e[++tot].to=to;e[tot].next=head[from];head[from]=tot;
}void dfs1(int x,int f)
{fa[x]=f; dep[x]=dep[f]+1; size[x]=1;for (int i=head[x];~i;i=e[i].next){int y=e[i].to;if (y!=f){dfs1(y,x);if (size[y]>size[son[x]]) son[x]=y;size[x]+=size[y];}}
}void dfs2(int x,int tp)
{top[x]=tp;if (son[x]) dfs2(son[x],tp);for (int i=head[x];~i;i=e[i].next){int y=e[i].to;if (y!=fa[x] && y!=son[x]) dfs2(y,y);}
}void dfs3(int x)
{for (int i=head[x];~i;i=e[i].next){int y=e[i].to;if (y!=fa[x]){dfs3(y);s[x]+=s[y];}}
}int lca(int x,int y)
{while (top[x]!=top[y]){if (dep[top[x]]<dep[top[y]]) swap(x,y);x=fa[top[x]];}return dep[x]>dep[y]?y:x;
}int main()
{ memset(head,-1,sizeof(head));scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d",&a[i]);for (int i=1,x,y;i<n;i++){scanf("%d%d",&x,&y);add(x,y); add(y,x);}dfs1(1,0); dfs2(1,1);for (int i=1;i<n;i++){int LCA=lca(a[i],a[i+1]);s[a[i]]++; s[a[i+1]]++;s[LCA]--; s[fa[LCA]]--;}dfs3(1); s[a[1]]++;  //第一个点不用减1for (int i=1;i<=n;i++)printf("%d\n",s[i]-1);return 0;
}

这篇关于【LOJ#2236】【洛谷P3258】松鼠的新家【LCA】【树上差分】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/659869

相关文章

poj1330(LCA最近公共祖先)

题意:求最近公共祖先 思路:之前学习了树链剖分,然后我就用树链剖分的一小部分知识就可以解这个题目了,记录每个结点的fa和depth。然后查找时,每次将depth大的结点往上走直到x = y。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>

poj 3159 (spfa差分约束最短路) poj 1201

poj 3159: 题意: 每次给出b比a多不多于c个糖果,求n最多比1多多少个糖果。 解析: 差分约束。 这个博客讲差分约束讲的比较好: http://www.cnblogs.com/void/archive/2011/08/26/2153928.html 套个spfa。 代码: #include <iostream>#include <cstdio>#i

poj 3169 spfa 差分约束

题意: 给n只牛,这些牛有些关系。 ml个关系:fr 与 to 牛间的距离要小于等于 cost。 md个关系:fr 与 to 牛间的距离要大于等于 cost。 隐含关系: d[ i ] <= d[ i + 1 ] 解析: 用以上关系建图,求1-n间最短路即可。 新学了一种建图的方法。。。。。。 代码: #include <iostream>#include

POJ 1364差分约束

给出n个变量,m个约束公式 Sa + Sa+1 + .... + Sa+b < ki or > ki ,叫你判断是否存在着解满足这m组约束公式。 Sa + Sa+1   +   .+ Sa+b =  Sum[a+b] - Sum[a-1]  . 注意加入源点n+1 。 public class Main {public static void main(Strin

Python中差分进化differential_evolution的调用及参数说明

在场景应用中,要求我们的函数计算结果尽可能的逼近实际测量结果,可转化计算结果与测量结果的残差,通过最小化残差,便可求出最优的结果。但使用最小二乘等方法来计算时,常常会使迭代的结果显然局部最优点而导致结算错误。 差分进化原理 差分进化(Differential Evolution,DE)是一种基于群体差异的进化算法,其计算思想主要包括以下几个方面: 一、初始化种群 首先,随机生成一个初始种群

高精度计算(代码加解析,洛谷p1601,p1303)除法待更新

目录 高精度加法 高精度减法 高精度乘法 高精度加法 我们知道在c++语言中任何数据类型都有一定的表示范围。当两个被加数很大时,正常加法不能得到精确解。在小学,我们做加法都采用竖式方法。那么我们也只需要按照加法进位的方式就能得到最终解。 8 5 6+ 2 5 5-------1 1 1 1 加法进位: c[i] = a[i] + b[i];if(c[i] >=

洛谷 凸多边形划分

T282062 凸多边形的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 先整一个半成品,高精度过两天复习一下补上 #include <iostream>#include <algorithm>#include <set>#include <cstring>#include <string>#include <vector>#include <map>

能量项链,洛谷

解释:  环形dp问题还是考虑将环拉直,可以参考我上一篇文章:环形石子合并 [2 3 5 10 2] 3 5 10 将环拉直,[]内是一个有效的区间,可以模拟吸收珠子的过程,         如[2 3 5] <=>(2,3)(3,5)    2是头,3是中间,5是尾 len >= 3:因为最后[2 10 2]是最小的可以合并的有效区间 len <= n + 1因为[2 3

RS485差分信号不对称

在RS485总线通信中,差分信号不对称的问题时常出现,尤其是在总线未接从机设备的情况下。这一问题不仅影响通信质量,还可能导致信号传输错误。通过对实际波形、芯片手册及电路的深入分析,可以找出引发差分信号不对称的根本原因,并采取相应的解决措施。 问题描述 在RS485通信测试中,当总线上没有从机设备连接时,观察到RS485差分信号(A、B)关于地(GND)不对称。理想情况下,RS485的差分信

洛谷P5490扫描线

0是最小的数字,将一个线段看成一个区间,对于一个矩形,从下扫到上,入边为1,而出边为-1,意思是将这个区间上的所有点加1(区间修改).把线段表示为Line[i],其中记录了l,r,h,tag,左右端点,高度,入边还是出边(1或-1) 那么每次区间修改后不为0的区间它的值可能是1,2,3或者是其它数字,这不好统计,可以将它转化一下,0是不是表示没有被覆盖过的地方,我们只要统计0的个数然后用总长减去