[CC-TRIPS]Children Trips

题目大意：

\(n(n\le10^5)\)座城市构成一棵树，且树上的每条边的长度\(l_i\)满足\(1\le l_i\le 2\)。\(m(m\le10^5)\)个询问，每次询问从\(u\)到\(v\)，每天最多开\(p\)公里，至少需要多少天可以到达。注意，晚上必须停留在某座城市，而不能将车停在某两座城市之间。

思路：

当\(p\le100\)时，倍增预处理每个点向上跳到哪些位置，否则直接暴力跳。

源代码：

#include<cstdio>#include<cctype>#include<vector>#include<cstring>#include<algorithm>inline int getint() {register char ch;while(!isdigit(ch=getchar()));register int x=ch^'0';while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');return x;}const int N=1e5+1,logN=17,M=1e5,B=100;struct Edge {int to,w;};std::vector<Edge> e[N];inline void add_edge(const int &u,const int &v,const int &w) {e[u].push_back((Edge){v,w});e[v].push_back((Edge){u,w});}struct Query {int u,v,p,id;bool operator < (const Query &rhs) const {return p<rhs.p;}};Query q[M];int ans[M];int dep[N],dis[N],anc[N][logN],top[N][logN];inline int lg2(const float &x) {return ((unsigned&)x>>23&255)-127;}void dfs(const int &x,const int &par) {anc[x][0]=par;dep[x]=dep[par]+1;for(register int i=1;i<=lg2(dep[x]);i++) {anc[x][i]=anc[anc[x][i-1]][i-1];}for(auto &j:e[x]) {const int &y=j.to;if(y==par) continue;dis[y]=dis[x]+j.w;dfs(y,x);}}inline int lca(int x,int y) {if(dep[x]<dep[y]) std::swap(x,y);for(register int i=lg2(dep[x]-dep[y]);i>=0;i--) {if(dep[anc[x][i]]>=dep[y]) {x=anc[x][i];}}for(register int i=lg2(dep[x]);i>=0;i--) {if(anc[x][i]!=anc[y][i]) {x=anc[x][i];y=anc[y][i];}}return x==y?x:anc[x][0];}inline int dist(const int &x,const int &y) {const int z=lca(x,y);return dis[x]+dis[y]-dis[z]*2;}inline int jump(int x,int step) {for(register int i=lg2(dep[x]);i>=0;i--) {if(dis[x]-dis[anc[x][i]]<=step) {step-=dis[x]-dis[anc[x][i]];x=anc[x][i];}}return x;}int main() {const int n=getint();for(register int i=1;i<n;i++) {const int u=getint(),v=getint(),w=getint();add_edge(u,v,w);}dfs(1,0);const int m=getint();for(register int i=0;i<m;i++) {q[i].u=getint();q[i].v=getint();q[i].p=getint();q[i].id=i;}std::sort(&q[0],&q[m]);for(register int l=0,r=0;l<m;l=r) {while(r<m&&q[r].p==q[l].p) r++;const int &step=q[l].p;if(step<=B) {memset(top,0,sizeof top);for(register int i=1;i<=n;i++) {top[i][0]=jump(i,step);}for(register int j=1;j<=lg2(n);j++) {for(register int i=1;i<=n;i++) {top[i][j]=top[top[i][j-1]][j-1];}}for(register int i=l;i<r;i++) {int x=q[i].u,y=q[i].v;const int z=lca(x,y);int &ans=::ans[q[i].id];for(register int i=lg2(dep[x]);i>=0;i--) {if(dep[top[x][i]]>dep[z]) {x=top[x][i];ans+=1<<i;}}for(register int i=lg2(dep[y]);i>=0;i--) {if(dep[top[y][i]]>dep[z]) {y=top[y][i];ans+=1<<i;}}if(dist(x,y)>0) ans++;if(dist(x,y)>step) ans++;}} else {for(register int i=l;i<r;i++) {int x=q[i].u,y=q[i].v,t;const int z=lca(x,y);int &ans=::ans[q[i].id];for(t=jump(x,step);dep[t]>dep[z];t=jump(x,step)) {ans++;x=t;}for(t=jump(y,step);dep[t]>dep[z];t=jump(y,step)) {ans++;y=t;}if(dist(x,y)>0) ans++;if(dist(x,y)>step) ans++;}}}for(register int i=0;i<m;i++) {printf("%d\n",ans[i]);}return 0;}