Pagini recente » Cod sursa (job #1748195) | Cod sursa (job #2032777) | Cod sursa (job #524745) | Cod sursa (job #1112312) | Cod sursa (job #1802875)
#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;
const int NMAX = 100000;
const int BUFFSIZE = 4096;
const int NIL = -1;
inline char GetChar() {
static char buff[BUFFSIZE];
static int pos = BUFFSIZE;
if (pos == BUFFSIZE) {
fread(buff, 1, BUFFSIZE, stdin);
pos = 0;
}
return buff[pos++];
}
inline int ReadInt() {
int q = 0;
char c;
do {
c = GetChar();
} while (not isdigit(c));
do {
q = (q << 1) + (q << 3) + (c - '0');
c = GetChar();
} while (isdigit(c));
return q;
}
char buf[BUFFSIZE];
int ptr;
inline void PutChar(const char& ch) {
buf[ptr++] = ch;
if (ptr == BUFFSIZE) {
fwrite(buf, 1, BUFFSIZE, stdout);
ptr = 0;
}
}
inline void WriteInt(int x) {
int q;
int n = 0;
char digs[6];
do {
q = (x * 205) >> 11;
digs[n++] = x - (q << 1) - (q << 3) + '0';
x = q;
} while (x);
while (n--) {
PutChar(digs[n]);
}
PutChar('\n');
}
int pointer[NMAX - 1];
int head[NMAX];
int idx[NMAX], maxIdx[NMAX];
int ancestorHeights[NMAX];
int pathParent[NMAX];
#define LSB(x) ((x) & -(x))
int MSB[2 * NMAX + 1];
void BuildSchieberVishkin(const int n) {
static int parent[NMAX], vertices[NMAX];
// dfs
{
int stackSize = 1, currIdx = 1;
while (stackSize) {
const int node = vertices[--stackSize];
idx[node] = currIdx++;
for (int i = head[node]; ~i; i = pointer[i]) {
const int son = i + 1;
parent[son] = node;
vertices[stackSize++] = son;
}
}
}
// bfs
{
int queueFront = 0, queueBack = 1;
vertices[0] = 0;
while (queueBack != queueFront) {
const int node = vertices[queueFront++];
for (int i = head[node]; ~i; i = pointer[i]) {
const int son = i + 1;
vertices[queueBack++] = son;
}
}
}
memcpy(maxIdx, idx, 4 * n);
for (int i = n - 1; i >= 0; i -= 1) {
const int node = vertices[i];
if (LSB(maxIdx[parent[node]]) < LSB(maxIdx[node])) {
maxIdx[parent[node]] = maxIdx[node];
}
}
ancestorHeights[0] = 0;
for (int i = 0; i < n; i += 1) {
ancestorHeights[vertices[i]] = ancestorHeights[parent[vertices[i]]] | LSB(maxIdx[vertices[i]]);
}
memcpy(pathParent, parent, 4 * n);
pathParent[idx[0] - 1] = 0;
for (int i = 0; i < n; i += 1) {
const int node = vertices[i];
for (int j = head[node]; ~j; j = pointer[j]) {
const int son = j + 1;
if (maxIdx[node] != maxIdx[son]) {
pathParent[idx[son] - 1] = node;
} else {
pathParent[idx[son] - 1] = pathParent[idx[node] - 1];
}
}
}
}
inline int Query(const int& x, const int& y) {
const int Ix = maxIdx[x], Iy = maxIdx[y];
const int hIx = LSB(Ix), hIy = LSB(Iy);
const int msbMask = MSB[(Ix ^ Iy) | hIx | hIy];
const int mask = LSB(ancestorHeights[x] & ancestorHeights[y] & ~msbMask);
int left, right;
if (mask == hIx) {
left = x;
} else {
const int kMask = MSB[ancestorHeights[x] & (mask - 1)];
left = pathParent[((idx[x] & ~kMask) | (kMask + 1)) - 1];
}
if (mask == hIy) {
right = y;
} else {
const int kMask = MSB[ancestorHeights[y] & (mask - 1)];
right = pathParent[((idx[y] & ~kMask) | (kMask + 1)) - 1];
}
return (idx[left] < idx[right]) ? left : right;
}
int main() {
freopen("lca.in", "r", stdin);
freopen("lca.out", "w", stdout);
int n = ReadInt(), m = ReadInt();
memset(head, NIL, 4 * n);
for (int i = 1; i < n; i += 1) {
const int x = ReadInt() - 1;
pointer[i - 1] = head[x];
head[x] = i - 1;
}
MSB[1] = 0;
for (int i = 2; i <= n + n; i += 1) {
if (i & (i - 1)) {
MSB[i] = MSB[i - 1];
} else {
MSB[i] = ((MSB[i - 1] + 1) << 1) - 1;
}
}
BuildSchieberVishkin(n);
while (m--) {
WriteInt(1 + Query(ReadInt() - 1, ReadInt() - 1));
}
fwrite(buf, 1, ptr, stdout);
return 0;
}