HDU 3974 Assign the task(树)

题意：有n个人，给出n-1种属于关系，形成一颗阶层树，如果上级收到的任务，所有它的子树和它本身都将从事这任务。给出两种操作，第一：分配给x任务y，第二：查询x当前做的任务。

思路：在向上找祖先的过程中，维护更新时间最晚的人的任务号。

const int N = 5e4 + 5;
int t;
struct node
{
	int lasttime;
	int task;
}e[N];
int fa[N];
int main()
{
	//freopen("in.txt", "r", stdin);
	int cas = 0;
	cin >> t;
	while (t--)
	{
		printf("Case #%d:\n", ++cas);
		int n,m;scanf("%d", &n);
		memset(fa, -1, sizeof fa);
		f(i, 1, n)e[i].lasttime = 0, e[i].task = -1;
		int x, y;
		f(i, 1, n-1)
		{
			scanf("%d%d", &x, &y);
			fa[x] = y;
		}
		scanf("%d", &m);
		string op;
		int cot = 0;
		while (m--)
		{
			cin >> op;
			if (op == "C")//所有上级
			{
				scanf("%d", &x);
				int root = x;
				int last = 0;
				int ans = -1;
				while (root!=-1)
				{
					if (e[root].lasttime > last)
					{
						ans = e[root].task;
						last = e[root].lasttime;
					}
					root = fa[root];
				}
				if (last == 0)puts("-1");
				else printf("%d\n", ans);
			}
			else {
				scanf("%d%d", &x, &y);
				e[x].lasttime = ++cot;
				e[x].task = y;
			}
		}
	}
	return 0;
}