LCATag:

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 消防局的设立 > 题目描述 > 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... [阅读全文]
Ɣ回顶部