http://codeforces.com/contest/1062/problem/E
这题两个难点，第一个是如何快速找到一堆不一定在一起的节点的公共LCA，第二个是如何确定这一堆节点中需要剔除哪一个。
可以先想一下，设原集合的lca为p1，可以取得最优答案的点为x，其他点为vi，那么x一定不在lca(所有的vi)这个点的子树上。这时候，任意一个vi和x的lca都是p1。这时假如维护一个S[l,r]表示[l,r]的公共LCA，根据上面说的性质，这个S序列一定存在一个断点，从这个点开始所有的S==p1,这样的话就可以利用二分查找找到这个断点，可以确定这个断点一定是候选答案之一。另外一个在二分的过程中其实是所有的lca都是基于最左边那个点积累过来的，所以除了分界点之外另外一个可能影响到答案的就是最左边这个点。到这里就算是找到了唯二可能影响答案的点，只需要对他们分别验证就可以了。从dalao的代码里学到了lca也可以作为线段树维护的变量。。。 继续阅读“[线段树+][LCA][dfs序][二分查找][×] codeforces 1062E”
评论区大佬：嗯这个题贪心很明显啦然后nlogn方法也有很多种
http://codeforces.com/contest/980/problem/E
要使得去掉一些点之后剩下的仍然是一棵树，那么去掉的一定是叶子或者某条路上的缩点后相当于叶子的子图。。描述有点困难自行yy。。然后如何选择去掉的点？可以发现，如果i<j，那么去掉j一定不如去掉小于j的所有数，因为2^j=2^(j-1)+2^(j-2)+2^(j-3)+…..+2+1，所以贪心策略就是能不去掉大的就不去，所以要从n-1开始一个一个找（由于k<n所以节点n一定不会被去掉），怎么确定一个点是否能被保留下来，只要确定这个点到最近的保留下来的点的距离小到可以满足去掉k个的要求（想一下，如果这个点离最近的保留点太远了，远到了如果保留这个就没法保证能去掉k个点了，那就肯定不能留了），要保留这个点一定也要保留从这个点往上回溯所有的点，然后就会发现在以root为根的树上，这个01标志是连续的分布的，也就是说有一段1111然后一段000，这样的话就可以二分求分界点，而树上的二分就是lca里的倍增算法了，用倍增法查找就可以在logn时间内找到分界点，找到之后判断是否满足要求，如果满足则把分界点到当前点都标记上保留（话说这样logn不就退化了吗。。。）
wa点是距离的处理和树上倍增往前跳的时候把cur写成了i。。。
ECNU的oj，题很多的样子。。。orz
附上一篇讲树上差分很不错的blog
初学树上差分第一题吧算是，简单的分析一下就可以发现只需要求出来各条边在query中被覆盖到的次数就可以了。利用边的树上差分很容易就能求出来。每次求出lca之后分为两条链，则cf[u]++,cf[v]++,cf[lca]-=2；即可处理完毕。最后推的时候用dfs从下往上推就可以了。
继续阅读“[LCA][树上差分] ECNU OJ 3631 Delivery Service”
https://cn.vjudge.net/problem/POJ-2763
欧拉序线段树裸题，每次要求出两点之间的距离，单点修改，区间查询。
欧拉序其实就是把树拍扁的一种方法。。。对给定的树先求出欧拉序，在欧拉序上通过权值的正负来抵消多余的往返操作，然后每次求得时候先求LCA，再求出lca到两个端点的距离相加即可。有了欧拉序LCA就是一个rmq问题，用线段树做就能实现动态求lca，然后端点距离可以用BIT或者仍然用线段树做，求和最后输出即为答案。
实现的主要注意点是下标之间的关系。。。。这其中欧拉序求出来的点个数是2*n-1，然后BIT上存储的又是2n-2个间隔，然后BIT差分又得考虑左端点往前移动一下。。
自己思路的问题：每次用一个中转节点多连一条线就是等于跳过了一个节点，想到了偶数就是/2，奇数是+1/2，但是没有想到怎么去统计实现。
这个问题最后的答案可以表示为（S+O)/2，其中S是所有点对之间的路径长度之和，O是路径长度为奇数的路径的数量。然后就是如何计算这两个数字的问题。
我以前的理解是求S得用两遍dfs的treeDP，然而这次学到了新操作就是可以分别考察每一条边他被多少对点之间的路径包含了，只需要求出有根树每个点对应的子树中的节点个数即可，S+=(n-subts[x])*subs[x]。
求O的方法就更妙了，画出来一颗有根树就可以发现，两个节点之间的距离奇偶性可以用他们到根节点的奇偶性来表示！（因为树形结构本身对于根节点来说有某种意义上的差分性质emmm），假如两个点到root的路径长度（也就是depth）奇偶性相同，那么他们之间的路径就是偶数的否则是奇的。所以只需要求出来所有的奇数层的节点个数乘以所有的偶数层的节点个数就可以得到O了。
继续阅读“[比赛][TreeDP][树的性质][换轴][统计技巧] codeforces 1060E Sergey and Subway”
