題目描述

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