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;
}