题意： 有一棵树，水源在根节点1，房子在叶子节点。有若干操作，操作可能是歹徒占领或者离开一个房子。我们不想给歹徒供水，可以通过切断边实现（如果某个叶子节点到根节点的路径上有一条边被切掉，那么就不能供水了。）对于每次操作后，问不给所有歹徒供水最少要切多少条边，并且问在切满足前面最小的情况下，最少使得多少个良民受影响。初始没有歹徒。 思路： 我们先考虑第一个问题。容易知道，假设与根相连的有k条边，那么最多只需要切k次，就切断了所有房子的水源。 也就是说，从最少切的次数角度的考虑，切与水源相连的边一定是最优的。 我们可以考虑把树根1去掉，这样得到k棵子树 然后可以预处理出，对于每个叶子节点，其非根的最远祖先是谁，也就是k棵子树的根节点都是 …

题目链接 题意： 一棵树，给出点权，问一条树链上第k大的点权，点权可以动态修改。 思路： 暴力即可orz(数据是真的水啊。 求路径上的点的时候需要用到LCA /* *********************************************** Author :111qqz Created Time :2017年07月31日 星期一 01时12分54秒 File Name :3078.cpp ************************************************ */ #include <cstdio> #include <cstring> #include …

题目链接 题意： 给出一棵树，以及三个点（可能重合），问两两组成的3条路径中，哪2条路径重合部分最长。 思路： LCA还是一下就能想到的，rmq+dfs在线求。 然后我开始分情况讨论，讨论了一年也没讨论完，哭哭 结论是：求出三个lca，并取深度最大的那个，就是我们要的三岔路口K，然后分别求出K到a，b，c三点的路径长度，取最大值+1就是答案。 所以我的问题在于，没有试图往一般性的方向考虑，以为讨论一下就可以了... 这大概就是所谓的猜结论？ 感性的理解的话，LCA越深，意味着另一个点到LCA的距离越远，也就是相交的路径越长 但是我的话，估计还是很难在短短不到一个小时内得出这样一般性的结论orz... 这大概就是数学方面的天赋差距 …

题目链接 题意：求一个BST中某两个节点LCA.... 思路：卧槽。。。竟然求LCA...直接想到的显然是Tarjan的方法或者。。。RMQ+DFS。。。但是感觉。。。leetcode怎么可能考算法。。。。于是想到。。。可以从BST下手。。。 两个节点的LCA的值一定在这两个节点之间。 可以根据这个条件做二分。。。 这道题的收获是。。。不要被已知的东西限制住思路。。。tarjan或者RMQ+DFS显然也能做。。。但是那样的相当于没有用到BST的条件。。。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; …

zoj 3195题目链接 题意：求树上三点的最短距离。。。 思路：两两求，和除以2. 因为忘记初始化p=0..WA了将近两个小时。。。？ 妈的智障。 /* *********************************************** Author :111qqz Created Time :2016年05月21日 星期六 14时44分39秒 File Name :code/zoj/3195.cpp ************************************************ */ #include <cstdio> #include <cstring> #include …

hdu2874题目链接 题意：给一个森林，问两点的最短距离，或者输出两点不联通。 思路：最最重要的一点是:添加虚点！ 最最重要的一点是:添加虚点！ 最最重要的一点是:添加虚点！ 所谓虚点，就是之前假设某个不存在的点，有点类似做辅助线。 通过添加虚点，我们可以把这个森林转化成一棵树。 这样求两点的距离就可以转化成一棵树上的两点的距离。 用dis[u]+dis[v]-2*dis[LCA(u,v)]来求。 dis[i]表示节点i到新的树根节点的距离。 不联通的话就是LCA 为0的情况（0是添加的虚点，作为新的树的根） 具体添加虚点的方法是：森林中每棵树的根连边到虚点上。权值大小随意，因为最后会抵消（？） 为了知道每棵树的根，需要用到并查 …

题目链接 题意：求树上两点的最短距离？ 思路： dis[i]表示点i到根节点的距离，那么任意两点u,v的最短距离d = dis[u]+dis[v]-2*dis[LCA(u,v)]. 只需要求出rmq+dfs的在线方法求出lca(u,v)即可。 /* *********************************************** Author :111qqz Created Time :2016年05月20日 星期五 15时36分47秒 File Name :code/poj/1986.cpp ************************************************ */ #include …

poj1470题目链接 题意：求两点的lca. 思路：dfs+rmq. 读入技巧。 读入比较坑爹。。。 学会了一种新的读入技巧。 scanf("%2s",st); 表示读一个长度为2的字符串。。。读的时候会忽略各种空白字符。 /* *********************************************** Author :111qqz Created Time :2016年05月19日 星期四 15时44分12秒 File Name :code/poj/1470.cpp ************************************************ */ #include …

poj1330题目链接 题意：给出一棵树，求两点的lca. 思路：将lca转化成rmq在线求解。 代码部分参考了：参考代码 感觉实现得很巧妙。。。 把树存成了有向图，dfs遇到的时候一定是第一次遇到，此时更新R. 然后第二次遇到某个点就是在回溯的时候了。 算法学习链接 /* *********************************************** Author :111qqz Created Time :2016年05月19日 星期四 15时05分31秒 File Name :code/poj/1330.cpp ************************************************ …

题目链接 题意：一棵树，给出n-1个边权，然后q组查询，每组查询询问两个点之间的距离。 思路： dfs跑出根到每个点的距离，设为dis[i] 那么u,v两点的距离就是ans = dis[u]+dis[v]-2*dis[lca(u,v)]; 其中lca(u,v)为u,v的最近公共祖先。 这个式子是利用容斥，其实也很直观。。不理解的话画个图就好。 所以终点就是求两个点的LCA. 据说有好多种做法。今天学习了大概是最简单的一种？ 学习链接 //parent为并查集，FIND为并查集的查找操作 //QUERY为询问结点对集合 //TREE为基图有根树 Tarjan(u) visit[u] = true for each (u, v) in …