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 译文:
有一个公司有N个员工(从1到N),公司里的每个员工都有一个直接的老板(除了整个公司的领导),如果你是某人的顶头上司,那个人就是你的下属,他的下属也都是你的下属。如果你不是任何人的老板,那么你就没有下属,没有直接上司的员工是整个公司的领导,这就意味着N员工组成了一棵树。
公司通常会指派一些任务给一些员工完成,当分配给某人的任务时,他/她会把它分配给所有的下属,换句话说,这个人和他/她的下属同时接受一项任务。此外,每当员工收到任务时,他/她将停止当前任务(如果他/她有)并启动新任务。
写,有助于在公司给某个员工分配任务后,计算出员工的当前任务。
题解:这道题不知道为什么归类为线段树这一类里面,感觉没什么关系,就是模拟吧,好像就过了,向上找直到最终祖先为止,
然后找时间戳最迟
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
const int MAXN=;
char s[];
int num,fa[MAXN],zhi[MAXN],now[MAXN],u,v,t,ans,mm,x,y,n,q,fzy=;
using namespace std;
void query(int x)
{
if (x==-) return;
if (zhi[x]!=-&&now[x]>mm)
{
mm=now[x];
ans=zhi[x];
}
query(fa[x]);
}
int main()
{
scanf("%d",&t);
while (t--)
{
printf("Case #%d:\n",++fzy);
memset(fa,-,sizeof(fa));
memset(zhi,-,sizeof(zhi));
memset(now,-,sizeof(now));
num=;
scanf("%d",&n);
for (int i=,v,u;i<n;i++)
{
scanf("%d%d",&v,&u);
fa[v]=u;
}
scanf("%d",&q);
for (int i=;i<=q;i++)
{
scanf("%s",&s);
if (s[]=='C')
{
scanf("%d",&x);
ans=-;mm=-;
query(x);
printf("%d\n",ans);
}
else
{
scanf("%d%d",&x,&y);
zhi[x]=y;
now[x]=++num;
}
}
}
}
的。