LightOJ 1348 Aladdin and the Return Journey(树链剖分)

描述

Finally the Great Magical Lamp was in Aladdin’s hand. Now he wanted to
return home. But he didn’t want to take any help from the Genie
because he thought that it might be another adventure for him. All he
remembered was the paths he had taken to reach there. But since he
took the lamp, all the genies in the cave became angry and they were
planning to attack. As Aladdin was not afraid, he wondered how many
genies were there. He summoned the Genie from the lamp and asked this.

Now you are given a similar problem. For simplicity assume that, you
are given a tree (a connected graph with no cycles) with n nodes,
nodes represent places, edges represent roads. In each node, initially
there are an arbitrary number of genies. But the numbers of genies
change in time. So, you are given a tree, the number of genies in each
node and several queries of two types. They are:

1) 0 i j, it means that you have to find the total number of
genies in the nodes that occur in path from node i to j (0 ≤ i, j <
n).

2) 1 i v, it means that number of genies in node i is changed to
v (0 ≤ i < n, 0 ≤ v ≤ 1000).

Input

Input starts with an integer T (≤ 10), denoting the number of test
cases.

Each case starts with a blank line. Next line contains an integer n (2
≤ n ≤ 30000). The next line contains n space separated integers
between 0 and 1000, denoting the number of genies in the nodes
respectively. Then there are n-1 lines each containing two integers: u
v (0 ≤ u, v < n, u ≠ v) meaning that there is an edge from node u and
v. Assume that the edges form a valid tree. Next line contains an
integer q (1 ≤ q ≤ 105) followed by q lines each containing a query as
described above.

Output

For each case, print the case number in a single line. Then for each
query 0 i j, print the total number of genies in the nodes that occur
in path i to j.

Sample Input

1
4
10 20 30 40
0 1
1 2
1 3
3
0 2 3
1 1 100
0 2 3

Sample Output

Case 1:
90
170

思路

给一棵树维护两个操作:

• 0 x y：求x到y的所有节点和
• 1 x y：把x节点的值变成y

裸树链剖分

代码

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <sstream>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#include <list>
using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int first[N], tot, n, m;
int sum[N << 2];
int w[N], wt[N], cnt, siz[N], dep[N], fa[N], son[N], top[N], id[N];
struct edge
{
    int v, next;
} e[N];
void add_edge(int u, int v)
{
    e[tot].v = v;
    e[tot].next = first[u];
    first[u] = tot++;
}
void init()
{
    mem(first, -1);
    tot = 0;
    cnt = 0;
}
void pushup(int rt)
{
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void build(int l, int r, int rt)
{
    if (l == r)
    {
        sum[rt] = wt[l];
        return;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    pushup(rt);
}
void update(int p, int sc, int l, int r, int rt)
{
    if (l == r)
    {
        sum[rt] = sc;
        return;
    }
    int m = (l + r) >> 1;
    if (p <= m)
        update(p, sc, lson);
    else
        update(p, sc, rson);
    pushup(rt);
}
int query(int L, int R, int l, int r, int rt)
{
    if (L <= l && r <= R)
        return sum[rt];
    int m = (l + r) >> 1;
    int ans = 0;
    if (L <= m)
        ans += query(L, R, lson);
    if (R > m)
        ans += query(L, R, rson);
    pushup(rt);
    return ans;
}
void dfs1(int u, int f, int deep)
{
    siz[u] = 1;
    dep[u] = deep;
    fa[u] = f;
    son[u] = 0;
    int maxson = -1;
    for (int i = first[u]; ~i; i = e[i].next)
    {
        int v = e[i].v;
        if (v == f)
            continue;
        dfs1(v, u, deep + 1);
        siz[u] += siz[v];
        if (siz[v] > maxson)
        {
            son[u] = v;
            maxson = siz[v];
        }
    }
}
void dfs2(int u, int topf)
{
    top[u] = topf;
    id[u] = ++cnt;
    wt[cnt] = w[u];
    if (!son[u])
        return;
    dfs2(son[u], topf);
    for (int i = first[u]; ~i; i = e[i].next)
    {
        int v = e[i].v;
        if (v == fa[u] || v == son[u])
            continue;
        dfs2(v, v);
    }
}
int qsum(int x, int y)
{
    int ans = 0;
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        ans += query(id[top[x]], id[x], 1, n, 1);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y])
        swap(x, y);
    ans += query(id[x], id[y], 1, n, 1);
    return ans;
}
void change(int x, int k)
{
    update(id[x], k, 1, n, 1);
}
int main()
{
    // freopen("in.txt", "r", stdin);
    int t, u, v, q = 1;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        init();
        for (int i = 1; i <= n; i++)
            scanf("%d", &w[i]);
        for (int i = 1; i <= n - 1; i++)
        {
            scanf("%d%d", &u, &v);
            u++, v++;
            add_edge(u, v);
            add_edge(v, u);
        }
        dfs1(1, 0, 1);
        dfs2(1, 1);
        build(1, n, 1);
        scanf("%d", &m);
        printf("Case %d:\n", q++);
        while (m--)
        {
            int op, x, y;
            scanf("%d%d%d", &op, &x, &y);
            x++;
            if (op == 0)
            {
                y++;
                printf("%d\n", qsum(x, y));
            }
            else if (op == 1)
                change(x, y);
        }
    }
    return 0;
}