首页 > 代码库 > 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 ) 树链剖分