做网站北京公司,自助下单网站怎么做,上海市建设安全协会网站特种工,东莞市58同城招聘网最新招聘正题
题目链接:http://noi.ac/problem/2266 题目大意
给出nnn个点的一棵树#xff0c;有一些边上有中转站#xff08;边长度为222#xff0c;中间有一个中转站#xff09;#xff0c;否则就是边长为111。 mmm次询问一个东西从xxx出发走到yyy#xff0c;每隔kkk步中转站…正题
题目链接:http://noi.ac/problem/2266 题目大意
给出nnn个点的一棵树有一些边上有中转站边长度为222中间有一个中转站否则就是边长为111。
mmm次询问一个东西从xxx出发走到yyy每隔kkk步中转站会关闭一次kkk的倍数步走完后不能在中转站上。求在关闭多少次以内可以到达
1≤n,m≤1051\leq n,m\leq 10^51≤n,m≤105 解题思路
发现最多只需要走2n2n2n步然后每隔kkk步关闭一次所以可以考虑根号分治。
先处理好总的倍增数组后面求LCALCALCA和跳链要用。
对于k1k1k1的询问就看一下中间有没有中转站如果有就是−1-1−1否则就是距离
对于k≤nk\leq \sqrt nk≤n的询问我们对于每个kkk都进行一次预处理处理每个周期每个点往上走能走到哪里。然后再处理一个倍增数组然后询问的时候就在上面跳就好了
对于knk\sqrt nkn的询问直接每次暴力跳kkk步如果是中转站就跳k−1k-1k−1步然后一直跳到LCALCALCA处
时间复杂度O(nnlogn)O(n\sqrt n\log n)O(nnlogn)调一下块的大小就能过了 code
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const int N2e510,T17;
struct edge{int to,next;
}a[N1];
struct node{int x,y,k,id;
}q[N];
int n,m,Q,tot,num,ans[N],ls[N],dep[N],sd[N];
int g[N][100],f[N][T1],h[N][T1];
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
bool cmp(node x,node y)
{return x.ky.k;}
void dfs(int x,int fa){g[x][0]x;sd[x]sd[fa](xn);f[x][0]fa;dep[x]dep[fa]1;for(int i1;iQ;i)g[x][i]g[fa][i-1];for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;dfs(y,x);}return;
}
int LCA(int x,int y){if(dep[x]dep[y])swap(x,y);for(int iT;i0;i--)if(dep[f[y][i]]dep[x])yf[y][i];if(xy)return x;for(int iT;i0;i--)if(f[x][i]!f[y][i])xf[x][i],yf[y][i];return f[x][0];
}
void calc(int x,int fa,int k){if(g[x][k]n)h[x][0]g[x][k-1];else h[x][0]g[x][k];for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;calc(y,x,k);}return;
}
int query(int x,int y,int k){int pLCA(x,y),ans0;for(int iT;i0;i--){if(dep[h[x][i]]dep[p])xh[x][i],ans(1i);if(dep[h[y][i]]dep[p])yh[y][i],ans(1i);}if(x!y){int disdep[x]dep[y]-2*dep[p];if(dis0disk)ans;else if(disk) ans2;}return ans;
}
int getf(int x,int k){for(int i0;iT;i)if((ki)1)xf[x][i];return x;
}
int solve(int x,int y,int k){int pLCA(x,y),ans0;while(dep[x]dep[p]){int zgetf(x,k-1),t;if(f[z][0]n)tz;else tf[z][0];if(dep[t]dep[p])xt,ans;else break;}while(dep[y]dep[p]){int zgetf(y,k-1),t;if(f[z][0]n)tz;else tf[z][0];if(dep[t]dep[p])yt,ans;else break;}if(x!y){int disdep[x]dep[y]-2*dep[p];if(dis0disk)ans;else if(disk) ans2;}return ans;
}
int main()
{scanf(%d,n);numn;for(int i1;in;i){int x,y,w;scanf(%d%d%d,x,y,w);if(w1)addl(x,y),addl(y,x);else{num;addl(x,num);addl(num,y);addl(y,num);addl(num,x);}}Qsqrt(n);if(Q70)Q70;scanf(%d,m);for(int i1;im;i){scanf(%d%d%d,q[i].x,q[i].y,q[i].k);q[i].idi;}sort(q1,q1m,cmp);dfs(1,0);for(int j1;jT;j)for(int i1;inum;i)f[i][j]f[f[i][j-1]][j-1];int l1,r1;for(;rmq[r].kQ;r,lr){while(rmq[r].kq[r1].k)r;if(q[r].k1){for(int il;ir;i){int xq[i].x,yq[i].y,lcaLCA(x,y);if(sd[x]sd[y]-2*sd[lca])ans[q[i].id]-1;else ans[q[i].id]dep[x]dep[y]-2*dep[lca];}continue;}calc(1,1,q[r].k);for(int j1;jT;j)for(int i1;inum;i)h[i][j]h[h[i][j-1]][j-1];for(int il;ir;i)ans[q[i].id]query(q[i].x,q[i].y,q[i].k);}for(int ir;im;i)ans[q[i].id]solve(q[i].x,q[i].y,q[i].k);for(int i1;im;i)printf(%d\n,ans[i]);return 0;
}
