成都建网站多少钱,郴州网站建设哪家好,wordpress加logo,制作网页的三大技术是什么正题
luogu 5838 题目大意
给你一棵树#xff0c;和若干查询#xff0c;每次查询一条路径上是否有点的权值为x 解题思路
离线处理#xff0c;每次将树上权值为x的点附上1的值#xff0c;然后询问就是求和#xff0c;查询完后清零 代码
#includecstdio
#includ…正题
luogu 5838 题目大意
给你一棵树和若干查询每次查询一条路径上是否有点的权值为x 解题思路
离线处理每次将树上权值为x的点附上1的值然后询问就是求和查询完后清零 代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 100010
using namespace std;
int n, m, x, y, w, g, gg, tot, s[N], v[N], hs[N], fa[N], ans[N], dep[N], anc[N], head[N];
struct rec
{int to, next;
}a[N1];
struct node
{int x, v;bool operator (const node b) const{return x b.x;}
}pt[N];
struct nodee
{int t, x, y, v;bool operator (const nodee b) const{return t b.t;}
}q[N];
struct Tree//线段树求和
{int a[N2];#define ls x*2#define rs x*21void up(int x){a[x] a[ls] a[rs];return;}void add(int x, int L, int R, int w, int s){if (L w w R){a[x] s;return;}int mid L R 1;if (w mid) add(ls, L, mid, w, s);else add(rs, mid 1, R, w, s);up(x);}int ask(int x, int L, int R, int l, int r){if (L l R r) return a[x];int mid L R 1;if (r mid) return ask(ls, L, mid, l, r);if (l mid) return ask(rs, mid 1, R, l, r);return ask(ls, L, mid, l, mid) ask(rs, mid 1, R, mid 1, r);}
}T;
void add(int x, int y)
{a[tot].to y;a[tot].next head[x];head[x] tot;return;
}
void dfs1(int x)
{s[x] 1;for (int i head[x]; i; i a[i].next)if (a[i].to ! fa[x]){fa[a[i].to] x;dep[a[i].to] dep[x] 1;dfs1(a[i].to);s[x] s[a[i].to];if (s[a[i].to] s[hs[x]]) hs[x] a[i].to;}return;
}
void dfs2(int x, int y)
{anc[x] y;v[x] w;if (hs[x]) dfs2(hs[x], y);for (int i head[x]; i; i a[i].next)if (a[i].to ! fa[x] a[i].to ! hs[x])dfs2(a[i].to, a[i].to);
}
int ask(int x, int y)//求和
{int g 0;while (anc[x] ! anc[y]){if (dep[anc[x]] dep[anc[y]]) swap(x, y);g T.ask(1, 1, n, v[anc[x]], v[x]);x fa[anc[x]];}if (dep[x] dep[y]) swap(x, y);g T.ask(1, 1, n, v[x], v[y]);return g;
}
int main()
{scanf(%d%d, n, m);for (int i 1; i n; i){scanf(%d, pt[i].x);pt[i].v i;}for (int i 1; i n; i){scanf(%d%d, x, y);add(x, y);add(y, x);}for (int i 1; i m; i){scanf(%d%d%d, q[i].x, q[i].y, q[i].t);q[i].v i;}sort(pt 1, pt 1 n);sort(q 1, q 1 m);fa[1] dep[1] 1;dfs1(1);dfs2(1, 1);g 1;gg 1;while(g n){int h g;while(pt[h].x pt[g].x h n) T.add(1, 1, n, v[pt[h].v], 1), h;//赋值点权while(q[gg].t pt[g].x gg m) gg;//没有该权值的点while(q[gg].t pt[g].x gg m) ans[q[gg].v] ask(q[gg].x, q[gg].y), gg;//查询for (int i g; i h; i)T.add(1, 1, n, v[pt[i].v], -1);g h;}for (int i 1; i m; i)if (ans[i]) putchar(1);else putchar(0);return 0;
}
