题目大意

给你一颗带点权的树，后面有许多个询问\((u,v)\)，问：

\[\sum_{i=0}^{k-1}dist(u,d_i) \ or \ a_{d_i}\]

\(d\)为\(u\)到\(v\)路径上的点。

---

思考历程&正解

其实我只会我的方法……题解说得太简略了，集训队大佬Infleaking的方法完全听不懂……

首先看到这道题，就立马觉得是神仙题。

但是想到既然是树题，那应该不会太难。

于是我开始试着\(LCT\)建立联系……但是发现这个操作真是太骚了，用\(splay\)真的不好维护。

再想想线段树，但显然线段树还是不行。

到了后来，我突然想到了一个特别傻逼的做法：\(ST\)表！

这道题维护的东西和\(2\)的次幂息息相关，所以再维护的时候，左右区间必须是\(2\)的次幂。

然后想一想怎么做。

首先答案加上\(\frac{k(k+1)}{2}\)，也就是\(dist\)的贡献。接着考虑加没有加上的贡献加上去。

我们可以找到满足\(2^i\leq k\)的最大\(i\)，然后将区间变成两段。

我们维护左边第\(i\)位为\(1\)的个数，记作\(suml\)。

那么答案就是\(suml*2^{i}+左边的答案+右边的答案\)。

由于左边的区间是整的，所以比较好预处理。

首先对于每一位，预处理出一个前缀和，记作\(sum_{i,j}\)。

设\(f_{i,j}\)表示\(i\)到\(2^j-1\)个祖先的答案。转移是显然的，就是将其分成两个长度相等的子区间，左右区间的答案之和，加上左区间的\(i-1\)位为\(1\)的个数乘上\(2^{i-1}\)。

同样地，也求\(g_{i,j}\)，定义和\(f_{i,j}\)相反。

如果路径是一条从后代到祖先的链，可以\(i\)从高到低枚举，如果\(2^i>k\)就加上区间内\(i\)位为\(1\)的个数乘上\(2^i\)；否则就分成两个区间，将左区间的贡献加上之后，后面的答案就跟左区间没有关系了，那么就可以把左区间裁掉，转化成只有右区间的子问题。

现在最重要的问题是如何绕过它们的\(LCA\)。

首先从\(u\)开始跳，如果要往右边跳\(2^i\)步，判断一下是否绕过\(LCA\)。如果没有绕过，就跳过去，跳到不能跳为止。

对于后面的，可以将这样做下去的所有区间的左端点给处理出来。我们考虑倒过来求，也就是从\(v\)开始，向上跳\(lowbit(k)\)位，不要越过\(LCA\)，跳到不能跳为止。用个栈将这些经过的点存起来。

于是就可以很容易地算出后面的这些区间的答案。然后我们就把后面的区间给裁掉了。

于是只剩下了那个长度为\(2\)的次幂的，跨过\(LCA\)的区间。

考虑暴力求。每次分成两段，求出两段的答案之后用和\(f\)一样的方法合并。接着我们就发现，这两段中至少有一段是被处理过的，只需要处理那段没有被处理的就行了。于是递归的过程只有\(\lg\)层。

然后就没有然后了。时间复杂度是优秀的\(O(n\lg n)\)，实际上常数巨大无比……

而且代码实现不容易。

---

代码

using namespace std;#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define N 300010inline int input(){    char ch=getchar();    while (ch<'0' || '9'
        
         >i&1);        dep[x]=dep[fa[x][0]]+1;        f[x][0]=g[x][0]=0;        for (int i=1;1<
         <=dep[x];++i){ fa[x][i]=fa[fa[x][i-1]][i-1]; f[x][i]=f[x][i-1]+f[fa[x][i-1]][i-1]+(sum[x][i-1]-sum[fa[x][i-1]][i-1]<
          
           las) if (ei->to!=fa[x][0]){ fa[ei->to][0]=x; q[++tail]=ei->to; } }}inline int LCA(int u,int v){ if (dep[u]
           
            >=1,++i) if (k&1) u=fa[u][i]; if (u==v) return u; for (int i=18;i>=0;--i) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0];}long long getsum(int u,int v,int lca,int k){ return sum[u][k]+sum[v][k]-sum[lca][k]-sum[fa[lca][0]][k];}long long dfs(int k,int u,int v,int lca){ if (v==lca) return f[u][k]; if (dep[u]-dep[lca]<1<
            
             >1; for (i=29;i>=0 && k;--i) if (k>>i&1){ if (1<
             <=dep[u] && dep[lca]-1<=dep[fa[u][i]]){ ans+=f[u][i]+(sum[u][i]-sum[fa[u][i]][i]<
              
               >j&1){ ++top; w[top]=fa[w[top-1]][j]; } int x=w[top]; for (int j=i-1;j>=0;--j) if (k>>j&1){ --top; ans+=g[w[top]][j]+(sum[w[top]][j]-sum[fa[w[top]][j]][j]<
              
            
           
          
        
       
      
     
    

---

总结

在遇到位运算和各种询问结合起来的问题时，要想到\(ST\)表……