哪家网站建设公司好,免费手机端网站模板下载工具,品牌策划是什么,邢台高端网站建设公司博客园地址
E#xff1a;Tree Queries
思路
当我写完A完这道题后#xff0c;百度了一下#xff0c;发现好像没有人是用类树链剖分来写的#xff0c;都是LCALCALCA#xff0c;于是我就来水一篇树链剖分题解了。
第一步#xff1a;贪心取点
我们可以发现#xff0c;要…博客园地址
ETree Queries
思路
当我写完A完这道题后百度了一下发现好像没有人是用类树链剖分来写的都是LCALCALCA于是我就来水一篇树链剖分题解了。
第一步贪心取点
我们可以发现要使所有的点相连我们必须选择一条最长的路也就是在kkk个点中选择一个与root1root 1root1最远的点这样才有可能满足条件假设起点为s1,tiforiinrange(K)ihavethemax_deps\ \ 1,\ t\ \ i\ for\ i\ in\ range(K)\ i\ have\ the\ max\_deps 1, t i for i in range(K) i have the max_dep
第二步判断我们需要查询的点是否符合条件
我们需要查询的点与我们s−ts- ts−t的路径关系无非就是两种一、在这条最短路径上。二、与路径相连。
接下来我们就可以通过重链的跳转对这kkk个点判断是否符合条件了。
对于情况一我们一定有要满足dep[i]dep[t]andtop[i]top[t]dep[i]\ \ dep[t]\ and\ top[i]\ \ top[t]dep[i] dep[t] and top[i] top[t]这样判断就有iii点一定在我们的路径上。
对于情况二我们只需要满足dep[fa[i]]dep[t]1andtop[fa[i]]top[t]dep[fa[i]] dep[t] 1\ and\ top[fa[i]] top[t]dep[fa[i]]dep[t]1 and top[fa[i]]top[t]这里可能需要解释一下dep[fa]dep[t]1dep[fa] dep[t] 1dep[fa]dep[t]1是怎么来的了当我们的点直接与ttt相连时就是这种情况。
第三不跳跃整条重链到上面一条重链上去。
接下来我们跳转ttt有tfa[top[t]]t fa[top[t]]tfa[top[t]]因为我们在上面的操作中已经判断完了从top[t]−ttop[t] - ttop[t]−t上满足要求的点了跳转完后我们就是再进行步骤二直到跳跃到点111停止操作判断我们最后的答案。
代码
#include bits/stdc.husing namespace std;typedef long long ll;inline ll read() {ll f 1, x 0;char c getchar();while(c 0 || c 9) {if(c -) f -1;c getchar();} while(c 0 c 9) {x (x 1) (x 3) (c ^ 48);c getchar();}return f * x;
}const int N 2e5 10;vectorint G[N];
int top[N], fa[N], sz[N], dep[N], son[N];
int a[N], visit[N], n, m;void dfs1(int rt, int f) {fa[rt] f, sz[rt] 1;dep[rt] dep[f] 1;for(int i : G[rt]) {if(i f) continue;dfs1(i, rt);sz[rt] sz[i];if(!son[rt] || sz[i] sz[son[rt]])son[rt] i;}
}void dfs2(int rt, int t) {top[rt] t;if(!son[rt]) return ;dfs2(son[rt], t);for(int i : G[rt]) {if(i fa[rt] || i son[rt]) continue;dfs2(i, i);}
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);n read(), m read();for(int i 1; i n; i) {int x read(), y read();G[x].push_back(y);G[y].push_back(x);}dfs1(1, 0);dfs2(1, 1);for(int i 1; i m; i) {a[0] read();int max_id 0, sum 0;for(int j 1; j a[0]; j) {visit[j] 0;a[j] read();if(dep[a[j]] dep[max_id]) max_id a[j];}while(top[max_id] ! 1) {for(int j 1; j a[0]; j)if((top[a[j]] top[max_id] dep[a[j]] dep[max_id]) || (top[fa[a[j]]] top[max_id] dep[a[j]] dep[max_id] 1))if(!visit[j]) {sum;visit[j] 1;}max_id fa[top[max_id]];}for(int j 1; j a[0]; j)if((top[a[j]] top[max_id] dep[a[j]] dep[max_id]) || (top[fa[a[j]]] top[max_id] dep[a[j]] dep[max_id] 1))if(!visit[j]) {sum;visit[j] 1;}puts(sum a[0] ? YES : NO);}return 0;
}
