LG CF825G Tree-Queries

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转我们可以第一次修改的时候就用第一个黑点建树,可以预处理出$a_i$表示$i$到根节点路径上点编号的最小值我们考虑接下来将一个点$x$变为黑点对其他点的影响:显然$x$变成黑点对它的子树内的点的答案没有影响对子树外的影响:子树外的点可以通过根到达$x$,可以记录一个值$t$表示根能到黑点的所有路径上值的点的最小编号查询时答案就是$\min(a_x,t)$自己画个图就懂了……