HDU - 3974（线段树+dfs序+区间修改+点查询）

HDU - 3974（线段树+dfs序+区间修改+点查询）

首先你需要把所有的关系串联起来，当然dfs是一个非常好用的办法。
穿起来之后就相当于对一个区间进行修改操作了
这样子之后统计一下每个点的开始进入搜索的点编号和从这个点出去的点编号，就可以得到这点如果被更新时，相应的应该更新的所有点的编号都在一个区间内，只需要更新这个区间即可。

#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn  50005
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
int tree[maxn<<3];
vector <int> edge[maxn];
int ln[maxn],rn[maxn];
bool visited[maxn];
int num,n;
void init(){
    memset(visited,false,sizeof(visited));
    memset(tree,-1,sizeof(tree));
    memset(ln,-1,sizeof(ln));
    memset(rn,-1,sizeof(rn));
    for(int i=0;i<maxn;i++) edge[i].clear();
    num=1;
}
void pushdown(int node){
    if(tree[node]!=-1){
        tree[node<<1]=tree[node];
        tree[node<<1|1]=tree[node];
        tree[node]=-1;
    }

}
void update(int node,int start,int ends,int l,int r,int val){
    if(start>=l&&ends<=r){
        tree[node]=val;
        return ;
    }
    pushdown(node);
    int mid=(start+ends)>>1;
    if(l<=mid) update(node<<1,start,mid,l,r,val);
    if(mid<r) update(node<<1|1,mid+1,ends,l,r,val);
}

int query(int node,int start,int ends,int pos){
    if(start==ends) return tree[node];
    pushdown(node);
    int mid=(start+ends)>>1;
    if(pos<=mid) query(node<<1,start,mid,pos);
    else query(node<<1|1,mid+1,ends,pos);
}

void dfs(int u){
    ln[u]=++num;
    for(int i=0;i<edge[u].size();i++){
        dfs(edge[u][i]);
    }
    rn[u]=++num;
}

int main()
{
    int t;
    cin>>t;
    int z=1;
    char s[10];
    while(t--){
        init();
        cin>>n;
        printf("Case #%d:\n",z++);
        for(int i=0;i<n-1;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            edge[y].push_back(x);
            visited[x]=true;
        }
        for(int i=1;i<=n;i++){
            if(visited[i]==false){
                dfs(i);
            }
        }
        int m;
        cin>>m;
        while(m--){
            int x,y;
            scanf("%s",s);
            if(s[0]=='C'){
                scanf("%d",&x);
                printf("%d\n",query(1,1,num,rn[x]));
            }
            else{
                scanf("%d%d",&x,&y);
                update(1,1,num,ln[x],rn[x],y);
            }
        }
    }
    return 0;
}