关于序列问题上树

为什么区间数颜色数可以做到 $n\log n$，但是链上数颜色貌似只能做到 $n\sqrt{n}$。