SPOJ QTREE

题意

你有一棵$n$个点的树，边有权，有两种操作

• CHANGE x y，表示修改第$x$条边的边权为$y$

• QUERY x y，表示询问点$x$到$y$路径上的边权最大值

BZOJ 2125

题意

给定 $n$个 点仙人掌（每条边只在不超过1个简单环中的无向连通图），$q$ 次询问两点间最短路

边带权

$n,q\le 10000$

BZOJ 1921

题意

给一棵 $n$ 个点的树和长度为 $m$ 的特征串，树的每个节点有一个字符。

求随机两个点形成有向路径上构成的串在特征串里出现次数的期望

仅含小写字母，$n,m\le 5*10^4$