首页 > 代码库 > Hdu3966( Aragorn's Story ) 树链剖分
Hdu3966( Aragorn's Story ) 树链剖分
点更新树链剖分入门题,诶 错了好多发,提到同一点时没更新,边数组开小了一倍。
#include <cstdio>#include <algorithm>#include <iostream>#include <string.h>using namespace std;#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1const int maxn = 55555;int head[maxn];int top[maxn];struct Node{ int to; int next;}e[maxn * 2];int father[maxn];int deep[maxn];int size[maxn];int son[maxn];int pos[maxn];int color[maxn << 2];int vis[maxn];int len, z;void add(int from, int to){ e[len].to = to; e[len].next = head[from]; head[from] = len++;}void init(int x){ size[x] = 1; son[x] = 0; for (int i = head[x]; i != -1; i = e[i].next){ int cc = e[i].to; if (cc == father[x]) continue; father[cc] = x; deep[cc] = deep[x] + 1; init(cc); size[x] += size[cc]; if (size[cc] > size[son[x]]) son[x] = cc; }}void dfs(int x, int tp){ pos[x] = ++z; top[x] = tp; if (son[x]) dfs(son[x], tp); for (int i = head[x]; i != -1; i = e[i].next){ int cc = e[i].to; if (cc == father[x] || cc == son[x]) continue; dfs(cc, cc); }}void down(int rt){ if (color[rt]){ color[rt << 1] += color[rt]; color[rt << 1 | 1] += color[rt]; color[rt] = 0; }}void update(int L, int R, int ans, int l, int r, int rt){ if (L <= l&&r <= R){ color[rt] += ans; return; } int mid = (l + r) >> 1; down(rt); if (L <= mid) update(L, R, ans, lson); if (R > mid) update(L, R, ans, rson);}int ask(int key, int l, int r, int rt){ if (l == r) return color[rt]; down(rt); int mid = (l + r) >> 1; if (key <= mid) return ask(key, lson); else return ask(key, rson);}void gao(int x, int y, int ans){ int f1 = top[x]; int f2 = top[y]; while (f1 != f2){ if (deep[f1] < deep[f2]){ swap(f1, f2); swap(x, y); } update(pos[f1], pos[x], ans, 1, z, 1); x = father[f1]; f1 = top[x]; } if (deep[x]>deep[y]){ swap(x, y); } update(pos[x], pos[y], ans, 1, z, 1);}int main(){ int n, m, k; int a, b, c; char str[100]; while (cin >> n >> m >> k){ memset(head, -1, sizeof(head)); memset(color, 0, sizeof(color)); memset(size, 0, sizeof(size)); deep[1] = 1; len = 0; z = 0; for (int i = 1; i <= n; i++){ scanf("%d", &vis[i]); } for (int i = 0; i < m; i++){ scanf("%d%d", &a, &b); add(a, b); add(b, a); } init(1); dfs(1, 1); for (int i = 0; i < k; i++){ scanf("%s", str); if (str[0] == ‘Q‘){ scanf("%d", &a); printf("%d\n", vis[a] + ask(pos[a], 1, z, 1)); } if (str[0] == ‘I‘){ scanf("%d%d%d", &a, &b, &c); gao(a, b, c); } if (str[0] == ‘D‘){ scanf("%d%d%d", &a, &b, &c); gao(a, b, -c); } } } return 0;}
Hdu3966( Aragorn's Story ) 树链剖分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。