HDU - 3974
先给一棵n 个点的数， “u，v” 表示 v 是u的父亲。 m 个操作： “Txy” 表示把 以 x 为根的子树全部染成y这种颜色。 “Cx” 表示询问 x 号节点当前是哪种颜色？ 多组 (T≤10)
n,m≤500001≤x≤n,1≤y≤109
套路题，搞出DFS序，然后用线段树成段更新，以及单点查询就over!
学到了怎么搞DFS序，目前我知道两种方法： 一种是直接记每个节点的开始和结束的时间戳，其实就是把节点按照DFS的先后顺序(这个好像叫先序遍历)进行标号，像这样(样例)： 操作节点3就相当于修改区间[3, 5]。 另一种就是记每个节点开始的时间戳以及 以这个节点为根的子树的size。
两种方法大同小异，最终目的是要将树对应为区间，将树上的操作转化为区间上的修改，好用线段树来解决问题。
详见代码：
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <set> #include <map> #include <queue> using namespace std; typedef long long LL; const int inf = 1 << 30; const LL INF = 1LL << 60; const int MaxN = 50005; int T; int n, m; int all, time, cas; int pre[2 * MaxN + 5], last[MaxN + 5], other[2 * MaxN + 5]; int fa[MaxN + 5]; int left[MaxN + 5], right[MaxN + 5]; struct segtree { int l, r; int task; //当前区间的颜色 }tree[4 * MaxN + 5]; int lazy[4 * MaxN + 5];//lazy[rt]表示rt节点所管辖的区间 的颜色 //感觉有点多余,好像用那个task也可以实现,不过没写对 void build(int x, int y) { //建树 pre[++all] = last[x]; last[x] = all; other[all] = y; } int find(int x) { //找到给的这棵树的根节点 int father = fa[x]; while(x != father) { x = father; father = fa[father]; } return x; } void Dfs(int x, int fa) { int ed = last[x], dr; ++time; left[x] = time; //开始时间,对应区间左端点 while(ed != -1) { dr = other[ed]; if(dr != fa) Dfs(dr, x); ed = pre[ed]; } right[x] = time; //结束时间,对应区间右端点 } void Build(int rt, int l, int r) //建线段树 { tree[rt].l = l, tree[rt].r = r; tree[rt].task = -1; //初始化为-1 lazy[rt] = -1; if(l == r) return ; int mid = (l + r) >> 1; Build(rt << 1, l, mid); Build(rt << 1 | 1, mid + 1, r); } void push_down(int rt) { //下放标记 if(lazy[rt] != -1) { tree[rt << 1].task = lazy[rt]; tree[rt << 1 | 1].task = lazy[rt]; lazy[rt << 1] = lazy[rt]; lazy[rt << 1 | 1] = lazy[rt]; lazy[rt] = -1; } } void update(int rt, int L, int R, int t) { if(L <= tree[rt].l && tree[rt].r <= R) { lazy[rt] = t; //区间修改 tree[rt].task = t; return; } push_down(rt); int mid = (tree[rt].l + tree[rt].r) >> 1; if(L <= mid) update(rt << 1, L, R, t); if(R > mid) update(rt << 1 | 1, L, R, t); } int query(int rt, int pos) { if(tree[rt].l == pos && pos == tree[rt].r) { return tree[rt].task; } push_down(rt); int mid = (tree[rt].l + tree[rt].r) >> 1; if(pos <= mid) return query(rt << 1, pos); else return query(rt << 1 | 1, pos); } int main() { cas = 0; scanf("%d", &T); while(T--) { time = 0; all = -1; memset(last, -1, sizeof(last)); scanf("%d", &n); for(int i = 1; i <= n; i++) fa[i] = i; for(int i = 1; i <= n - 1; i++) { int u, v; scanf("%d %d", &u, &v); fa[u] = v; build(v, u); } int root = find(1);//可在1~n中随便找一点 //printf("root = %d\n", root); Dfs(root, 0); Build(1, 1, time); printf("Case #%d:\n", ++cas); scanf("%d", &m); for(int i = 1; i <= m; i++) { char op; int x, y; scanf(" %c", &op); if(op == 'C') { scanf("%d", &x); printf("%d\n", query(1, left[x]));//单点查询 } else if(op == 'T') { scanf("%d %d", &x, &y); update(1, left[x], right[x], y);//更新区间 } } memset(tree, 0, sizeof(tree)); memset(left, 0, sizeof(left)); memset(right, 0, sizeof(right)); memset(pre, 0, sizeof(pre)); memset(other, 0, sizeof(other)); } return 0; }求开始时间戳和子树size的也大同小异，一并贴上：
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <set> #include <map> #include <queue> using namespace std; typedef long long LL; const int inf = 1 << 30; const LL INF = 1LL << 60; const int MaxN = 50005; int T; int n, m; int all, time, cas; int pre[2 * MaxN + 5], last[MaxN + 5], other[2 * MaxN + 5]; int fa[MaxN + 5]; int start[MaxN + 5], size[MaxN + 5]; struct segtree { int l, r; int task; }tree[4 * MaxN + 5]; int lazy[4 * MaxN + 5]; void build(int x, int y) { pre[++all] = last[x]; last[x] = all; other[all] = y; } int find(int x) { int father = fa[x]; while(x != father) { x = father; father = fa[father]; } return x; } void Dfs(int x, int fa) { int ed = last[x], dr; ++time; start[x] = time; while(ed != -1) { dr = other[ed]; if(dr != fa) { Dfs(dr, x); size[x] += size[dr]; } ed = pre[ed]; } } void Build(int rt, int l, int r) { tree[rt].l = l, tree[rt].r = r; tree[rt].task = -1; lazy[rt] = -1; if(l == r) return ; int mid = (l + r) >> 1; Build(rt << 1, l, mid); Build(rt << 1 | 1, mid + 1, r); } void push_down(int rt) { if(lazy[rt] != -1) { tree[rt << 1].task = lazy[rt]; tree[rt << 1 | 1].task = lazy[rt]; lazy[rt << 1] = lazy[rt]; lazy[rt << 1 | 1] = lazy[rt]; lazy[rt] = -1; } } void update(int rt, int L, int R, int t) { if(L <= tree[rt].l && tree[rt].r <= R) { lazy[rt] = t; tree[rt].task = t; return; } push_down(rt); int mid = (tree[rt].l + tree[rt].r) >> 1; if(L <= mid) update(rt << 1, L, R, t); if(R > mid) update(rt << 1 | 1, L, R, t); } int query(int rt, int pos) { if(tree[rt].l == pos && pos == tree[rt].r) { return tree[rt].task; } push_down(rt); int mid = (tree[rt].l + tree[rt].r) >> 1; if(pos <= mid) return query(rt << 1, pos); else return query(rt << 1 | 1, pos); } int main() { cas = 0; scanf("%d", &T); while(T--) { time = 0; all = -1; memset(last, -1, sizeof(last)); scanf("%d", &n); for(int i = 1; i <= n; i++) fa[i] = i, size[i] = 1; for(int i = 1; i <= n - 1; i++) { int u, v; scanf("%d %d", &u, &v); fa[u] = v; build(v, u); } int root = find(1); //printf("root = %d\n", root); Dfs(root, 0); Build(1, 1, time); printf("Case #%d:\n", ++cas); scanf("%d", &m); for(int i = 1; i <= m; i++) { char op; int x, y; scanf(" %c", &op); if(op == 'C') { scanf("%d", &x); printf("%d\n", query(1, start[x])); } else if(op == 'T') { scanf("%d %d", &x, &y); update(1, start[x], start[x] + size[x] - 1, y); } } memset(tree, 0, sizeof(tree)); memset(start, 0, sizeof(start)); memset(size, 0, sizeof(size)); memset(pre, 0, sizeof(pre)); memset(other, 0, sizeof(other)); } return 0; }