正解:$Kruscal$重构树
解题报告:
发现一个图上搞就很麻烦,考虑变为生成树达到原有效果.
因为在询问的时候是要求走到的点编号尽量小,发现这个时候点的编号就成为限制了,于是不难想到把每条边的边权设为两个端点中的编号$max$,然后建个$Kruscal$重构树.
然后再维护一棵线段树和一个倍增数组,每次查询就是查子树乘积,修改就直接修改就成
$over$
代码咕了$kk$
发现一个图上搞就很麻烦,考虑变为生成树达到原有效果.
因为在询问的时候是要求走到的点编号尽量小,发现这个时候点的编号就成为限制了,于是不难想到把每条边的边权设为两个端点中的编号$max$,然后建个$Kruscal$重构树.
然后再维护一棵线段树和一个倍增数组,每次查询就是查子树乘积,修改就直接修改就成
$over$
代码咕了$kk$