SP10707 COT2 - Count on a tree II
2022/4/7 23:50:07
本文主要是介绍SP10707 COT2 - Count on a tree II,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
\(\text{Solution}\)
统计树上 \(x\) 到 \(y\) 路径不同数的种类数
可以树上莫队
离线的树上莫队就是把树用欧拉序拍下来,然后和序列上的莫队一样即可
\(\text{Code}\)
#include <cstdio> #include <algorithm> #include <cmath> #define RE register #define IN inline using namespace std; const int N = 1e5 + 5; int n, m, a[N], b[N], h[N], tot, dfc, rev[N], st[N], ed[N], ans[N]; int fa[N], dep[N], siz[N], son[N], top[N], bl[N], Ans, buc[N], used[N]; struct edge{int to, nxt;}e[N * 2]; IN void add(int x, int y){e[++tot] = edge{y, h[x]}, h[x] = tot;} struct node{int l, r, id, z;}Q[N]; IN bool cmp(node a, node b){return ((bl[a.l] ^ bl[b.l]) ? a.l < b.l : ((bl[a.l] & 1) ? a.r < b.r : a.r > b.r));} void dfs1(int x, int f) { st[x] = ++dfc, rev[dfc] = x, fa[x] = f, dep[x] = dep[f] + 1, siz[x] = 1; for(RE int i = h[x]; i; i = e[i].nxt) { int v = e[i].to; if (v == f) continue; dfs1(v, x), siz[x] += siz[v]; if (siz[v] > siz[son[x]]) son[x] = v; } ed[x] = ++dfc, rev[dfc] = x; } void dfs2(int x, int t) { top[x] = t; if (son[x]) dfs2(son[x], t); for(RE int i = h[x]; i; i = e[i].nxt) { int v = e[i].to; if (v == fa[x] || v == son[x]) continue; dfs2(v, v); } } IN int LCA(int x, int y) { while (top[x] ^ top[y]) { if (dep[top[x]] > dep[top[y]]) x = fa[top[x]]; else y = fa[top[y]]; } return (dep[x] < dep[y] ? x : y); } IN void Del(int x){--buc[a[x]]; if (!buc[a[x]]) --Ans;} IN void Add(int x){if (!buc[a[x]]) ++Ans; ++buc[a[x]];} IN void update(int x){(used[x] ? Del(x) : Add(x)), used[x] ^= 1;} void GetQ() { for(RE int i = 1, x, y; i <= m; i++) { scanf("%d%d", &x, &y); if (st[x] > st[y]) swap(x, y); int lca = LCA(x, y); if (lca == x) Q[i] = node{st[x], st[y], i}; else Q[i] = node{ed[x], st[y], i, lca}; } } void solve() { GetQ(), sort(Q + 1, Q + m + 1, cmp); int l = 1, r = 0; for(RE int i = 1; i <= m; i++) { while (l < Q[i].l) update(rev[l++]); while (l > Q[i].l) update(rev[--l]); while (r < Q[i].r) update(rev[++r]); while (r > Q[i].r) update(rev[r--]); if (Q[i].z) update(Q[i].z); ans[Q[i].id] = Ans; if (Q[i].z) update(Q[i].z); } } int main() { scanf("%d%d", &n, &m); for(RE int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i]; sort(b + 1, b + n + 1); int len = unique(b + 1, b + n + 1) - b - 1; for(RE int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + len + 1, a[i]) - b; for(RE int i = 1, x, y; i < n; i++) scanf("%d%d", &x, &y), add(x, y), add(y, x); dfs1(1, 0), dfs2(1, 1); int block = sqrt(n) + 1; for(RE int i = 1; i <= dfc; i++) bl[i] = i / block + 1; solve(); for(RE int i = 1; i <= m; i++) printf("%d\n", ans[i]); }
这篇关于SP10707 COT2 - Count on a tree II的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding