[題解] P4556 [Vani有約會]雨天的尾巴

[題解] P4556 [Vani有約會]雨天的尾巴

給定一棵樹，有m次修改操作，每次修改 \(( x\) \(y\) \(z )\) 表示 \((x,y)\) 之間的路徑上數值 \(z\) 的個數 \(+1\) 。最後求每個節點上數量最多的數是哪個，如果有多個相同的則輸出較小的。

想到用線段樹合并+樹上差分。由于值存儲在點上，是以在 \(fa[LCA(x,y)],LCA(x,y)\) 上 \(-1\)，在\(x,y\) 上 \(+1\) 即可。

注意線段樹在 \(pushup()\) 時要記得更新是哪個數字數量最多。