原题 P3368 与P3374大同小异，不过树状数组$t$[500002]使用差分进行优化。 差分原理 若有一个数组$a$，则它的差分数组为$t$。 那么$t[i]=a[i]+a[i-1]$ （初始化） 且$a[i]=t[1]+t[2]+···+t[i]$（使用） 当在$a[i]-a[j]$之间进行区间$+v$时， 则$t[i]+=v$，$t[j]-=v$即可。 #include<bits/

原题P3374 $lowbit()$将某数在二进制下的高位$1$去掉，只剩最后一个最低位$1$。 例如 $lowbit(3_{10}(101_{2}))=1_{10}(001_{2})$ 那么，若有一个数组$a[n]$，它的前缀和的树状数组为$t$ 那么 1234567while(j&lt;=n){ t[j]+=a[i]; j+=lowbit(j);//跳转到需要此

使用链式前向星。 DFS函数处理某个点第$2^i$的父亲关系。 lca函数中不要忘了拉平(将a,b点拉至同一深度)最后用倍增算法找父亲。 $\log_{2}{} $的预处理直接使用 $log2()$ 函数即可。 链式前向星的道路数组要开$2$倍。 123456789101112131415161718192021222324252627282930313233343536373839404142