题目链接

题意：

一棵树，给出点权，问一条树链上第k大的点权，点权可以动态修改。

思路：

暴力即可orz(数据是真的水啊。

求路径上的点的时候需要用到LCA

/* ***********************************************
Author :111qqz
Created Time :2017年07月31日 星期一 01时12分54秒
File Name :3078.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3 …

题目链接

题意：

给出一棵树，以及三个点（可能重合），问两两组成的3条路径中，哪2条路径重合部分最长。

思路：

LCA还是一下就能想到的，rmq+dfs在线求。

然后我开始分情况讨论，讨论了一年也没讨论完，哭哭

题目链接

题意：定义一个函数F．．

For exampe: _F_(_babbabbababbab_, _babb_) = 6. The list of pairs is as follows:

(1, 4), (4, 7), (9, 12)

Its continuous sequences are:

  * 

(1, 4)

  * 

(4, 7)

  * 

(9, 12)

  * 

(1, 4), (4, 7)

  * 

(4, 7), (9, 12)

  * 

(1, 4), (4, 7), (9, 12)

erfen

hdu 4123 题目链接

题意：一棵树，定义d[i]为点i到树上某点的最大距离。。。给出若干查询，每个查询一个x,问最多能有多少点满足这些点中，最大的d与最小的d的差小于等于x.要求这些点的编号必须是连续的。

zoj 3195题目链接 题意：求树上三点的最短距离。。。 思路：两两求，和除以2. 因为忘记初始化p=0..WA了将近两个小时。。。？ 妈的智障。

/* ***********************************************
Author :111qqz
Created Time :2016年05月21日 星期六 14时44分39秒
File Name :code/zoj/3195.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3 …

hdu2874题目链接

题意：给一个森林，问两点的最短距离，或者输出两点不联通。

思路：最最重要的一点是:添加虚点！

最最重要的一点是:添加虚点！

最最重要的一点是:添加虚点！

题目链接 题意：求树上两点的最短距离？ 思路： dis[i]表示点i到根节点的距离，那么任意两点u,v的最短距离d = dis[u]+dis[v]-2*dis[LCA(u,v)]. 只需要求出rmq+dfs的在线方法求出lca(u,v)即可。

hdu 3530题目链接

题意：给出n个数，m,k，问最大的j-i+1,使得【i,j】间的最大值与最小值的差属于[m,k] 思路：rmq+尺取。 2A.

poj1470题目链接

题意：求两点的lca. 思路：dfs+rmq. 读入技巧。 读入比较坑爹。。。 学会了一种新的读入技巧。

scanf("%2s",st);

表示读一个长度为2的字符串。。。读的时候会忽略各种空白字符。

poj1330题目链接

题意：给出一棵树，求两点的lca. 思路：将lca转化成rmq在线求解。

代码部分参考了：参考代码

感觉实现得很巧妙。。。 把树存成了有向图，dfs遇到的时候一定是第一次遇到，此时更新R. 然后第二次遇到某个点就是在回溯的时候了。