题意：
给出一棵树，两种操作：
1.求出a到b的距离；
2.修改某一条边的权值。
思路：
可以用树链刨分（我不会
首先，求a到b的距离，因为有很多组询问，所以必须得用lca解决
ans = dis[a] + dis[b] – 2 * dis[lca(a,b)] dis是这个点到根的距离
修改某一条边的权值这里比较麻烦，因为修改了某一条边的权值之后，可能有很多个点的距离都会被影响，但是暴力修改的话，会tle
所以就想到用dfs序处理，每一个点的dfs序的区间控制这个点以及它的子树上的所有点
当某一条边被修改时，那么这条边所连接的时间戳比较大的点及其它的子树的所有点的这个区间都会被影响，那么就直接修改区间
查询的时候，只需要查询3个点，a , b , lca(a,b)，所以这就是树状数组的区间修改，单点查询，不懂话欢迎看我的算法学习中的这部分😅
poj毒瘤，所以只能用链式前向星
边数是点数 * 2，又因为这个错误re了无数发🤣
代码：
Original: https://www.cnblogs.com/kickit/p/9173022.html
Author: qrfkickit
Title: poj 2763 Housewife Wind
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604629/
转载文章受原作者版权保护。转载请注明原作者出处！