《P4092 [HEOI2016/TJOI2016] 树》
题目描述
在 2016 年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树，根为 1 ，有以下两种操作：
标记操作：对某个结点打上标记。（在最开始，只有结点 1 有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）
询问操作：询问某个结点最近的一个打了标记的祖先。（这个结点本身也算自己的祖先）
你能帮帮她吗?
输入格式
第一行两个正整数 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'&¤tChar<='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;
}