Mayflyyh
Mayflyyh
MayFlyyh's Blog

LCA
文章归档

POJ 3417 Network

题意:给你一颗N个节点树,再给你M条新边(保证不与树边重复)。现在求剪短一条树边和任意M边中的一条边,能将树分成两个联通块的方案 > N (1 ≤ N ≤ 100 000), M (1 ≤ M ≤ 100 000) 一开始想的:暴力,N*M然后检验。。 然后想到树形DP,能不能按照每个节点剪掉它与…

   145   2018-08-11 去围观

题解 LuoGu P2420 让我们异或吧

LuoGu P2420 让我们异或吧 题目描述 异或是一种神奇的运算,大部分人把它总结成不进位加法. 在生活中…xor运算也很常见。比如,对于一个问题的回答,是为1,否为0.那么: 好了,现在我们来制造和处理一些复杂的情况。比如我们将给出一颗树,它很高兴…

   101   2018-03-17 去围观

题解 LuoGu P2279 消防局的设立

LuoGu P2279 消防局的设立 题目描述 2020年,人类在火星上建立了一个庞大的基地群,总共有n个基地。起初为了节约材料,人类只修建了n-1条道路来连接这些基地,并且每两个基地都能够通过道路到达,所以所有的基地形成了一个巨大的树状结构。如果基地A到基地B至…

   163   2018-03-17 去围观

题解 Luogu P1967 货车运输

题解 Luogu P1967 货车运输 题目描述 A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。 输入文件第…

   175   2018-02-24 去围观

LCA学习笔记

建树 结点数为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]) con…

   172   2018-02-13 去围观