LCATag:

Rikka with Intersection of Paths 题解

MayFlyyh | LCA, 容斥, 组合 | 2020-10-07
Rikka with Intersection of Paths 题解 Rikka有一棵包含$ n(1≤n≤3×10^5) $个节点的树 $T$,节点编号为 $1$ 到 $n$ 。树上也标记了$ m (2≤m≤3×10^5)$ 条简单路径,第i条路径连接 $x_i$ 和 $y_i$ $ (1≤x_i,y_i≤n)$,这些路径可能会有重复的。如果要在其中选择 $k$ 条路径,要求这 $k$ 条路径至少有一个公共点,计算有多少种选择方案。输出其... [阅读全文]

异象石 题解

MayFlyyh | LCA | 2020-10-07
异象石 题解
异象石 题解 在 Adera 的异时空中有一张地图。这张地图上有 N 个点,有 N−1 条双向边把它们连通起来。起初地图上没有任何异象石,在接下来的 M个时刻中,每个时刻会发生以下三种类型的事件之一: 地图的某个点上出现了异象石(已经出现的不会再次出现); 地图某个点上的异象石被摧毁(不会摧毁没有异象石的点); 向玩家询问使所有异... [阅读全文]
ė 6 没有评论 0

POJ 3417 Network

MayFlyyh | LCA | 2018-08-11
题意:给你一颗N个节点树,再给你M条新边(保证不与树边重复)。现在求剪短一条树边和任意M边中的一条边,能将树分成两个联通块的方案 > N (1 ≤ N ≤ 100 000), M (1 ≤ M ≤ 100 000) 一开始想的:暴力,N*M然后检验。。 然后想到树形DP,能不能按照每个节点剪掉它与它父亲节点的树边思考 剪掉这条树边,树边部分肯定不与大树相连接 分类讨论一下... [阅读全文]
ė 6 没有评论 0

题解 LuoGu P2420 让我们异或吧

MayFlyyh | LCA | 2018-03-17
LuoGu P2420 让我们异或吧 题目描述 异或是一种神奇的运算,大部分人把它总结成不进位加法. 在生活中…xor运算也很常见。比如,对于一个问题的回答,是为1,否为0.那么: 好了,现在我们来制造和处理一些复杂的情况。比如我们将给出一颗树,它很高兴自己有N个结点。树的每条边上有一个权值。我们要进行M次询问,对于每次询问,我们想... [阅读全文]
ė 6 没有评论 0

题解 LuoGu P2279 消防局的设立

MayFlyyh | DP, LCA | 2018-03-17
题解 LuoGu P2279 消防局的设立
LuoGu P2279 消防局的设立 题目描述 2020年,人类在火星上建立了一个庞大的基地群,总共有n个基地。起初为了节约材料,人类只修建了n-1条道路来连接这些基地,并且每两个基地都能够通过道路到达,所以所有的基地形成了一个巨大的树状结构。如果基地A到基地B至少要经过d条道路的话,我们称基地A到基地B的距离为d。 由于火星上非常干燥,经... [阅读全文]

题解 Luogu P1967 货车运输

MayFlyyh | LCA, 倍增 | 2018-02-24
题解 Luogu P1967 货车运输 题目描述 A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。 输入文件第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道 路。 接下... [阅读全文]

LCA学习笔记

MayFlyyh | LCA, 学习笔记, 未分类 | 2018-02-13
建树 结点数为N 边数为M 根节点S log2N 为树的最大深度 int log2N=log(1.0*N)/log(2.0)+0.5; 通过DFS预处理出树与深度 inline void dfs(int x,int f){ V[x]=1; D[x]=D[f]+1; F[X][0]=f; for(int i=Last[x];i;i=e[i].next){ if(V[x]) continue; dfs(e[i].to,x); } } 朴素算法 DFS 复杂度O(N) 求LCA(A,B)... [阅读全文]
Ɣ回顶部