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\)