在这里总结一下坑点:
int find_sum_line(int x,int y) {
int ans;
ans = 0;
while(b[x].top!=b[y].top) {
if(b[b[x].top].d<b[b[y].top].d) {
swap(x,y);
}
ans = ans+find_sum(1,b[b[x].top].id,b[x].id);
x = b[b[x].top].fa;
}
if(b[x].d>b[y].d) {
swap(x,y);
}
ans = ans+find_sum(1,b[x].id,b[y].id);
return ans;
}
但是这题是边权转点权,也就是说画个图,就会发现:在上面代码中 while 循环出来以后计算的最后一段路径中终点这个点的点权不能算。

如图,打勾的边是已经计算过权值的边。可以发现图中的情况就是代码中 while 循环外的最后一次处理。看紫色箭头,会发现如果查询 x 到 y,那么其实会多出最上面的一条边,所以我们应该是从 x 的重儿子开始查询,到 y 结束。所以代码应该这么写:
int find_sum_line(int x,int y) {
int ans;
ans = 0;
while(b[x].top!=b[y].top) {
if(b[b[x].top].d<b[b[y].top].d) {
swap(x,y);
}
ans = ans+find_sum(1,b[b[x].top].id,b[x].id);
x = b[b[x].top].fa;
}
if(b[x].d>b[y].d) {
swap(x,y);
}
ans = ans+find_sum(1,b[b[x].mson].id,b[y].id);//注意看这一行有什么改变
return ans;
}
查询最大值,最小值也同理。
2. 在更新取反 tag 的时候,一定不要直接赋 1!因为节点的 tag 可能已经是 1 了,这样再取反一次,就相当于没做任何操作,所以应该是对 tag 进行异或 1 的操作。
3. 注意:节点编号从 0 开始,但是边的编号还是从 1 开始!
4. 注意:边的权值可能为负!也就是说在查找最大值的时候可能也是个负数!所以应该这么写:
线段树内查找:
int find_max(int now,int l,int r) {
if(l<=a[now].l && a[now].r<=r) {
return a[now].maxn;
}
if(a[now].r<l || a[now].l>r) {
return INT_MIN;//注意这里
}
push_down(now);
int ans;
ans = max(find_max(now*2,l,r),find_max(now*2+1,l,r));
push_up(now);
return ans;
}
路径上查找:
int find_max_line(int x,int y) {
int ans;
ans = INT_MIN;//注意这里
while(b[x].top!=b[y].top) {
if(b[b[x].top].d<b[b[y].top].d) {
swap(x,y);
}
ans = max(ans,find_max(1,b[b[x].top].id,b[x].id));
x = b[b[x].top].fa;
}
if(x == y) {
return ans;
}
if(b[x].d>b[y].d) {
swap(x,y);
}
ans = max(ans,find_max(1,b[b[x].mson].id,b[y].id));
return ans;
}
暂时只发现了这么多坑点,如果还有漏的欢迎补充。