首页 > 代码库 > Light 1348 - Aladdin and the Return Journey(树链剖分)
Light 1348 - Aladdin and the Return Journey(树链剖分)
Light 1348 - Aladdin and the Return Journey
题目链接
树链剖分基础题,注意一个坑点,就是下标按0开始的话按我的写法是会错的,因为son初值赋成0了,要么改一下son初值,要么把下标都+1
代码:
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int N = 30005; int dep[N], fa[N], son[N], sz[N], top[N], id[N], idx; int first[N], next[N * 2], vv[N * 2]; void dfs1(int u, int f, int d) { dep[u] = d; sz[u] = 1; fa[u] = f; son[u] = 0; for (int i = first[u]; i + 1; i = next[i]) { int v = vv[i]; if (v == f) continue; dfs1(v, u, d + 1); sz[u] += sz[v]; if (sz[son[u]] < sz[v]) son[u] = v; } } void dfs2(int u, int tp) { id[u] = ++idx; top[u] = tp; if (son[u]) dfs2(son[u], tp); for (int i = first[u]; i + 1; i = next[i]) { int v = vv[i]; if (v == fa[u] || v == son[u]) continue; dfs2(v, v); } } inline int lowbit(int x) { return x&(-x); } int bit[N]; void add(int x, int v) { while (x < N) { bit[x] += v; x += lowbit(x); } } int get(int x) { int ans = 0; while (x) { ans += bit[x]; x -= lowbit(x); } return ans; } int get(int l, int r) { return get(r) - get(l - 1); } int gao(int u, int v) { int tp1 = top[u], tp2 = top[v]; int ans = 0; while (tp1 != tp2) { if (dep[tp1] < dep[tp2]) { swap(tp1, tp2); swap(u, v); } ans += get(id[tp1], id[u]); u = fa[tp1]; tp1 = top[u]; } if (dep[u] > dep[v]) swap(u, v); ans += get(id[u], id[v]); return ans; } int en; void add_Edge(int u, int v) { vv[en] = v; next[en] = first[u]; first[u] = en++; } int t, n, val[N]; int main() { int cas = 0; scanf("%d", &t); while (t--) { idx = 0; en = 0; memset(bit, 0, sizeof(bit)); memset(first, -1, sizeof(first)); scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &val[i]); int u, v; for (int i = 1; i < n; i++) { scanf("%d%d", &u, &v); u++; v++; add_Edge(u, v); add_Edge(v, u); } dfs1(1, 0, 1); dfs2(1, 1); for (int i = 1; i <= n; i++) add(id[i], val[i]); int q; scanf("%d", &q); int ty, a, b; printf("Case %d:\n", ++cas); while (q--) { scanf("%d%d%d", &ty, &a, &b); if (ty) { a++; add(id[a], b - val[a]); val[a] = b; } else printf("%d\n", gao(a + 1, b + 1)); } } return 0; }
Light 1348 - Aladdin and the Return Journey(树链剖分)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。