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("%dn", ans); } else { scanf("%d%d", &a, &b); t++; po[a].task = b; po[a].time = t; } } } return 0;}