BZOJ4771七彩树

it2022-05-06  6

/* 线段树合并 维护每个颜色的最小深度即可 ??? 要强制在线 考虑不限制深度的方法统计子树中的颜色个数将每种颜色按照dfs序排序, 然后树上每个点答案贡献 + 1, 同种颜色相邻dfs序的lca处-1 这样统计子树和即可 考虑假如有深度限制的话, 这个方法可以离线来做, 按照深度从小到大一层一层地加入点, 同时对于每种 颜色按照dfs序维护set, 那么对于所有的询问按照deep[x] + d排序就可以处理了 现在要求在线, 那么按照深度建立主席树, 每次在上面查询就好了 l 写成1 debug3小时 */ #include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<queue> #include<cmath> #include<set> #define ll long long #define M 200010 #define mmp make_pair using namespace std; int read() { int nm = 0, f = 1; char c = getchar(); for(; !isdigit(c); c = getchar()) if(c == '-') f = -1; for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0'; return nm * f; } int n, m, t, deep[M], root[M], sz[M], son[M], fa[M], top[M], dfn[M], low[M], dft, cor[M], maxdeep, ans, cnt; vector<int> to[M], note[M]; struct cmp { bool operator () (const int &a, const int &b) const { return dfn[a] < dfn[b]; } }; set<int, cmp> st[M]; set<int>::iterator it, it2; void init() { for(int i = 1; i <= n; i++) vector<int>().swap(to[i]), vector<int>().swap(note[i]), st[i].clear(), son[i] = 0; maxdeep = ans = cnt = dft = 0; } void dfs(int now, int f) { deep[now] = deep[f] + 1; // note[deep[now]].push_back(now); maxdeep = max(maxdeep, deep[now]); sz[now] = 1; for(int i = 0; i < to[now].size(); i++) { int vj = to[now][i]; dfs(vj, now); if(sz[vj] > sz[son[now]]) son[now] = vj; sz[now] += sz[vj]; } } void dfs(int now) { dfn[now] = ++dft; note[deep[now]].push_back(now);/* if(son[now]) { top[son[now]] = top[now]; dfs(son[now]); }*/ for(int i = to[now].size() - 1; i >= 0; i--) { int vj = to[now][i]; if(vj == son[now]) top[vj] = top[now]; else top[vj] = vj; dfs(vj); } low[now] = dft; } int lca(int a, int b) { while(top[a] != top[b]) { if(deep[top[a]] < deep[top[b]]) swap(a, b); a = fa[top[a]]; } if(deep[a] > deep[b]) swap(a, b); return a; } int rt[M], ls[M * 50], rs[M * 50], v[M * 50]; void insert(int l, int r, int &now, int pos, int val) { if(!now) { now = ++cnt; ls[now] = rs[now] = v[now] = 0; } if(l == r) { v[now] += val; return; } int mid = (l + r) >> 1; if(pos <= mid) insert(l, mid, ls[now], pos, val); else insert(mid + 1, r, rs[now], pos, val); v[now] = v[ls[now]] + v[rs[now]]; } int merge(int last, int now, int l, int r) { if(!last || !now) return last + now; if(l == r) { v[now] += v[last]; return now; } int mid = (l + r) >> 1; ls[now] = merge(ls[last], ls[now], l, mid); rs[now] = merge(rs[last], rs[now], mid + 1, r); v[now] = v[ls[now]] + v[rs[now]]; return now; } int query(int l, int r, int now, int ln, int rn) { if(l > rn || r < ln) return 0; if(l >= ln && r <= rn) return v[now]; int mid = (l + r) >> 1; return query(l, mid, ls[now], ln, rn) + query(mid + 1, r, rs[now], ln, rn); } int main() { // freopen("1.in", "r", stdin); freopen("2.out", "w", stdout); t = read(); while(t--) { n = read(), m = read(); init(); for(int i = 1; i <= n; i++) cor[i] = read(); for(int i = 2; i <= n; i++) fa[i] = read(), to[fa[i]].push_back(i); dfs(1, 0); top[1] = 1; dfs(1); rt[0] = 0; for(int d = 1; d <= maxdeep; d++) { rt[d] = 0; for(int i = note[d].size() - 1; i >= 0; i--) { int x = note[d][i]; // cout << x << " " << deep[x] << " " << dfn[x] << " " << cnt<< "\n"; insert(1, n, rt[d], dfn[x], 1); it = st[cor[x]].lower_bound(x); int pre = -1, nxt = -1; if(it != st[cor[x]].end()) nxt = *it; if(it != st[cor[x]].begin()) pre = *(--it); if(pre != -1) insert(1, n, rt[d], dfn[lca(pre, x)], -1); if(nxt != -1) insert(1, n, rt[d], dfn[lca(x, nxt)], -1); if(pre != -1 && nxt != -1) insert(1, n, rt[d], dfn[lca(pre, nxt)], 1); st[cor[x]].insert(x); } rt[d] = merge(rt[d - 1], rt[d], 1, n); } // for(int i = 1; i < n; i++) cout << lca(i, i + 1) << " "; // break; while(m--) { int x = read() ^ ans, d = read() ^ ans; d = min(maxdeep, deep[x] + d); ans = query(1, n, rt[d], dfn[x], low[x]); cout << ans << '\n'; } } return 0; } /* 3 3 3 1 2 3 1 2 1 1 2 2 3 3 5 8 1 3 3 2 2 1 1 3 3 1 0 0 0 3 0 1 3 2 1 2 0 6 2 4 1 5 8 1 3 3 2 2 1 1 3 3 1 0 0 0 3 0 1 3 2 1 2 0 6 2 4 1 1 5 5 1 2 3 4 5 1 1 1 1 1 1 1 1 0 0 1 1 5 5 */

转载于:https://www.cnblogs.com/luoyibujue/p/10518344.html


最新回复(0)