HDU 3974 Assign the task

题目链接
先给每个人物利用dfs先序地打标记。之后所有的处理都是在这个标记基础上操作的。再树上每个节点形成的树(包括自己有多少个结点），对于某个人u，分配工作的时候(想成染色)，相当于对[idx[u], idx[u] + cnt[u] - 1]这个区间染色。
比如例子

    2                       1
   / \                     /  \
  3   5  对应在线段树中位置  2    5
 / \                     / \
4   1                    3  4

那么对于2号人物分配任务k，相当于对区间[1,1+5-1]这个区间染颜色k。其它就是区间更新+查询了。
粗心的地方：留意，后续操作都是对标记操作，如a，应操作idx[a]。另外就是cas既然用for递增不是while(T--)的话，别不小心习惯cas++..

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define pb push_back
const int inf = 0x3f3f3f3f, maxN = 5e4 + 5;
int N, M, T;

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define lch rt << 1
#define rch rt << 1 | 1
int seg[maxN << 2];

vector<int> G[maxN];
// 记录节点i的子数和自身坐标
int cnt[maxN], idx[maxN];
int vis[maxN], ii;

void dfs(int s) {
    idx[s] = ii++;
    cnt[s] = 1;
    rep(i, 0, G[s].size()) {
        int cur = G[s][i];
        if (vis[cur])
            continue;
        vis[cur] = 1;
        dfs(cur);
        cnt[s] += cnt[cur];
    }
}

void push_down(int rt) {
    if (seg[rt] == -1)
        return;
    seg[lch] = seg[rch] = seg[rt];
    seg[rt] = -1;
}

void update(int L, int R, int x, int l, int r, int rt) {
    if (L <= l && r <= R) {
        seg[rt] = x;
        return;
    }
    push_down(rt);
    int m = (l + r) / 2;
    if (L <= m) update(L, R, x, lson);
    if (R > m) update(L, R, x, rson);
}

int query(int p, int l, int r, int rt) {
    if (l == r) {
        return seg[rt];
    }
    push_down(rt);
    int m = (l + r) / 2;
    if (p <= m) return query(p, lson);
    else return query(p, rson);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif

    scanf("%d", &T);
    rep(cas, 1, T + 1) {
        scanf("%d", &N);
        int a, b;
        // 最终剩下的就是boss
        ll boss = N + N * (N - 1) / 2;
        rep(i, 1, N + 1)
            G[i].clear();
        rep(i, 1, N) {
            scanf("%d%d", &a, &b);
            G[b].pb(a);
            boss -= a;
        }
        ii = 1;
        mst(vis, 0);
        mst(seg, -1);
        mst(cnt, 0);
        vis[boss] = 1;
        dfs(boss);

        // rep(i, 1, N + 1)
        //   printf("%d ", cnt[i]);
        // puts("");

        scanf("%d", &M);
        char op[10];
        printf("Case #%lld:\n", cas);
        rep(i, 0, M) {
            scanf("%s %d", op, &a);
            if (op[0] == 'T') {
                scanf("%d", &b);
                int lb = idx[a];
                int ub = idx[a] + cnt[a] - 1;
                update(lb, ub, b, 1, N, 1);
            } else {
                printf("%d\n", query(idx[a], 1, N, 1));
            }
        }
    }
    return 0;
}