起因是发现自己脑子并不好使老忘。
DSU on tree
先树剖。
Func Modify = [] (int cur ,int op) -> void {
if (op) max = std :: max (max ,tr.Query (a[cur]).first) ,tr.Insert (a[cur] ,0) ;
else tr.Del (a[cur]) ;
for (int i = head[cur] ; i ; i = e[i].nxt) {
int nex = e[i].to ;
if (nex == fa[cur] || nex == son) continue ;
Modify (nex ,op) ;
}
} ;
Func Solve = [] (int cur ,int op) -> void {
for (int i = head[cur] ; i ; i = e[i].nxt) {
int nex = e[i].to ;
if (nex == fa[cur] || nex == hson[cur]) continue ;
Solve (nex ,0) ;
} if (hson[cur]) Solve (hson[cur] ,1) ,son = hson[cur] ;
Modify (cur ,1) ,ans2[cur] = max ,son = 0 ;
if (!op) Modify (cur ,0) ,max = 0 ;
} ;