题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=3974

题意：给定一棵树，50000个节点，50000个操作，C x表示查询x节点的值，T x y表示更新x节点及其子节点的值为y

大致把边存一下那一棵树来举例子

　　　　2

　　3　　　 5

 4　　　 1

例如像这样的一棵树，可以将2->1,3->2,4->3,1->4,5->5按照dfs序来编号，然后用线段树进行区间修改，稍微想一想

应该都会了。

#include <iostream>#include <cstring>#include <vector>using namespace std;const int M = 5e4 + 10;vector<int>vc[M];int pre[M] , dig[M] , length[M] , cnt;void dfs(int pos) {    if(vc[pos].size() == 0) {        return ;    }    int len = vc[pos].size();    for(int i = 0 ; i < len ; i++) {        dig[vc[pos][i]] = ++cnt;        dfs(vc[pos][i]);        length[vc[pos][i]] = cnt;    }}struct TnT {    int l , r , num , add;}T[M << 2];void build(int l , int r , int p) {    int mid = (l + r) >> 1;    T[p].l = l , T[p].r = r , T[p].add = -1 , T[p].num = -1;    if(T[p].l == T[p].r) {        return ;    }    build(l , mid , p << 1);    build(mid + 1 , r , (p << 1) | 1);}void pushdown(int p) {    if(T[p].add != -1) {        T[p << 1].num = T[p].add;        T[(p << 1) | 1].num = T[p].add;        T[p << 1].add = T[p].add;        T[(p << 1) | 1].add = T[p].add;        T[p].add = -1;    }}void updata(int l , int r , int p , int ad) {    int mid = (T[p].l + T[p].r) >> 1;    if(T[p].l == l && T[p].r == r) {        T[p].num = ad;        T[p].add = ad;        return ;    }    pushdown(p);    if(mid >= r) {        updata(l , r , p << 1 , ad);    }    else if(mid < l) {        updata(l , r , (p << 1) | 1 , ad);    }    else {        updata(l , mid , p << 1 , ad);        updata(mid + 1 , r , (p << 1) | 1 , ad);    }}int query(int pos , int p) {    int mid = (T[p].l + T[p].r) >> 1;    if(T[p].l == T[p].r && T[p].l == pos) {        return T[p].num;    }    pushdown(p);    if(mid >= pos) {        return query(pos , p << 1);    }    else {        return query(pos , (p << 1) | 1);    }}int main() {    int t;    int ans = 0;    scanf("%d" , &t);    while(t--) {        int n;        ans++;        scanf("%d" , &n);        for(int i = 0 ; i <= n ; i++) {            vc[i].clear();            pre[i] = -1;        }        for(int i = 0 ; i < n - 1 ; i++) {            int x , y;            scanf("%d%d" , &x , &y);            vc[y].push_back(x);            pre[x] = y;        }        int temp = -1;        for(int i = 1 ; i <= n ; i++) {            if(pre[i] == -1) {                temp = i;                break;            }        }        cnt = 0;        dig[temp] = ++cnt;        length[temp] = n;        dfs(temp);        int m;        scanf("%d" , &m);        char cp[2];        printf("Case #%d:\n" , ans);        build(1 , n , 1);        while(m--) {            int x , y;            scanf("%s" , cp);            if(cp[0] == ‘C‘) {                scanf("%d" , &x);                printf("%d\n" , query(dig[x] , 1));            }            if(cp[0] == ‘T‘) {                scanf("%d%d" , &x , &y);                updata(dig[x] , length[x] , 1 , y);            }        }    }    return 0;}

hdu 3974 Assign the task（线段树）