题目描述

在 2016 年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树，根为 1 ，有以下两种操作：

1. 标记操作：对某个结点打上标记。（在最开始，只有结点 1 有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）

2. 询问操作：询问某个结点最近的一个打了标记的祖先。（这个结点本身也算自己的祖先）

你能帮帮她吗?

输入格式

第一行两个正整数 N 和 Q 分别表示节点个数和操作次数。

接下来 N−1 行，每行两个正整数 u,v(1⩽u,v⩽n) 表示 u 到 v 有一条有向边。

接下来 Q 行，形如 oper num ，oper 为 C 时表示这是一个标记操作, oper 为 Q 时表示这是一个询问操作。

输出格式

输出一个正整数，表示结果

输入输出样例

输入 #1复制

5 5 
1 2 
1 3 
2 4 
2 5 
Q 2 
C 2 
Q 2 
Q 5 
Q 3

输出 #1复制

1
2
2
1

说明/提示

30% 的数据，1⩽N,Q⩽1000 ；

70% 的数据，1⩽N,Q⩽10000 ；

100% 的数据，1⩽N,Q⩽100000 。

代码实现：

#include<iostream>
#include<cstdio>
#define N 100001
using namespace std;
int nodeCount, queryCount, edgeCount, queueHead, queueTail;
int adjacencyList[N], parent[N], queue[N*5];
bool visited[N];
struct Edge
{
int nextEdge;
int targetNode;
} edges[N];
void addEdge(int source, int destination)
{
edges[++edgeCount].nextEdge=adjacencyList[source];
edges[edgeCount].targetNode=destination;
adjacencyList[source]=edgeCount;
}
void readInteger(int &value)
{
value=0;
char currentChar=getchar();
while(currentChar<'0'||currentChar>'9') currentChar=getchar();
while(currentChar>='0'&&currentChar<='9')
{
value=(value<<1)+(value<<3)+currentChar-'0';
currentChar=getchar();
}
}
void processNode(int node)
{
visited[node]=1;
parent[node]=node;
queueHead=0;
queueTail=0;
queue[++queueTail]=node;
while(queueHead<queueTail)
{
int currentNode=queue[++queueHead];
for(int i=adjacencyList[currentNode]; i; i=edges[i].nextEdge)
{
int childNode=edges[i].targetNode;
if(visited[childNode]) continue;
queue[++queueTail]=childNode;
parent[childNode]=node;
}
}
}
int main()
{
scanf("%d%d",&nodeCount,&queryCount);
for(int i=1; i<nodeCount; i++)
{
int node1, node2;
scanf("%d%d",&node1,&node2);
addEdge(node1,node2);
}
visited[1]=1;
for(int i=1; i<=nodeCount; i++) parent[i]=1;
for(int i=1; i<=queryCount; i++)
{
char operationType;
int nodeNumber;
cin>>operationType;
readInteger(nodeNumber);
if(operationType=='C'&&!visited[nodeNumber]) processNode(nodeNumber);
else if(operationType=='Q') printf("%d\n",parent[nodeNumber]);
}
return 0;
}