1. 点的差分
求路径 u - v 上的点被经过的次数。
cnt [ x ] 代表点 x 经过的次数。
核心代码:
cnt[n]++;
cnt[v]++;
cnt[lca]--;
cnt[fa[lca]]--;
2. 边的差分
求 u - v 路径上每一条边经过的次数。
cnt [ x ]:代表 x 向上的边经过的次数。
核心代码:
cnt[u]++;
cnt[v]++;
cnt[lca]-=2;
标签:cnt,++,差分,次数,lca,--,树上
From: https://blog.csdn.net/Ryan_hsMax/article/details/142654332