hdu 3966 Aragorn's Story hdu 6162 Ch’s gift 树链剖分（点权）

3966 AC code

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50005;
struct edge
{
    int to;
    int nex;
}e[MAXN * 2];
int head[MAXN], cnt;
int son[MAXN], fa[MAXN], deep[MAXN], num[MAXN];
int top[MAXN], p[MAXN], pos;
int n, m, q;
int a[MAXN];
void init()
{
    cnt = 0;
    memset(head, -1, sizeof(head));
    pos = 1;
    memset(son, -1, sizeof(son));
}
void add(int a, int b)
{
    e[cnt] = edge{ b, head[a] };
    head[a] = cnt++;
}
void dfs1(int u, int pre, int dep)
{
    deep[u] = dep;
    num[u] = 1;
    fa[u] = pre;
    for (int i = head[u]; i + 1; i = e[i].nex)
    {
        int v = e[i].to;
        if (v != fa[u])
        {
            dfs1(v, u, dep + 1);
            num[u] += num[v];
            if (son[u] == -1 || num[son[u]] < num[v])
                son[u] = v;
        }
    }
}
void dfs2(int u, int sp)
{
    top[u] = sp;
    p[u] = pos++;
    if (son[u] == -1)
        return;
    dfs2(son[u], sp);
    for (int i = head[u]; i + 1; i = e[i].nex)
    {
        int v = e[i].to;
        if (son[u] != v && fa[u] != v)
            dfs2(v, v);
    }
}

int c[MAXN];
int lowbit(int k)
{
    return k & (-k);
}
void update(int k, int x)
{
    while (k < MAXN)
    {
        c[k] += x;
        k += lowbit(k);
    }
}
int query(int k)
{
    int res = 0;
    while (k > 0)
    {
        res += c[k];
        k -= lowbit(k);
    }
    return res;
}

void change(int u, int v, int val)
{
    int f1 = top[u], f2 = top[v];
    while (f1 != f2)
    {
        if (deep[f1] < deep[f2])
        {
            swap(f1, f2);
            swap(u, v);
        }
        update(p[f1], val);
        update(p[u] + 1, -val);
        u = fa[f1];
        f1 = top[u];
    }
    if (deep[u] > deep[v])
        swap(u, v);
    update(p[u], val);
    update(p[v] + 1,  -val);
}

char op[2];
int main()
{
    while (scanf("%d%d%d", &n, &m, &q) > 0)
    {
        init();
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        while (m--)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            add(u, v);
            add(v, u);
        }
        memset(c, 0, sizeof(c));
        dfs1(1, 0, 0);
        dfs2(1, 1);
        for (int i = 1; i <= n; i++)
        {
            update(p[i], a[i]);
            update(p[i] + 1, -a[i]);
        }
        while (q--)
        {
            scanf("%s", op);
            if (op[0] == 'Q')
            {
                int u;
                scanf("%d", &u);
                printf("%d\n", query(p[u]));
            }
            else
            {
                int u, v, val;
                scanf("%d%d%d", &u, &v, &val);
                if (op[0] == 'D')
                    val = -val;
                change(u, v, val);
            }
        }
    }
}

6162 AC code

#include <bits/stdc++.h>
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)>>1;
#define ll long long
using namespace std;
const int MAXN = 100005;
struct edge
{
    int to;
    int nex;
}e[MAXN * 2];
int n, m, q, ql, qr;
int lval, rval;
ll a[MAXN], t[MAXN];
int head[MAXN], cnt;
int son[MAXN], fa[MAXN], deep[MAXN], num[MAXN];
int top[MAXN], p[MAXN];
int pos;
void add(int a, int b)
{
    e[cnt] = edge{ b, head[a] };
    head[a] = cnt++;
}
void init()
{
    cnt = 0;
    memset(head, -1, sizeof(head));
    pos = 1;
    memset(son, -1, sizeof(son));
}
void dfs1(int u, int pre, int dep)
{
    deep[u] = dep;
    num[u] = 1;
    fa[u] = pre;
    for (int i = head[u]; i + 1; i = e[i].nex)
    {
        int v = e[i].to;
        if (v != fa[u])
        {
            dfs1(v, u, dep + 1);
            num[u] += num[v];
            if (son[u] == -1 || num[son[u]] < num[v])
                son[u] = v;
        }
    }
}
void dfs2(int u, int sp)
{
    top[u] = sp;
    p[u] = pos++;
    if (son[u] == -1)
        return;
    dfs2(son[u], sp);
    for (int i = head[u]; i + 1; i = e[i].nex)
    {
        int v = e[i].to;
        if (v != fa[u] && v != son[u])
            dfs2(v, v);
    }
}

struct node
{
    int l;
    int r;
    ll minn;
    ll maxn;
    ll sum;
}que[MAXN * 4];
void up(int k)
{
    que[k].sum = que[k << 1].sum + que[k << 1 | 1].sum;
    que[k].maxn = max(que[k << 1].maxn, que[k << 1 | 1].maxn);
    que[k].minn = min(que[k << 1].minn, que[k << 1 | 1].minn);
}
void build(int left, int right, int k)
{
    que[k].l = left;
    que[k].r = right;
    if (left == right)
    {
        que[k].maxn = que[k].minn = que[k].sum = a[left];
        return;
    }
    imid; 
    build(lson);
    build(rson);
    up(k);
}
ll query(int left, int right, int k)
{
    if (qr < left || right < ql)
        return 0;
    if (ql <= left && right <= qr && que[k].minn >= lval && que[k].maxn <= rval)
        return que[k].sum;
    if (left == right)
        return 0;
    imid;
    return query(lson) + query(rson);
}

ll change(int u, int v)
{
    ll res = 0;
    int f1 = top[u], f2 = top[v];
    while (f1 != f2)
    {
        if (deep[f1] < deep[f2])
        {
            swap(f1, f2);
            swap(u, v);
        }

        ql = p[f1];
        qr = p[u];
        res += query(1, n, 1);

        u = fa[f1];
        f1 = top[u];
    }
    if (deep[u] > deep[v])
        swap(u, v);
    ql = p[u];
    qr = p[v];
    res += query(1, n, 1);
    return res;
}

int main()
{
    while (scanf("%d%d", &n, &q) > 0)
    {
        vector<ll>ans;
        m = n - 1;
        init();
        for (int i = 1; i <= n; i++)
            scanf("%lld", &t[i]);
        int u, v, minval, maxval;
        while (m--)
        {
            scanf("%d%d", &u, &v);
            add(u, v);
            add(v, u);
        }
        dfs1(1, 0, 0);
        dfs2(1, 1);
        for (int i = 1; i <= n; i++)
            a[p[i]] = t[i];
        build(1, n, 1);
        for (int i = 0; i < q; i++)
        {
            int l, r;
            scanf("%d%d%d%d", &l, &r, &lval, &rval);
            ll val = change(l, r);
            ans.push_back(val);
        }
        for (int i = 0; i < q; i++)
        {
            if (i != 0)
                printf(" ");
            printf("%lld", ans[i]);
        }
        printf("\n");
    }
}