https://qoj.ac/problem/5020
神秘 RE 害人不浅。
记 \(z=\text{lca}(x,y)\)，把链拆成 \(z,x\to z,y\to z\) 三个部分。
第一个部分相当于子任务 2（\(x=y\)），树上距离 \(\le k\) 的点数，点分治即可 \(O(n\log n)\)。
第二个和第三个本质相同，考虑在 \(z\to x\) 路径上会新加入哪些合法的点。记 \(S\) 为路径上的点集（不包括 \(z\)，他的贡献在第一个部分）。
记 \(f_{u,i}\) 为 \(u\) 子树内，距离 \(u\) 恰好等于 \(i\) 的点数，容易发现这一部分的贡献为 \(\sum_{p\in S}f_{p,k}\)，即向下走的过程中新的合法点为子树内距离恰好为 \(k\) 的点的和。
\(f_{u,i}\) 是长链剖分的形式，对 \(k\) 从小到大离线考虑，定义新的 \(f_u\) 为原先的 \(f_{u,k}\)，发现 \(k\) 自增一在链上相当于向下偏移了一，每次把轻儿子的 \(f_{u,k}\) 合并到父亲的链上，这样总合并次数为 \(O(n)\)。
查询的时候暴力向上跳长链，长剖到根的轻边数量为 \(O(\sqrt n)\)，需要支持求长链的前缀和。
\(n\) 次单点修改，\(q\sqrt n\) 次求前缀和，使用分块平衡复杂度得到 \(O(n\sqrt n)\)。
如果是重链剖分的话总合并次数和查询次数均为 \(O(n\log n)\)，使用 BIT 复杂度为 \(O(n\log^2n)\)。
感觉第一个部分也能这么算，需要维护深度差为二的前缀和。
但是这里的 BIT 大小为最深路径长度，我不会算重剖下链头最深路径长度总和的上界，doqe 说今年集训队论文有提到这个，畏惧。
https://qoj.ac/submission/1848804
代码
#include<bits/stdc++.h>
constexpr int rSiz=1<<21;
char rBuf[rSiz],*p1=rBuf,*p2=rBuf;
#define gc() (p1==p2&&(p2=(p1=rBuf)+fread(rBuf,1,rSiz,stdin),p1==p2)?EOF:*p1++)
template<class T>void rd(T&x){char ch=gc();for(;ch<'0'||ch>'9';ch=gc());for(x=0;ch>='0'&&ch<='9';ch=gc())x=(x<<1)+(x<<3)+(ch^48);
}
constexpr int _=2e5+5;
int n,q;
std::vector<int>e[_];
int dep[_],mxd[_],son[_],fat[_];
void dfs1(int u,int fa){dep[u]=dep[fat[u]=fa]+1;for(int v:e[u])if(v^fa){dfs1(v,u);if(mxd[v]>mxd[son[u]])son[u]=v;}mxd[u]=mxd[son[u]]+1;
}
int top[_],end[_],w[_];
void dfs2(int u,int rt){top[u]=rt;end[rt]=u;if(u==rt)w[u]=1;else w[u]=w[fat[u]]+1;if(son[u])dfs2(son[u],rt);for(int v:e[u])if(v^fat[u]&&v^son[u])dfs2(v,v);
}
namespace YJK{int dfn[_],nfd[_],dfscnt,siz[_],lg[_],a[19][_];void dfs3(int u){nfd[dfn[u]=++dfscnt]=u;siz[u]=1;for(int v:e[u])if(v^fat[u])dfs3(v),siz[u]+=siz[v];}int argMin(int x,int y){return dep[x]<dep[y]?x:y;}void init(){dfscnt=0;lg[0]=-1;dfs3(1);for(int i=1;i<=n;++i){lg[i]=lg[i>>1]+1;a[0][i]=fat[nfd[i]];}for(int k=1;k<19;++k)for(int i=1;i+(1<<k)-1<=n;++i)a[k][i]=argMin(a[k-1][i],a[k-1][i+(1<<(k-1))]);}int lca(int x,int y){if(x==y)return x;x=dfn[x],y=dfn[y];if(x>y)std::swap(x,y);++x;int k=lg[y-x+1];return argMin(a[k][x],a[k][y-(1<<k)+1]);}
};
using YJK::lca;
int dis(int x,int y){return dep[x]+dep[y]-2*dep[lca(x,y)];
}
namespace JZQ{bool vis[_],ok;std::vector<int>c;int siz[_],mxs[_],tot,G;void dfs3(int u,int fa){siz[u]=1;mxs[u]=0;if(ok)c.push_back(u);for(int v:e[u])if(!vis[v]&&v^fa){dfs3(v,u);siz[u]+=siz[v];mxs[u]=std::max(mxs[u],siz[v]);}mxs[u]=std::max(mxs[u],tot-siz[u]);if(mxs[u]<mxs[G])G=u;}int fah[_];std::vector<int>d[_][2];void dfs4(int u,int fa){ok=0;G=0;dfs3(u,0);u=G;vis[u]=1;fah[u]=fa;c.clear();d[u][0].resize(tot+5,0);d[u][1].resize(tot+5,0);ok=1;dfs3(u,0);for(int v:c){++d[u][0][dis(v,u)];if(fa)++d[u][1][dis(v,fa)];}for(int o=0;o<2;++o)for(int i=1;i<(int)d[u][o].size();++i)d[u][o][i]+=d[u][o][i-1];for(int v:e[u])if(!vis[v])tot=siz[v],dfs4(v,u);}int Ask(int x,int k){int val=0;for(int u=x;u;u=fah[u]){int p=std::min(k-dis(u,x),(int)d[u][0].size()-1);if(p>=0)val+=d[u][0][p];if(fah[u]){p=std::min(k-dis(fah[u],x),(int)d[u][1].size()-1);if(p>=0)val-=d[u][1][p];}}return val;}void init(){tot=n;mxs[0]=1e9;dfs4(1,0);}
};
std::vector<std::pair<int,std::pair<int,int> > >b[_];
std::vector<int>g;
int B,L[_],R[_],D[_];
struct block{int m;std::vector<int>t;std::vector<std::vector<int> >s;void Chg(int x,int v){for(int i=x;i<=R[D[x]];++i)s[D[x]][i-L[D[x]]]+=v;for(int i=D[x]+1;i<=D[m];++i)t[i]+=v;}int Qry(int x){x=std::min(x,m);if(!x)return 0;return t[D[x]]+s[D[x]][x-L[D[x]]];}int Qry(int l,int r){return Qry(r)-Qry(l-1);}void init(int x){m=x;t.resize(D[x]+5,0);s.resize(D[x]+5);for(int i=0;i<=D[x];++i)s[i].resize(B+5,0);}
}f[_];
int calc(int x,int y,int k){int val=0;for(;top[x]^top[y];){if(dep[top[x]]<dep[top[y]])std::swap(x,y);val+=f[top[x]].Qry(k+1,w[x]+k);x=fat[top[x]];}if(dep[x]>dep[y])std::swap(x,y);val+=f[top[x]].Qry(w[x]+k+1,w[y]+k);return val;
}
int ans[_];
int main(){rd(n);B=400;for(int i=1,l=1,r=B;l<=n;l=r+1,r=std::min(r+B,n),++i){L[i]=l;R[i]=r;for(int j=l;j<=r;++j)D[j]=i;}for(int i=1,u,v;i<n;++i){rd(u),rd(v);e[u].push_back(v);e[v].push_back(u);}dfs1(1,0);dfs2(1,1);for(int u=1;u<=n;++u){if(son[fat[u]]^u){f[u].init(w[end[u]]);for(int v=u;v;v=son[v])f[u].Chg(w[v],1);if(u>1)g.push_back(u);}}std::sort(g.begin(),g.end(),[](int x,int y){return mxd[x]>mxd[y];});YJK::init();JZQ::init();rd(q);for(int i=1,x,y,z,k;i<=q;++i){rd(x),rd(y),rd(k);b[k].push_back({i,{x,y}});ans[i]=JZQ::Ask(lca(x,y),k);}for(int k=0;k<n;){for(auto pr:b[k]){int x=pr.second.first,y=pr.second.second;ans[pr.first]+=calc(x,y,k);}++k;for(;!g.empty()&&mxd[g.back()]<k;g.pop_back());for(int u:g){int v=f[u].Qry(k,k),p=top[fat[u]];f[p].Chg(dep[u]-dep[p]+k,v);}}for(int i=1;i<=q;++i)printf("%d\n",ans[i]);
}