Codechef ：Children Trips/TRIPS（树分块）

传送门

题解：

设一个阀值 k k k，小于 k k k的倍增，大于 k k k的暴力跳，这样的复杂度是 O ( n m k + n k ) O(\frac{nm}{k}+nk) O(knm​+nk)的，取 k = m k=\sqrt{m} k=m ​最优，时间复杂度为 O ( n m ) O(n \sqrt{m}) O(nm ​)。不过空间开不下，要开小一点。

同时有个结论：我们可以从两端跳到lca，最后拼起来，这样就大大降低代码复杂度了。

#include <bits/stdc++.h>using namespace std;typedef pair <int,int> pii;const int RLEN=1<<18|1;inline char nc() {static char ibuf[RLEN],*ib,*ob;(ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));return (ib==ob) ? -1 : *ib++;}inline int rd() {char ch=nc(); int i=0,f=1;while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();}while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();}return i*f;}const int N=1e5+50, S=100, L=18;int n,m,id[N],tot;namespace ori_tree {int fa[N][L+1],val[N],dep[N],d[N];vector <pii> e[N];inline int lca(int x,int y) {if(d[x]<d[y]) swap(x,y);int u=d[x]-d[y];for(int i=0;i<=L;i++) if((u>>i)&1) x=fa[x][i];if(x==y) return x;for(int i=L;i>=0;i--) if(fa[x][i]^fa[y][i]) x=fa[x][i], y=fa[y][i];return fa[x][0];}inline void dfs_pre(int x,int f) {id[x]=++tot; for(auto v:e[x]) if(v.first^f)dfs_pre(v.first,x);}inline void dfs(int x,int f) {fa[x][0]=f; dep[x]=dep[f]+val[x]; d[x]=d[f]+1;for(int i=1;i<=L;i++) fa[x][i]=fa[fa[x][i-1]][i-1];for(auto v:e[x]) if(v.first^f) val[v.first]=v.second, dfs(v.first,x);}inline void init() {n=rd();vector <pair<int,pair<int,int>> > vec;for(int i=1;i<n;i++) {int x=rd(), y=rd(), w=rd();e[x].push_back(pii(y,w));e[y].push_back(pii(x,w));vec.push_back(make_pair(w,pii(x,y)));} dfs_pre(1,0);for(int i=1;i<=n;i++) e[i].clear();for(auto i:vec) {int x=id[i.second.first], y=id[i.second.second], w=i.first;e[x].push_back(pii(y,w));e[y].push_back(pii(x,w));} dfs(1,0);}}using ori_tree::dep;using ori_tree::val;struct Tree {int fa[N],top[N],d[N];int sze[N],son[N];vector <int> chain[N];vector <int> e[N];inline void dfs(int x,int f) {sze[x]=1; d[x]=d[f]+1;for(auto v:e[x]) {dfs(v,x); sze[x]+=sze[v];if(sze[v]>=sze[son[x]]) son[x]=v;}}inline void dfs_top(int x) {chain[top[x]].push_back(x);for(auto v:e[x]) {top[v]=(son[x]==v) ? top[x] : v;dfs_top(v);}}inline void init() {for(int i=2;i<=n;i++) if(fa[i] && fa[i]!=i) e[fa[i]].push_back(i);for(int i=1;i<=n;i++) if(!top[i])dfs(i,0), top[i]=i, dfs_top(i);}inline pii group(int x,int f) {int cnt=0;while(fa[top[x]] && dep[fa[top[x]]]>dep[f]) cnt+=d[x]-d[fa[top[x]]], x=fa[top[x]];int l=0, r=d[x]-d[top[x]];while(l<=r) {int mid=(l+r)>>1, u=chain[top[x]][mid];if(dep[u]>dep[f]) {cnt+=d[x]-d[u];x=u; r=mid-1;} else l=mid+1;} return pii(cnt,dep[x]-dep[f]);}} tr[S+1];inline void dfs_pre(int x,int f) {for(int i=0;i<=S;i++) {if(i<val[x]) tr[i].fa[x]=x;else tr[i].fa[x]=tr[i-val[x]].fa[f];}for(auto v:ori_tree::e[x]) if(v.first^f) dfs_pre(v.first,x);}inline pii group(int x,int f,int step) {if(step<=S) {return tr[step].group(x,f);} else {int cnt=0;while(dep[x]-dep[f]>=step) {int l=x;while(l!=f && tr[S].fa[l]!=l && dep[x]-dep[tr[S].fa[l]]<=step) l=tr[S].fa[l];int res=step-(dep[x]-dep[l]); l=tr[res].fa[l];++cnt; x=l;}return pii(cnt,dep[x]-dep[f]);}}int main() {ori_tree::init();dfs_pre(1,0);for(int i=2;i<=S;i++) tr[i].init();m=rd();for(int i=1;i<=m;i++) {int u=id[rd()], v=id[rd()], l=ori_tree::lca(u,v), step=rd();pii s1=group(u,l,step), s2=group(v,l,step);int ans=s1.first+s2.first, res=s1.second+s2.second;if(res) ans+=1+(res>step);printf("%d\n",ans);}}