There is a company that has N employees(numbered from 1 to N),every employee in the company has a immediate boss (except for the leader of whole company).If you are the immediate boss of someone,that person is your subordinate, and all his subordinates are your subordinates as well. If you are nobody’s boss, then you have no subordinates,the employee who has no immediate boss is the leader of whole company.So it means the N employees form a tree.
The company usually assigns some tasks to some employees to
finish.When a task is assigned to someone,He/She will assigned it to all
his/her subordinates.In other words,the person and all his/her
subordinates received a task in the same time. Furthermore,whenever a
employee received a task,he/she will stop the current task(if he/she
has) and start the new one.
Write a program that will help in figuring out some employee’s
current task after the company assign some tasks to some employee.
InputThe first line contains a single positive integer T( T <= 10 ), indicates the number of test cases.
For each test case:
The first line contains an integer N (N ≤ 50,000) , which is the number of the employees.
The following N – 1 lines each contain two integers u and v, which
means the employee v is the immediate boss of employee
u(1<=u,v<=N).
The next line contains an integer M (M ≤ 50,000).
The following M lines each contain a message which is either
“C x” which means an inquiry for the current task of employee x
or
“T x y”which means the company assign task y to employee x.
(1<=x<=N,0<=y<=10^9)OutputFor each test case, print the test case number (beginning
with 1) in the first line and then for every inquiry, output the
correspond answer per line.Sample Input
1
5
4 3
3 2
1 3
5 2
5
C 3
T 2 1
C 3
T 3 2
C 3
Sample Output
Case #1:
-1
1
2题意 ： 每个老板有很多员工 ， 当老板有任务时 ， 他的所有员工都会执行此任务 ， 并且弃掉他以前的任务。思路 ：
这题是在线段树专题里的 ， 然后我自己构造了一个树 ， 用 vector 存的点 ， 但是超内存了 ， 我也不知道什么鬼 ， 搜网上的也有用 vector 写的 ， 但他们没事 ， 搞不懂 。还有一种解法 ， 是用并查集解的 ， 他与普通的区别在于 他对每个节点在多加一个参数 ，表示当前变量出现的时间截点 。 代码示例 ：
/*
* Author: ry
* Created Time: 2017/10/13 20:59:29
* File Name: 1.cpp
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <time.h>
using namespace std;
const int eps = 5e4+5;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define ll long longstruct s
{
int task;
int time;
}po[eps];int pre[eps];int main() {
int t, n, m;
int a, b;
char ch[5];
int k = 1; cin >>t;
while (t--){
cin >>n;
for(int i = 1; i <= n; i++){
po[i].task = -1;
po[i].time = 0;
}
for(int i = 1; i <= n; i++) pre[i] = i;
for(int i = 1; i < n; i++){
scanf("%d%d", &a, &b);
pre[a] = b;
}
printf("Case #%d:\n", k++);
cin >>m;
int t = 0;
while (m--){
scanf("%s", ch);
if (ch[0] == 'C'){
scanf("%d", &a);
int ans = -1, time = 0;
int i = a;
while (pre[i] != i){
if (po[i].time > time) {
ans = po[i].task;
time = po[i].time;
}
i = pre[i];
}
if (po[i].time > time) ans = po[i].task;
printf("%d\n", ans);
}
else {
scanf("%d%d", &a, &b);
t++;
po[a].task = b;
po[a].time = t;
}
}
} return 0;
}
