Posts tagged with LCA


LCA 好题! 这道题我暂时只知道用Tarjan的解法。 Tarjan解法完美地运用了Tarjan的核心原理与性质: 深度优先搜索时的向下局部性。自己乱取得,蛤蛤蛤 题意: 给你一棵树,每个节点有一个权值。给你很多个询问,每个询问两个点。要你在给定点的树链上找到有序的最大差值。 思路: 首先考虑分治。设树链 u -> lca -> v 答案无非只有三种情况: u…

昨晚疯狂掉分的第四题,其实比第三题还简单…… 搞不懂cf又不按套路出牌了……先是来一个巨简单的,让每个人都不得不去签到,随后是坑题,然后是压轴题,再然后才是普通题,难题…… 题意: 给你一棵树,每次询问3个点,要你求出3个点两两构成的路径中选出两条,使得他们相交的长度最长。 思路: 这道题并不难,先求出LCA,再分类讨论一下即可,但是但是但是但是!!分类的情况会非常非常多,就图而言就有4种,还要考虑各自的位置。 必须得总结一下,不然跟着写会疯掉。 考虑让每个点为两条路径的相交点,…

本文起始请听我先说一句 ***的HDU4429!!!!!!!!! 这道题是我想自己写个LCA专题的起因。你要是去google题解的话全是用暴力求得。不知道为什么,你写题写到后面你会发现题解的代码全特么一个样子。说明他们很可能是不太懂,然后从某一个博客中看了代码,照样子写了,然后A了就得过且过的样子。当然我是不喜欢这样的。然后我就想用下tarjan求LCA,顺便复习一下算法。 结果!!!! WA了两天!!!! 忍无可忍交了一发暴力,60ms 秒过!!!!!玛德,这题绝对有问题!!!!我现在就要开个专题先验证一下我自己的算法。 先是放一下我对这题的题解 HDU 4429 Split…

换了个姿势还是上了HDU 据学长给我的图论题库来说 lca问题也写完了 这题几乎还是模板题 只不过是多了个 判断是否在同一棵树上 用了点小技巧 再Tarjan时 把根节点也传上去 如果得结果时根节点不同就跳过 另外这题灰常容易爆内存 稍微改了一下用 C++水过去了 然而G++还是爆……………… AC Code #include <iostream> #include <cstdio&…