每个点开一个权值线段樹然后用树上差分的方法修改，最后自底向上暴力线段树合并即可
不过空间较大，会\(MLE\)写个内存池就可以了。

这道题调了7个小时也是够了最后只好比着题解做了一遍2333

首先考虑n=2000的情况。因为这是在一条路径上所以可以考虑差分。用a[i][j]表示第i个点中j这种粮食出现的次数加入要在从x到y的路径上加入c这种粮食。将这条路径分为两部分进行差分从x到lca，也就是将a[x][c]++,a[fa[lca]]--从y到son[lca]。就是将a[y][c]++,a[lca]--(详细原因见树上差分)最后dfs一遍，并且在回溯的时候合并一下就行了

那么对于n=100000的数据，只要用线段树合并优化一下就行了也就昰将a数组改为n棵动态开点线段树。合并的时候用线段树合并的板子合并一下就行了