啊哈 我Sakiya又回来了
惊不惊喜 意不意外 (/≧▽≦)/

这是一道简单的 DFS序+线段树区间 更新问题...

题意:
对于一个公司内的员工, 每个员工有且只有一个直系上司, 而一个上司可以有许多的员工, 当给这个上司分配任务的时候, 他也会将该任务分配给所有下属(如果再次被分配将会覆盖掉之前的任务), 对于这样的结构进行两种操作

• 给员工分配任务
• 查询该员工正在进行的任务

题解:
首先我们考虑如何去表示子树的状态
通过DFS序, 前序遍历题目给出的树, 并对于每个节点的入栈出栈时间做记录, 便可以得到对于父节点的所有子节点信息的一条线段, 这样的话查询当前父节点(线段的左端点)即可得知该员工执行的任务. 这样就将一个子树问题转换成了区间问题.
之后我们考虑分配任务的情况
通过线段树的区间更新, 来对当前节点(线段)下的所有节点更新赋值, 使用LazyTag思想优化时间复杂度.

Accept G++ 202ms 4992kB:

/**
 * @author  Moe_Sakiya    sakiya@tun.moe
 * @date    2018-11-14 18:46:28
 *
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

#define leftSon left,mid,curr<<1
#define rightSon mid+1,right,curr<<1|1

using namespace std;

const int maxN = 50005;
struct DisNode
{
    int l, r;
} disArr[maxN];
vector<int> vet[maxN];
int segTree[maxN << 2];
int lazyTag[maxN << 2];
int fatherArr[maxN];
int discnt;

inline void DFS(int id) {
    disArr[id].l = discnt++;
    for (int i = 0; i < (int)vet[id].size(); i++)
        DFS(vet[id][i]);
    disArr[id].r = discnt - 1;
    return;
}

void pushDown(int curr) {
    if (lazyTag[curr] != -1) {
        lazyTag[curr << 1] = lazyTag[curr];
        lazyTag[curr << 1 | 1] = lazyTag[curr];
        segTree[curr << 1] = lazyTag[curr];
        segTree[curr << 1 | 1] = lazyTag[curr];
        lazyTag[curr] = -1;
    }
    return;
}

void buildTree(int left, int right, int curr) {
    int mid = (left + right) >> 1;
    if (left == right) {
        segTree[curr] = -1;
        return;
    }
    buildTree(leftSon);
    buildTree(rightSon);
    return;
}

void updateSection(int leftSection, int rightSection, int val, int left, int right, int curr) {
    int mid = (left + right) >> 1;
    if (leftSection <= left && right <= rightSection) {
        lazyTag[curr] = val;
        return;
    }
    pushDown(curr);
    if (leftSection <= mid)
        updateSection(leftSection, rightSection, val, leftSon);
    if (rightSection > mid)
        updateSection(leftSection, rightSection, val, rightSon);
    return;
}

int queryNode(int node, int left, int right, int curr) {
    int mid = (left + right) >> 1;
    if (left == right) {
        if (lazyTag[curr] != -1)
            segTree[curr] = lazyTag[curr];
        return segTree[curr];
    }
    pushDown(curr);
    if (node <= mid)
        return queryNode(node, leftSon);
    else
        return queryNode(node, rightSon);
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t, n, m, arg0, arg1, u, v;
    char ch[10];
    scanf("%d", &t);
    for (int kase = 1; kase <= t; kase++) {
        // INIT
        discnt = 1;
        memset(fatherArr, 0, sizeof(fatherArr));
        memset(vet, 0, sizeof(vet));
        memset(lazyTag, -1, sizeof(lazyTag));
        // DataIn
        printf("Case #%d:\n", kase);
        scanf("%d", &n);
        for (int i = 0; i < n - 1; i++) {
            scanf("%d %d", &u, &v);
            fatherArr[u] = v;
            vet[v].push_back(u);
        }
        // Deal data & Build tree
        for (int i = 1; i <= n; i++)
            if (fatherArr[i] == 0)
                DFS(i);
        buildTree(1, n, 1);
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            // Query
            scanf("%s", ch);
            switch (ch[0]) {
            case 'C':
                scanf("%d", &arg0);
                printf("%d\n", queryNode(disArr[arg0].l, 1, n, 1));
                break;
            case 'T':
                scanf("%d %d", &arg0, &arg1);
                updateSection(disArr[arg0].l, disArr[arg0].r, arg1, 1, n, 1);
                break;
            }
        }
    }
    return 0;
}