HDU 3974：樹映射到區間 + 線段樹區間更新/單點查詢

題目大意

給一棵有根樹，支援兩種操作：
C x：查詢節點 x 的值。
U x y：將以 x 為根的子樹所有節點值設為 y。
初始值為 -1。多組測資。

解題思路：DFS 序 + 線段樹

1. DFS 遍歷樹，給每個節點分配進入時間 start[x] 和離開時間 end[x]。子樹對應區間 [start[x], end[x]]。
2. 建立線段樹支援區間賦值更新（懶標記）與單點查詢。
3. 操作轉化：
    更新：update(start[x], end[x], y)
    查詢：query(start[x])

核心代碼

#include <cstdio>
#include <cstring>

struct SegNode { int l, r, val, lazy; } seg[200010];
struct Edge { int to, next; } edge[50010];
int head[50010], start[50010], end[50010], used[50010];
int tot, cnt;

void addEdge(int x, int y) { // y 是父，x 是子
    edge[tot].to = x;
    edge[tot].next = head[y];
    head[y] = tot++;
}

void dfs(int x) {
    ++cnt; start[x] = cnt;
    for (int i = head[x]; i != -1; i = edge[i].next)
        dfs(edge[i].to);
    end[x] = cnt;
}

void build(int l, int r, int k) {
    seg[k].l = l; seg[k].r = r; seg[k].val = -1; seg[k].lazy = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(l, mid, k<<1);
    build(mid+1, r, k<<1|1);
}

void pushDown(int k) {
    if (!seg[k].lazy) return;
    seg[k<<1].val = seg[k<<1|1].val = seg[k].lazy;
    seg[k<<1].lazy = seg[k<<1|1].lazy = seg[k].lazy;
    seg[k].lazy = 0;
}

void update(int l, int r, int k, int v) {
    if (seg[k].l == l && seg[k].r == r) {
        seg[k].val = seg[k].lazy = v; return;
    }
    pushDown(k);
    int mid = (seg[k].l + seg[k].r) >> 1;
    if (r <= mid) update(l, r, k<<1, v);
    else if (l > mid) update(l, r, k<<1|1, v);
    else { update(l, mid, k<<1, v); update(mid+1, r, k<<1|1, v); }
    seg[k].val = (seg[k<<1].val == seg[k<<1|1].val) ? seg[k<<1].val : -1;
}

int query(int pos, int k) {
    if (seg[k].val != -1) return seg[k].val;
    if (seg[k].l == seg[k].r) return seg[k].val;
    pushDown(k);
    int mid = (seg[k].l + seg[k].r) >> 1;
    return pos <= mid ? query(pos, k<<1) : query(pos, k<<1|1);
}

int main() {
    int T; scanf("%d", &T);
    for (int cs = 1; cs <= T; ++cs) {
        int n; scanf("%d", &n);
        tot = 0; cnt = 0;
        memset(head, -1, sizeof(head));
        memset(used, 0, sizeof(used));
        for (int i = 1; i < n; ++i) {
            int x, y; scanf("%d%d", &x, &y);
            used[x] = 1; addEdge(x, y);
        }
        int root = 1;
        while (used[root]) ++root;
        dfs(root);
        build(1, cnt, 1);
        int m; scanf("%d", &m);
        printf("Case #%d:\n", cs);
        while (m--) {
            char op[2]; scanf("%s", op);
            if (op[0] == 'C') {
                int x; scanf("%d", &x);
                printf("%d\n", query(start[x], 1));
            } else {
                int x, y; scanf("%d%d", &x, &y);
                update(start[x], end[x], 1, y);
            }
        }
    }
    return 0;
}

複雜度

• DFS 序構建：O(N)
• 每次操作：O(log N)
• 總時間：O((N + Q) log N)
• 空間：O(N)

關鍵技巧

• 樹映射到區間（DFS 序）是處理子樹操作的經典技巧。
• 線段樹懶標記用於區間賦值，查詢時向下傳遞。
• 查找根節點：入度為 0 的節點。